Kiểm tra xem một Cây nhị phân đã cho có phải là Heap trong C ++ hay không

Khái niệm

Đối với một cây nhị phân nhất định, chúng ta cần xác minh xem nó có thuộc tính heap hay không, Cây nhị phân cần đáp ứng hai điều kiện sau để trở thành một heap -

• Cây nhị phân phải là một cây hoàn chỉnh (tức là tất cả các cấp ngoại trừ cấp cuối cùng phải đầy đủ).

• Giá trị mỗi nút của cây nhị phân phải lớn hơn hoặc bằng nút con của nó (xem xét max-heap).

Ví dụ

Đối với ví dụ sau, cây này chứa thuộc tính đống -

Ví dụ sau không có thuộc tính heap -

Phương pháp

Cần phải xác minh từng điều kiện ở trên một cách riêng biệt, để xác minh tính đầy đủ isComplete (Hàm này kiểm tra xem cây nhị phân có đầy đủ hay không) và để xác minh đống hàm isHeapUtil được viết.

Đối với việc viết hàm isHeapUtil, chúng tôi xem xét những điều sau -

• Mỗi và mọi Node có thể có 2 con, 0 con (các nút cấp cuối) hoặc 1 con (có thể có tối đa một nút như vậy).

• Nếu người ta thấy rằng Node không có nút con thì đó là nút lá và trả về true (Trường hợp cơ sở)

• Nếu thấy rằng Node có một nút con (nó phải là nút con bên trái vì nó là một cây hoàn chỉnh) thì chúng ta yêu cầu so sánh nút này với nút con duy nhất của nó.

• Nếu người ta thấy rằng Node có cả hai con thì hãy xác minh thuộc tính heap tại Node định kỳ cho cả hai cây con.

Ví dụ

/* C++ program to checks if a binary tree is max heap or not */
#include <bits/stdc++.h>
using namespace std;
struct Node1{
   int key;
   struct Node1 *left;
   struct Node1 *right;
};
struct Node1 *newNode(int k){
   struct Node1 *node1 = new Node1;
   node1->key = k;
   node1->right = node1->left = NULL;
   return node1;
}
unsigned int countNodes(struct Node1* root1){
   if (root1 == NULL)
      return (0);
   return (1 + countNodes(root1->left) + countNodes(root1->right));
}
bool isCompleteUtil (struct Node1* root1, unsigned int index1, unsigned int number_nodes){
   if (root1 == NULL)
      return (true);
   if (index1 >= number_nodes)
      return (false);
   // Recur for left and right subtrees
   return (isCompleteUtil(root1->left, 2*index1 + 1, number_nodes) && isCompleteUtil(root1->right, 2*index1 + 2, number_nodes));
}
bool isHeapUtil(struct Node1* root1){
   if (root1->left == NULL && root1->right == NULL)
      return (true);
   if (root1->right == NULL){
      return (root1->key >= root1->left->key);
   }
   else{
      if (root1->key >= root1->left->key &&
         root1->key >= root1->right->key)
      return ((isHeapUtil(root1->left)) &&
      (isHeapUtil(root1->right)));
      else
         return (false);
   }
}
bool isHeap(struct Node1* root1){
   unsigned int node_count = countNodes(root1);
   unsigned int index1 = 0;
   if (isCompleteUtil(root1, index1, node_count) &&
      isHeapUtil(root1))
   return true;
   return false;
}
// Driver program
int main(){
   struct Node1* root1 = NULL;
   root1 = newNode(10);
   root1->left = newNode(9);
   root1->right = newNode(8);
   root1->left->left = newNode(7);
   root1->left->right = newNode(6);
   root1->right->left = newNode(5);
   root1->right->right = newNode(4);
   root1->left->left->left = newNode(3);
   root1->left->left->right = newNode(2);
   root1->left->right->left = newNode(1);
   if (isHeap(root1))
      cout << "Given binary tree is a Heap\n";
   else
      cout << "Given binary tree is not a Heap\n";
   return 0;
}

Đầu ra

Given binary tree is a Heap