개념
주어진 이진 트리에 대해 힙 속성이 있는지 여부를 확인해야 합니다. 이진 트리는 힙이 되기 위해 다음 두 가지 조건을 충족해야 합니다. –
-
이진 트리는 완전한 트리여야 합니다(즉, 마지막을 제외한 모든 레벨이 가득 차 있어야 함).
-
바이너리 트리의 모든 노드 값은 자식 노드보다 크거나 같아야 합니다(max-heap 고려).
예
다음 예와 관련하여 이 트리에는 힙 속성이 포함되어 있습니다. –
다음 예제에는 힙 속성이 없습니다. –
방법
위의 각각의 조건을 별도로 검증하는 것이 필요하며, 완전성 검증을 위한 isComplete(이 함수는 바이너리 트리의 완성 여부를 체크)와 힙 검증을 위한 isHeapUtil 함수가 작성되어 있다.
isHeapUtil 함수 작성과 관련하여 다음 사항을 고려합니다. –
-
각각의 모든 노드는 2개의 자식, 0개의 자식(마지막 수준 노드) 또는 1개의 자식(이러한 노드가 최대 1개일 수 있음)을 가질 수 있습니다.
-
노드에 자식이 없는 경우 리프 노드이고 true(기본 사례)를 반환합니다.
-
노드에 하나의 자식이 있는 경우(완전한 트리이므로 왼쪽 자식이어야 함) 이 노드를 단일 자식과만 비교해야 합니다.
-
노드에 둘 다 자식이 있는 것으로 확인되면 두 하위 트리에 대해 반복 시 노드에서 힙 속성을 확인하십시오.
예시
/* 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; }
출력
Given binary tree is a Heap