Cộng đồng chia sẻ tri thức Lib24.vn

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

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 14:00:32


Mục lục
* * * * *

Cây đại diện cho các nút được kết nối bởi các cạnh. Chúng tôi 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ơ sở hạ tầng đặ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 con. Cây nhị phân có các lợi ích của cả mảng được sắp xếp và danh sách được liên kết vì tìm kiếm nhanh như trong 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 được liên kết.

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

Điều khoản quan trọng

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

  1. Đường dẫn - Đường dẫn đề cập đến chuỗi các nút dọc theo các cạnh của cây.
  2. Root - Nút ở đầu cây được gọi là root. 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.
  3. Cha mẹ - Bất kỳ nút nào ngoại trừ nút gốc có một cạnh hướng lên một nút được gọi là cha.
  4. Con - Nút bên dưới một nút đã cho được nối với cạnh xuống của nó được gọi là nút con của nó.
  5.  - Nút không có nút con nào được gọi là nút lá.
  6. Subtree - Subtree đại diện cho hậu duệ của một nút.
  7. Tham quan - Tham quan nghĩa là kiểm tra giá trị của nút khi điều khiển nằm trên nút.
  8. Traversing - Traversing có nghĩa là đi qua các nút theo một thứ tự cụ thể.
  9. Cấp độ - Cấp độ của một nút đại diện cho việc tạo ra một nút. Nếu nút gốc ở mức 0, thì nút con tiếp theo của nó ở cấp 1, cháu của nó ở cấp 2, v.v.
  10. khóa - Khóa biểu thị giá trị của một nút dựa trên đó thao tác tìm kiếm sẽ được thực hiện cho một nút.

Đại 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. Con trái của một nút phải có giá trị nhỏ hơn giá trị của cha mẹ và con phải của nút phải có giá trị lớn hơn giá trị cha của nó.

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

Chúng ta sẽ thực hiện 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 dưới đây. Nó có một phần dữ liệu và tham chiếu đến các nút con trái và 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 chia sẻ cấu trúc chung.

BST hoạt động cơ bản

Các hoạt động 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 -

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

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

Chèn hoạt động

Việc chèn đầu tiên tạo ra cây. Sau đó, bất cứ khi nào một yếu 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, 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 thực hiện chức năng chèn sẽ như thế này -

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 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, 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 thực hiện thuật toán này sẽ giố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;
   }  
}

Được cập nhật: 25 tháng 3 lúc 13:12:19 | Lượt xem: 388