資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢給定二叉樹中最大的完全子樹
概念
對於給定的二叉樹，任務是確定給定二叉樹中最大完全子樹的大小。
完全二叉樹 – 如果所有層都完全填充（最後一層可能除外），並且最後一層的所有鍵都儘可能地靠左，則二叉樹被視為完全二叉樹。需要注意的是，所有完美二叉樹都是完全二叉樹，但反之則不成立。如果一棵樹不是完全的，那麼它也不是完美二叉樹。
輸入
2 / \ 3 4 / \ / \ 5 6 7 8 / \ / 9 10 11
輸出
Size : 10 Inorder Traversal : 9 5 10 3 11 6 2 7 4 8 The above given tree is a complete binary tree.
輸入
51 / \ 31 61 / \ / \ 6 21 46 71 / 11
輸出
Size : 4(With respect of right subtree) Inorder Traversal : 11 46 61 71 The above given tree is not a complete binary tree.
方法
只需自底向上遍歷樹。接下來，在從子節點到父節點的遞迴中向上返回時，我們可以將有關子樹的資訊傳遞給父節點。父節點可以使用傳遞的資訊在恆定時間內執行完全樹測試（對於父節點）。在這種情況下，左右子樹都需要告訴父節點它們是否為完美或完全的，並且它們還需要返回迄今為止找到的最大完全二叉樹的大小。
我們應該注意，子樹需要向上樹傳遞以下資訊以確定最大的完全子樹，以便我們可以將最大大小與父節點的資料進行比較以驗證完全二叉樹屬性。
應該存在一個布林變數來驗證左子樹或右子樹是否為完美和完全的。
我們再次需要驗證，在遞迴中的左子節點和右子節點呼叫中，我們是否透過以下 3 種情況找出父節點子樹是否為完全的：
如果左子樹是完美的，右子樹是完全的，並且它們的高度相同，則子樹根節點也被視為完全二叉子樹，其大小等於左子樹和右子樹的總和加 1（對於當前根節點）。
如果左子樹是完全的，右子樹是完美的，並且左子樹的高度比右子樹大 1，則子樹根節點是完全二叉子樹，其大小等於左子樹和右子樹的總和加 1（對於當前根節點）。但是根子樹不能宣告為完美二叉子樹，因為在這種情況下，它的左子節點不是完美的。
否則，此子樹不能被視為完全二叉樹，只需返回迄今為止在左子樹或右子樹中找到的最大尺寸的完全子樹。因此，可以得出結論，如果樹不是完全的，那麼它也不是完美的。
示例
//This is a C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Node structure of the tree
struct node1 {
int data;
struct node1* left;
struct node1* right;
};
// For creating a new node
struct node1* newNode(int data){
struct node1* node1 = (struct node1*)malloc(sizeof(struct node1));
node1->data = data;
node1->left = NULL;
node1->right = NULL;
return node1;
};
// Shows structure for return type of
// function findPerfectBinaryTree
struct returnType {
// For storing if sub-tree is perfect or not
bool isPerfect;
// For storing if sub-tree is complete or not
bool isComplete;
// Indicates size of the tree
int size1;
// Root of biggest complete sub-tree
node1* rootTree;
};
// Shows helper function that returns height
// of the tree given size
int getHeight(int size1){
return ceil(log2(size1 + 1));
}
// Shows function to return the biggest
// complete binary sub-tree
returnType findCompleteBinaryTree(struct node1* root){
// Declaring returnType that
// needs to be returned
returnType rt1;
// If root is NULL then it is considered as both
// perfect and complete binary tree of size 0
if (root == NULL) {
rt1.isPerfect = true;
rt1.isComplete = true;
rt1.size1 = 0;
rt1.rootTree = NULL;
return rt1;
}
// Shows recursive call for left and right child
returnType lv1 = findCompleteBinaryTree(root->left);
returnType rv1 = findCompleteBinaryTree(root->right);
// CASE - A
// It has been seen that if left sub-tree is perfect and right is
// complete and there height is also same then sub-tree root
// is also complete binary sub-tree with size equal to
// sum of left and right subtrees plus one for current root
if (lv1.isPerfect == true && rv1.isComplete == true && getHeight(lv1.size1) == getHeight(rv1.size1)) {
rt1.isComplete = true;
// It has been seen that if right sub-tree is perfect then
// root is also perfect
rt1.isPerfect = (rv1.isPerfect ? true : false);
rt1.size1 = lv1.size1 + rv1.size1 + 1;
rt1.rootTree = root;
return rt1;
}
// CASE - B
// It has been seen if left sub-tree is complete and right is
// also perfect and the left height is greater than height of right by one
// then sub-tree root will be a complete binary sub-tree with the size equal to
// sum of left and right subtrees plus one for current root.
// But sub-tree cannot be perfect binary sub-tree.
if (lv1.isComplete == true && rv1.isPerfect == true && getHeight(lv1.size1) == getHeight(rv1.size1) + 1) {
rt1.isComplete = true;
rt1.isPerfect = false;
rt1.size1 = lv1.size1 + rv1.size1 + 1;
rt1.rootTree = root;
return rt1;
}
// CASE - C
// Otherwise this sub-tree cannot be a complete binary tree
// and simply return the biggest sized complete sub-tree
// found till now in the left or right sub-trees
rt1.isPerfect = false;
rt1.isComplete = false;
rt1.size1 = max(lv1.size1, rv1.size1);
rt1.rootTree = (lv1.size1 > rv1.size1 ? lv1.rootTree :
rv1.rootTree);
return rt1;
}
// Shows function to print the inorder traversal of the tree
void inorderPrint(node1* root){
if (root != NULL) {
inorderPrint(root->left);
cout << root->data << " ";
inorderPrint(root->right);
}
}
// Driver code
int main(){
// Creating the tree
struct node1* root = newNode(50);
root->left = newNode(30);
root->right = newNode(60);
root->left->left = newNode(5);
root->left->right = newNode(20);
root->right->left = newNode(45);
root->right->right = newNode(70);
root->right->left->left = newNode(10);
// Getting the biggest sized complete binary sub-tree
struct returnType ans1 = findCompleteBinaryTree(root);
cout << "Size : " << ans1.size1 << endl;
// Printing the inorder traversal of the found sub-tree
cout << "Inorder Traversal : ";
inorderPrint(ans1.rootTree);
return 0;
}輸出
Size : 4 Inorder Traversal : 10 45 60 70
更新於: 2020-07-23
231 次檢視
廣告