Cây nhị phân trong C/C++ là một dạng cấu trúc dữ liệu quan trọng. Cách duyệt cây, cách thao tác với binary tree là nội dung code mình chia sẻ với bạn trong bài viết này.
Tóm Tắt
1. Cây nhị phân là gì?
Định nghĩa: Cây nhị phân (hay còn gọi là Binary Tree) là cây rỗng hoặc cây có tối đa hai nút con, trong đó thứ tự của cây được phân biệt thứ tự rõ ràng. Một nút gọi là con trái, một nút gọi là con phải.
Cây nhị phân khác với cây nhị phân tìm kiếm ở chỗ, nó không phân biệt lớn nhỏ. Phần tử có thể nằm ở bất kì vị trí nào trong cây.
Một số phép toán thường dùng trên cấu trúc cây nhị phân :
- Tạo cây rỗng
- Kiểm tra cây rỗng
- Xác định con trái của một nút
- Xác đinh con phải của một nút
- Kiểm tra nút lá
- Xác định số nút của cây
- Tạo cây mới từ hai cây có sẵn
- Tìm một đỉnh có khóa x trên cây
Có hai cách thường được sử dụng để trình diễn cây nhị phân :
- Biểu diễn bằng mảng
- Biểu diễn bằng con trỏ
Nhưng thường để dễ thao tác, người ta sẽ sử dụng con trỏ trong C hoặc C + + để biếu diễn. Bài viết này mình sử dụng cách này .
2. Cài đặt cây nhị phân trong C/C++
Mình sẽ sử dụng ngôn ngữ C để viết nhé!
Ngôn ngữ C và C++ chỉ khác nhau một chút về câu lệnh nhập xuất, khai báo con trỏ. Nếu bạn muốn code khác ngôn ngữ mình chia sẻ. Chỉ cần đổi một chút là được, quan trọng là hiểu về mặt thuật toán.
Chú ý lỗi hiển thị
Dấu & bị tự chuyển thành & amp;
2.1 Khai báo cấu trúc cây nhị phân
#include#include // Hai dong ben tren la khai bao thu vien trong C typedef int item; //kieu item la kieu nguyen struct Node { item key; //truong key cua du lieu, ban dat ten la gì thi tuy Node *Left; // Con tro trái Node *Right; // con tro phai }; typedef Node *Tree; //cay
Một node sẽ gồm key để lưu dữ liệu, tiếp theo là con trỏ trái và con trỏ phải dùng để biểu diễn con trái và con phái.
2.2 Hàm tạo một Node
Tạo một node có giá trị x cấu trúc cây nhị phân. Hàm này sẽ giúp bạn tạo một node để chèn thành phần vào Cây .
Node* makeNode(Node *p, item x) // chen 1 Node vao cay
{
p = (Node *) malloc(sizeof(Node)); // cap bo nho cho con tro.
// p = new Node*; // cap bo nho cho con tro voi C++
p->key = x;
p->Left = p->Right = NULL;
return p; // ok
}
Vì nó là một node đơn, nên ta sẽ truyền giá trị cho node. Hai con trái và phải đều đặt giá trị NULL ( trống ) .
2.3 Nhập dữ liệu cho cây nhị phân – Create Binary Tree
Hàm nhập tài liệu từ bàn phím khá quan trọng. Các bài kiểm tra và bài tập ứng dụng thấp của cây nhị phân đều sử dụng hàm này .
Điều kiện nhập của mình ở đây là nếu nhập bằng 0 thì sẽ kết thúc nhập. Thứ tự nhập như sau :
Nhập node gốc trước, nếu node này bằng 0 thì kết thúc nhập ( return NULL );
Nếu khác 0, gọi đệ quy nhập con bên trái
Gọi đệ quy nhập con phải.
Trả về node vừa nhập: Return P.
// Ham nhap du lieu key tu ban phim
Node* CreateTree(Node *p,item x)
{
printf("Node: "); scanf("%d", &x);
if (x==0)return NULL;
p= makeNode(p,x);
printf("Nhap con trai cua node %d: ",x);
p->Left=CreateTree(p->Left,x);
printf("Nhap con phai cua node %d: ",x);
p->Right=CreateTree(p->Right,x);
return p;
}
3. Các phép duyệt cây
Có 3 chiêu thức duyệt cây đó là :
- Duyệt theo thứ tự trước: PreOder ( N -L – R)
- Duyêt theo thứ tự giữa: InOder ( L – N – R)
- Duyệt theo thứ tự sau: PostOrder ( L – R – N)
Ví dụ cây nhị phân ở đầu bài viết:
Kết quả duyệt trước: 1 2 4 8 9 5 10 11 3 6 13 7 14
Kết quả duyệt giữa: 8 4 9 2 10 5 11 1 6 13 3 14 7
Kết quả duyệt sau: 8 9 4 10 11 5 2 13 6 14 7 3 1
3.1 Duyệt theo thứ tự trước
Duyệt theo thứ tự trước Preoder: Theo thứ tự Node – Left – Right ( N – L – R )
Tức là sẽ duyệt gốc trước, sau đó duyệt con trái, rồi con phải.
Code C :
//duyet theo thu tu truoc
void NLR(Tree T)
{
if(T!=NULL)
{printf("%d ",T->key);
NLR(T->Left); // de quy duyet con trai
NLR(T->Right); // De quy duyet con phai
}
}
3.2 Duyệt theo thứ tự giữa – Inoder
Cách duyệt : Left – Node – Right ( LNR ) tức là tất cả chúng ta sẽ duyệt con trái, sau đó duyệt gốc, rồi duyệt con phải .
Code C :
// Duyet theo LNR thu tu giua
void LNR(Tree T)
{
if(T!=NULL)
{
LNR(T->Left);
printf("%d ",T->key);//duyet goc
LNR(T->Right);
}
}
3.3 Duyệt theo thứ tự sau – PostOder
Thăm những gốc lần lượt theo thứ tự như sau : Con trái, con phải, rồi mới tới gốc. Left – Right – Node ( LRN )
Code :
//duyet theo thu tu sau
void LRN(Tree T)
{
if(T!=NULL)
{
LRN(T->Left);
LRN(T->Right);
printf("%d ",T->key);
}
}
4. Các hàm khác trên cây nhị phân
Giới thiệu thêm 1 số ít hàm thường dùng so với cây nhị phân. Đây hoàn toàn có thể là câu hỏi thêm, bài tập ứng dụng hoặc cũng sử dụng trong nhiều trường hợp riêng .
4.1 Hàm tìm kiếm node có khóa x trên cây
Thuật toán mình sử dụng :
Nếu Key tại Node T = x thì return T.
Nếu T = NULL return NULL
Khai báo Tree P. Gọi đệ quy tìm con trái. Nếu con trái không có, tìm con phải.
// tim nut co key x
Node* searchKey(Tree T, item x)
{ Tree p;
if (T->key==x)return T;
if(T==NULL) return NULL;
p=searchKey(T->Left,x);
if(p==NULL)searchKey(T->Right,x);
4.2 Trả về con trái, con phải, kiểm tra node lá, đếm số node
Hàm trả về con trái, hàm trả về con phải :
Node * leftChild(Tree T){
if(T!=NULL)return T->Left;
else return NULL;
}
Node * rightChild(Tree T){
if(T!=NULL)return T->Right;
else return NULL;
}
Hàm kiểm tra Node lá, đếm số node trên cây.
Node là là node không có con.
Code hoàn chỉnh một bài toán về cây nhị phân cơ bản:
int isLeaf(Tree T){
if(T!=NULL)
return (T->Left==NULL && T->Right==NULL);
else return NULL;
}
// Dem so node tren cay
int numberNode(Tree T){
if(T==NULL)return 0;
else return (1+numberNode(leftChild(T))+numberNode(rightChild(T)));
}
Hàm kiểm tra số node trên cây nhị phân. Gọi đệ quy cho con trái, gọi đệ quy cho con phải là được .
Ngoài ra còn có hàm
#include#include typedef int item; //kieu item la kieu nguyen struct Node { item key; //truong key cua du lieu Node *Left, *Right; //con trai va con phai }; typedef Node *Tree; //cay Node* makeNode(Node *p, item x) // chen 1 Node vao cay { p = (Node *) malloc(sizeof(Node)); p->key = x; p->Left = p->Right = NULL; return p; // ok } Node* CreateTree(Node *p,item x) // nhap cay { printf("Node: "); scanf("%d", &x); if (x==0)return NULL; p= makeNode(p,x); printf("Nhap con trai cua node %d: ",x); p->Left=CreateTree(p->Left,x); printf("Nhap con phai cua node %d: ",x); p->Right=CreateTree(p->Right,x); return p; } // Duyet theo LNR thu tu giua void LNR(Tree T) { if(T!=NULL) { LNR(T->Left); printf("%d ",T->key);//duyet goc LNR(T->Right); } } void NLR(Tree T)//duyet theo thu tu truoc { if(T!=NULL) {printf("%d ",T->key); NLR(T->Left); NLR(T->Right); } } void LRN(Tree T)//duyet theo thu tu sau { if(T!=NULL) { LRN(T->Left); LRN(T->Right); printf("%d ",T->key); } } Node* searchKey(Tree T, item x) // tim nut co key x { Tree p; if (T->key==x)return T; if(T==NULL) return NULL; p=searchKey(T->Left,x); if(p==NULL)searchKey(T->Right,x); } Node * leftChild(Tree T){ if(T!=NULL)return T->Left; else return NULL; } Node * rightChild(Tree T){ if(T!=NULL)return T->Right; else return NULL; } int isLeaf(Tree T){ if(T!=NULL) return (T->Left==NULL&&T->Right==NULL); else return NULL; } int numberNode(Tree T){ if(T==NULL)return 0; else return (1+numberNode(leftChild(T))+numberNode(rightChild(T))); } int main() { Tree T; T=NULL; //Tao cay rong Node *p=NULL;item x; printf("Nhap 0 de chuyen sang nhap node khac hoac thoat"); T=CreateTree(p,x); //Nhap cay printf("Duyet cay theo thu tu giua LNR: \n"); LNR(T); printf("\n"); printf("Duyet cay theo thu tu truoc NLR: \n"); NLR(T); printf("\n"); printf("Duyet cay theo thu tu sau LRN: \n"); LRN(T); printf("\n"); // Node *P; // // printf("Nhap vao key can tim: "); // scanf("%d", &x); // P = searchKey(T, x); // if (P != NULL) printf("Tim thay key %d\n", P->key); // else printf("Key %d khong co trong cay\n", x); // // if (delKey(T, x)) printf("Xoa thanh cong\n"); // else printf("Khong tim thay key %d can xoan", x); // printf("Duyet cay theo thu tu giua: \n"); // LNR(T); // printf("\n"); //}while(chon!=4); return 0; }
Source: https://final-blade.com
Category: Kiến thức Internet
