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).

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:

1. Data element: Lưu giữ giá trị 1 phần tử với kiểu dữ liệu bất kỳ
2. Left pointer: Con trỏ trỏ tới cây nhị phân bên trái của Node
3. 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:

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ỏ.

struct node root;

Khởi tạo con trỏ Node:

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.

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

1. Phân cấp dữ liệu
2. Hỗ trợ tìm kiếm dễ dàng hơn(xem thêm về duyệt cây)
3. Thao tác trên các danh sách dữ liệu đã được sắp xếp
4. 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
5. Sử dụng trong các thuật toán định tuyến luồng