資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中檢查給定的二叉樹是否為堆
概念
對於給定的二叉樹，我們需要驗證它是否具有堆屬性。二叉樹需要滿足以下兩個條件才能成為堆：
二叉樹應該是一棵完全二叉樹（即除了最後一層外，所有層都應該填滿）。
二叉樹的每個節點的值都應該大於或等於其子節點（考慮最大堆）。
示例
對於以下示例，這棵樹包含堆屬性：
以下示例不具有堆屬性：
方法
需要分別驗證上述每個條件，為了驗證完整性，編寫了 isComplete（此函式檢查二叉樹是否完整）和為了驗證堆屬性編寫了 isHeapUtil 函式。
在編寫 isHeapUtil 函式時，我們考慮以下幾點：
每個節點最多可以有 2 個子節點，0 個子節點（最後一層節點）或 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
更新於： 2020-07-23
294 次檢視
廣告