Cấu trúc dữ liệu và thuật toán - Cây

Cây đại diện cho các nút được kết nối bởi các cạnh. Chúng ta sẽ thảo luận cụ thể về cây nhị phân hoặc cây tìm kiếm nhị phân.

Cây nhị phân là một cơ cấu dữ liệu đặc biệt được sử dụng cho mục đích lưu trữ dữ liệu. Cây nhị phân có một điều kiện đặc biệt là mỗi nút có thể có tối đa hai nút con. Cây nhị phân có những lợi ích của cả mảng có thứ tự và danh sách được liên kết vì tìm kiếm nhanh như trong một mảng được sắp xếp và thao tác chèn hoặc xóa cũng nhanh như trong danh sách liên kết.

Điều khoản quan trọng

Sau đây là các điều khoản quan trọng đối với cây.

Path - Đường dẫn đề cập đến chuỗi các nút dọc theo các cạnh của cây.
Root- Nút ở ngọn cây gọi là gốc. Chỉ có một gốc trên mỗi cây và một đường dẫn từ nút gốc đến bất kỳ nút nào.
Parent - Bất kỳ nút nào ngoại trừ nút gốc đều có một cạnh hướng lên trên một nút được gọi là cha.
Child - Nút bên dưới một nút nhất định được nối bởi cạnh của nó hướng xuống được gọi là nút con của nó.
Leaf - Nút không có nút con nào được gọi là nút lá.
Subtree - Cây con đại diện cho con cháu của một nút.
Visiting - Tham quan đề cập đến việc kiểm tra giá trị của một nút khi quyền điều khiển ở trên nút.
Traversing - Đi ngang có nghĩa là đi qua các nút theo một thứ tự cụ thể.
Levels- Mức của một nút thể hiện sự sinh ra của một nút. Nếu nút gốc ở mức 0, thì nút con tiếp theo của nó ở mức 1, nút cháu của nó ở mức 2, v.v.
keys - Khóa đại diện cho một giá trị của một nút dựa trên đó hoạt động tìm kiếm sẽ được thực hiện cho một nút.

Biểu diễn cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân thể hiện một hành vi đặc biệt. Nút con bên trái của nút phải có giá trị nhỏ hơn giá trị của nút cha và nút con bên phải của nút phải có giá trị lớn hơn giá trị mẹ của nó.

Chúng ta sẽ triển khai cây bằng cách sử dụng đối tượng nút và kết nối chúng thông qua các tham chiếu.

Nút cây

Mã để viết một nút cây sẽ tương tự như những gì được đưa ra bên dưới. Nó có một phần dữ liệu và các tham chiếu đến các nút con bên trái và bên phải của nó.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

Trong một cây, tất cả các nút đều có chung cấu trúc.

BST Thao tác Cơ bản

Các thao tác cơ bản có thể được thực hiện trên cấu trúc dữ liệu cây tìm kiếm nhị phân, như sau:

Insert - Chèn một phần tử trong cây / tạo cây.
Search - Tìm kiếm một phần tử trong cây.
Preorder Traversal - Đi ngang cây theo cách đặt hàng trước.
Inorder Traversal - Đi ngang cây theo thứ tự.
Postorder Traversal - Đi ngang cây theo thứ tự có sau.

Chúng ta sẽ học cách tạo (chèn vào) một cấu trúc cây và tìm kiếm một mục dữ liệu trong một cây trong chương này. Chúng ta sẽ tìm hiểu về các phương pháp duyệt cây trong chương tới.

Chèn hoạt động

Lần chèn đầu tiên tạo ra cây. Sau đó, bất cứ khi nào một phần tử được chèn vào, trước tiên hãy xác định vị trí thích hợp của nó. Bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu nhỏ hơn giá trị khóa, hãy tìm kiếm vị trí trống trong cây con bên trái và chèn dữ liệu. Nếu không, hãy tìm kiếm vị trí trống trong cây con bên phải và chèn dữ liệu.

Thuật toán

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
	
end If

Thực hiện

Việc triển khai chức năng chèn sẽ giống như sau:

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty, create root node
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent  = NULL;

      while(1) {                
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }
			
         //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Hoạt động tìm kiếm

Bất cứ khi nào một phần tử cần được tìm kiếm, hãy bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu nhỏ hơn giá trị khóa, hãy tìm kiếm phần tử trong cây con bên trái. Nếu không, hãy tìm kiếm phần tử trong cây con bên phải. Thực hiện theo cùng một thuật toán cho mỗi nút.

Thuật toán

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if

Việc triển khai thuật toán này sẽ trông như thế này.

struct node* search(int data) {
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data); 
      
      //go to left tree

      if(current->data > data) {
         current = current->leftChild;
      }
      //else go to right tree
      else {                
         current = current->rightChild;
      }

      //not found
      if(current == NULL) {
         return NULL;
      }

      return current;
   }  
}

Để biết về việc thực hiện cấu trúc dữ liệu cây tìm kiếm nhị phân, vui lòng nhấp vào đây .