Kiểm tra cây nhị phân có phải Heap trong C++

Khái niệm

Cho cây nhị phân, kiểm tra xem nó có thỏa mãn tính chất Heap (max-heap) hay không. Cây nhị phân phải thỏa mãn 2 điều kiện:

• Là cây hoàn chỉnh (complete tree): mọi cấp độ đều đầy trừ cấp độ cuối, và các nút ở cấp cuối nghiêng về trái.
• Giá trị mỗi nút ≥ giá trị nút con (max-heap).

Ví dụ minh họa (hình ảnh cây thỏa mãn và không thỏa mãn).

Phương pháp

• isCompleteUtil: kiểm tra tính hoàn chỉnh bằng cách đánh chỉ số mảng (index) cho từng nút, so sánh với tổng số nút.
• isHeapUtil: đệ quy kiểm tra tính chất heap:
  • Nút lá → true.
  • Chỉ có con trái (do cây hoàn chỉnh) → so sánh với con trái.
  • Có cả hai con → so sánh với cả hai và đệ quy hai nhánh.
• Kết hợp: isHeap = isComplete && isHeapUtil.

Ví dụ (C++)

#include <bits/stdc++.h>
using namespace std;

struct Node1{
    int key;
    struct Node1 *left, *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) return 0;
    return 1 + countNodes(root1->left) + countNodes(root1->right);
}

bool isCompleteUtil(struct Node1* root1, unsigned int index1, unsigned int number_nodes){
    if (!root1) return true;
    if (index1 >= number_nodes) return false;
    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 && !root1->right) return true;
    if (!root1->right) return (root1->key >= root1->left->key);
    if (root1->key >= root1->left->key && root1->key >= root1->right->key)
        return isHeapUtil(root1->left) && isHeapUtil(root1->right);
    return false;
}

bool isHeap(struct Node1* root1){
    unsigned int node_count = countNodes(root1);
    return isCompleteUtil(root1, 0, node_count) && isHeapUtil(root1);
}

int main(){
    struct Node1* 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