Cây nhị phân – Binary 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:

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:

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

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

Mr4 Java Developer

Đi lên từ nền tảng vững chắc!