Cây nhị phân hoàn chỉnh

Trong hướng dẫn này, bạn sẽ tìm hiểu về một cây nhị phân hoàn chỉnh và các kiểu khác nhau của nó. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của một cây nhị phân hoàn chỉnh trong C, C ++, Java và Python.

Cây nhị phân hoàn chỉnh là cây nhị phân trong đó tất cả các mức được lấp đầy hoàn toàn ngoại trừ có thể là mức thấp nhất, được điền từ bên trái.

Một cây nhị phân hoàn chỉnh cũng giống như một cây nhị phân đầy đủ, nhưng có hai điểm khác biệt chính

  1. Tất cả các phần tử lá phải nghiêng về bên trái.
  2. Phần tử lá cuối cùng có thể không có anh chị em bên phải, tức là một cây nhị phân hoàn chỉnh không phải là một cây nhị phân đầy đủ.
Cây nhị phân hoàn chỉnh

Cây nhị phân đầy đủ so với cây nhị phân hoàn chỉnh

So sánh giữa cây nhị phân đầy đủ và cây nhị phân hoàn chỉnh So sánh giữa cây nhị phân đầy đủ và cây nhị phân hoàn chỉnh So sánh giữa cây nhị phân đầy đủ và cây nhị phân hoàn chỉnh So sánh giữa cây nhị phân đầy đủ và cây nhị phân hoàn chỉnh

Làm thế nào một cây nhị phân hoàn chỉnh được tạo ra?

  1. Chọn phần tử đầu tiên của danh sách làm nút gốc. (số phần tử ở cấp I: 1) Chọn phần tử đầu tiên làm gốc
  2. Đặt phần tử thứ hai làm phần tử con bên trái của nút gốc và phần tử thứ ba làm phần tử con bên phải. (số phần tử ở cấp II: 2) 12 là con bên trái và 9 là con bên phải
  3. Đặt hai phần tử tiếp theo là con của nút bên trái của mức thứ hai. Một lần nữa, đặt hai phần tử tiếp theo là con của nút bên phải của phần tử cấp hai (số phần tử trên các phần tử cấp III: 4)).
  4. Tiếp tục lặp lại cho đến khi bạn đến phần tử cuối cùng. 5 là con bên trái và 6 là con bên phải

Ví dụ về Python, Java và C / C ++

Python Java C C ++ 
 # Checking if a binary tree is a complete binary tree in C class Node: def __init__(self, item): self.item = item self.left = None self.right = None # Count the number of nodes def count_nodes(root): if root is None: return 0 return (1 + count_nodes(root.left) + count_nodes(root.right)) # Check if the tree is complete binary tree def is_complete(root, index, numberNodes): # Check if the tree is empty if root is None: return True if index>= numberNodes: return False return (is_complete(root.left, 2 * index + 1, numberNodes) and is_complete(root.right, 2 * index + 2, numberNodes)) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) node_count = count_nodes(root) index = 0 if is_complete(root, index, node_count): print("The tree is a complete binary tree") else: print("The tree is not a complete binary tree") 
 // Checking if a binary tree is a complete binary tree in Java // Node creation class Node ( int data; Node left, right; Node(int item) ( data = item; left = right = null; ) ) class BinaryTree ( Node root; // Count the number of nodes int countNumNodes(Node root) ( if (root == null) return (0); return (1 + countNumNodes(root.left) + countNumNodes(root.right)); ) // Check for complete binary tree boolean checkComplete(Node root, int index, int numberNodes) ( // Check if the tree is empty if (root == null) return true; if (index>= numberNodes) return false; return (checkComplete(root.left, 2 * index + 1, numberNodes) && checkComplete(root.right, 2 * index + 2, numberNodes)); ) public static void main(String args()) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.right = new Node(5); tree.root.left.left = new Node(4); tree.root.right.left = new Node(6); int node_count = tree.countNumNodes(tree.root); int index = 0; if (tree.checkComplete(tree.root, index, node_count)) System.out.println("The tree is a complete binary tree"); else System.out.println("The tree is not a complete binary tree"); ) )
 // Checking if a binary tree is a complete binary tree in C #include #include #include struct Node ( int key; struct Node *left, *right; ); // Node creation struct Node *newNode(char k) ( struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->key = k; node->right = node->left = NULL; return node; ) // Count the number of nodes int countNumNodes(struct Node *root) ( if (root == NULL) return (0); return (1 + countNumNodes(root->left) + countNumNodes(root->right)); ) // Check if the tree is a complete binary tree bool checkComplete(struct Node *root, int index, int numberNodes) ( // Check if the tree is complete if (root == NULL) return true; if (index>= numberNodes) return false; return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes)); ) int main() ( struct Node *root = NULL; root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); int node_count = countNumNodes(root); int index = 0; if (checkComplete(root, index, node_count)) printf("The tree is a complete binary tree"); else printf("The tree is not a complete binary tree"); )
 // Checking if a binary tree is a complete binary tree in C++ #include using namespace std; struct Node ( int key; struct Node *left, *right; ); // Create node struct Node *newNode(char k) ( struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->key = k; node->right = node->left = NULL; return node; ) // Count the number of nodes int countNumNodes(struct Node *root) ( if (root == NULL) return (0); return (1 + countNumNodes(root->left) + countNumNodes(root->right)); ) // Check if the tree is a complete binary tree bool checkComplete(struct Node *root, int index, int numberNodes) ( // Check if the tree is empty if (root == NULL) return true; if (index>= numberNodes) return false; return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes)); ) int main() ( struct Node *root = NULL; root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); int node_count = countNumNodes(root); int index = 0; if (checkComplete(root, index, node_count)) cout << "The tree is a complete binary tree"; else cout << "The tree is not a complete binary tree"; )

Mối quan hệ giữa chỉ mục mảng và phần tử cây

Một cây nhị phân hoàn chỉnh có một đặc tính thú vị mà chúng ta có thể sử dụng để tìm con và cha của bất kỳ nút nào.

Nếu chỉ số của bất kỳ phần tử nào trong mảng là i, phần tử trong chỉ mục 2i+1sẽ trở thành phần tử con bên trái và phần tử trong 2i+2chỉ mục sẽ trở thành phần tử con bên phải. Ngoài ra, phần tử cha của bất kỳ phần tử nào tại chỉ mục i được cho bởi giới hạn dưới của (i-1)/2.

Hãy kiểm tra nó ra,

 Con bên trái của 1 (chỉ số 0) = phần tử trong (2 * 0 + 1) chỉ mục = phần tử trong 1 chỉ mục = 12 Con bên phải của 1 = phần tử trong (2 * 0 + 2) chỉ số = phần tử trong 2 chỉ mục = 9 Tương tự, Con bên trái của 12 (chỉ số 1) = phần tử trong (2 * 1 + 1) chỉ mục = phần tử trong 3 chỉ mục = 5 Con bên phải của 12 = phần tử trong (2 * 1 + 2) chỉ mục = phần tử trong 4 chỉ mục = 6

Hãy để chúng tôi cũng xác nhận rằng các quy tắc giữ cho việc tìm kiếm cha của bất kỳ nút nào

 Cấp độ gốc của 9 (vị trí 2) = (2-1) / 2 = ½ = 0.5 ~ 0 chỉ số = 1 Cấp độ gốc của 12 (vị trí 1) = (1-1) / 2 = 0 chỉ số = 1

Hiểu được ánh xạ của các chỉ mục mảng với các vị trí cây là rất quan trọng để hiểu cách thức hoạt động của Cấu trúc dữ liệu Heap và cách nó được sử dụng để thực hiện Sắp xếp Heap.

Hoàn thành các ứng dụng cây nhị phân

  • Cấu trúc dữ liệu dựa trên đống
  • Sắp xếp đống

thú vị bài viết...