Cây Nhị Phân Trong C/C++ Binary Tree - Cấu Trúc Dữ Liệu Và Giải Thuật

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.

Mục lục bài viết

• 1. Cây nhị phân là gì?
• 2. Cài đặt cây nhị phân trong C/C++
  • 2.1 Khai báo cấu trúc cây nhị phân
  • 2.2 Hàm tạo một Node
  • 2.3 Nhập dữ liệu cho cây nhị phân – Create Binary Tree
• 3. Các phép duyệt cây
  • 3.1 Duyệt theo thứ tự trước
  • 3.2 Duyệt theo thứ tự giữa – Inoder
  • 3.3 Duyệt theo thứ tự sau – PostOder
• 4. Các hàm khác trên cây nhị phân
  • 4.1 Hàm tìm kiếm node có khóa x trên cây
  • 4.2 Trả về con trái, con phải, kiểm tra node lá, đếm số node

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 để biểu 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<stdlib.h> #include<stdio.h> // 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 phần tử 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 dữ 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áiGọ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 phương pháp duyệt cây đó là:

1. Duyệt theo thứ tự trước: PreOder ( N -L – R)
2. Duyêt theo thứ tự giữa: InOder ( L – N – R)
3. 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 14Kế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à 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 các 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 một số hàm thường dùng đối với cây nhị phân. Đây 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 NULLKhai 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<stdlib.h> #include<stdio.h> 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; }