Cây nhị phân – Binary Tree
Phần trước mình đã hướng dẫn các bạn về danh sách liên kết. Trong phần hướng dẫn tiếp theo này, chúng ta sẽ đi tìm hiểu về cấu trúc dữ liệu Cây. Bài hôm nay sẽ trình bày về cây nhị phân(binary tree), bài tiếp theo sẽ trình bày về cây tìm kiếm nhị phân(binary seach tree).
NỘI DUNG BÀI VIẾT
1. Lý thuyết về cây nhị phân
Cây nhị phân là một cấu trúc bao gồm các Node, trong đó mỗi Node bao gồm 3 thành phần sau:
- Data element: Lưu giữ giá trị 1 phần tử với kiểu dữ liệu bất kỳ
- Left pointer: Con trỏ trỏ tới cây nhị phân bên trái của Node
- Right pointer: Con trỏ trỏ tới cây nhị phân bên phải của Node
Nếu một cây nhị phân trống, nó sẽ được biểu diễn thành con trỏ NULL. Hình ảnh dưới đây sẽ cho bạn cái nhìn tổng quát về cây nhị phân:
Các thuật ngữ sử dụng trong cấu trúc Cây
- Root: Node tổ tiên của cây. Là Node mà không có cha
- Child: Là Node con của một Node cụ thể nào đó
- Parent: Ngược lại của Child
- Siblings: Các Node có cùng một cha
- Descendant: Node có thể truy cập bằng cách duyệt từ cha tới con
- Ancestor: Node có thể truy cập bằng cách duyệt từ con đến cha
- Leaf: Node không có Child
- Internal node: Node có ít nhất 1 Child
- External node: Node không có Child
2. Cài đặt cây nhị phân
Chúng ta cần định nghĩa kiểu dữ liệu Node cho cây nhị phân. Như đã trình bày, mỗi Node của cây nhị phân sẽ như sau:
|
1 2 3 4 5 6 |
struct node { int data; //Data element struct node * left; //Pointer to left node struct node * right; //Pointer to right node }; |
2.1. Khởi tạo 1 Node
Khởi tạo Node gốc, không sử dụng con trỏ.
|
1 |
struct node root; |
Khởi tạo con trỏ Node:
|
1 2 3 4 5 6 7 |
struct node * MakeNode(int value) { struct node * temp=(node * )malloc(sizeof(node)); temp->data = value; temp->left = temp->right=NULL; return temp; } |
2.2. Tính chiều cao/ chiều sâu của cây
Ý tưởng của việc tính chiều cao là duyệt theo thứ tự PostOrder và lưu trên 2 biến độc lập cho cây con trái và cây con phải. Kết quả chiều sâu của cây là giá trị lớn hơn.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
int MaxDepth(struct node* node) { if (node==NULL) return 0; else { /* compute the depth of each subtree */ int lDepth = MaxDepth(node->left); int rDepth = MaxDepth(node->right); /* use the larger one */ if (lDepth > rDepth) return(lDepth+1); else return(rDepth+1); } } |
Đó là các chức năng cơ bản có trong cây nhị phân. Chúng ta sẽ đi sâu hơn khi tìm hiểu về cây tìm kiếm nhị phân ở bài tiếp theo.
3. Ứng dụng của Cây
- Phân cấp dữ liệu
- Hỗ trợ tìm kiếm dễ dàng hơn(xem thêm về duyệt cây)
- Thao tác trên các danh sách dữ liệu đã được sắp xếp
- Sử dụng như một quy trìn để tổng hợp hình ảnh kỹ thuật số cho hiệu ứng hình ảnh
- Sử dụng trong các thuật toán định tuyến luồng
