ตรวจสอบว่า Binary Tree เป็น Heap หรือไม่ใน C++

แนวคิด

Binary Tree เป็น Heap (Max-Heap) ต้องผ่าน 2 เงื่อนไข:

1. Complete Binary Tree: ทุกระดับเต็มยกเว้นระดับสุดท้าย และโหนดชิดซ้ายสุด
2. Heap Property: ค่าของโหนดทุกตัว ≥ ค่าลูกของมัน

วิธีการแก้ปัญหา

• isCompleteUtil(): ตรวจสอบความสมบูรณ์ด้วย index (root=0, left=2i+1, right=2i+2) หาก index ≥ จำนวนโหนด → ไม่สมบูรณ์
• isHeapUtil(): ตรวจสอบ Heap Property แบบ recursive
  • โหนดไม่มีลูก (leaf) → true
  • โหนดมีลูกซ้ายอย่างเดียว (เพราะ complete tree) → เปรียบเทียบกับลูกซ้าย
  • โหนดมีลูกทั้งคู่ → เปรียบเทียบกับทั้งคู่ และเรียก recursive ทั้งสองด้าน
• เป็น Heap ถ้าทั้งสองเงื่อนไขเป็นจริง

ตัวอย่างโค้ด C++

#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){ ... }
bool isCompleteUtil (struct Node1* root1, unsigned int index1, unsigned int number_nodes){ ... }
bool isHeapUtil(struct Node1* root1){ ... }
bool isHeap(struct Node1* 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;
}

ผลลัพธ์

Given binary tree is a Heap