Khái niệm
Đối với một Cây nhị phân nhất định, nhiệm vụ là xác định kích thước của cây con hoàn chỉnh tối đa trong Cây nhị phân đã cho.
Cây nhị phân hoàn chỉnh - Cây nhị phân hoàn chỉnh được coi là Cây nhị phân hoàn chỉnh nếu tất cả các cấp được lấp đầy hoàn toàn mà không có cấp độ cuối cùng và cấp độ cuối cùng còn lại tất cả các khóa càng tốt. ngược lại KHÔNG đúng. Người ta đã thấy rằng nếu một cây không hoàn chỉnh thì nó cũng không phải là Cây nhị phân hoàn hảo.
Đầu vào
2 / \ 3 4 / \ / \ 5 6 7 8 / \ / 9 10 11
Đầu ra
Size : 10 Inorder Traversal : 9 5 10 3 11 6 2 7 4 8 The above given tree is a complete binary tree.
Đầu vào
51 / \ 31 61 / \ / \ 6 21 46 71 / 11
Đầu ra
Size : 4(With respect of right subtree) Inorder Traversal : 11 46 61 71 The above given tree is not a complete binary tree.
Phương pháp
Chỉ cần thăm cây theo cách từ dưới lên. Tiếp theo, liên quan đến việc xuất hiện trong đệ quy từ con đến cha, chúng ta có thể chuyển thông tin về cây con cho cây mẹ. Thông tin đã chuyển chỉ có thể được áp dụng bởi cha mẹ để thực hiện kiểm tra Cây hoàn chỉnh (đối với nút cha) trong thời gian không đổi. Trong trường hợp này, cả cây con bên trái và bên phải đều yêu cầu tổng số thông tin gốc cho dù chúng có hoàn hảo hay không và đầy đủ hay không và chúng cũng cần trả về kích thước tối đa của cây nhị phân hoàn chỉnh được tìm thấy cho đến nay.
Chúng tôi cần lưu ý rằng các cây con cần chuyển thông tin sau lên cây để xác định cây con hoàn chỉnh lớn nhất để chúng tôi có thể so sánh kích thước tối đa với dữ liệu của cây mẹ để xác minh thuộc tính Cây nhị phân hoàn chỉnh.
-
Một biến bool phải tồn tại để xác minh xem cây con bên trái hay cây con bên phải là Hoàn hảo và Hoàn chỉnh hay không.
-
Một lần nữa, chúng ta phải xác minh rằng từ các lệnh gọi con trái và phải trong đệ quy, chúng ta tìm xem cây con mẹ có Hoàn thành hay không bằng cách sau 3 trường hợp -
-
Người ta thấy rằng nếu cây con bên trái là hoàn hảo và bên phải là hoàn chỉnh và có chiều cao cũng bằng nhau thì gốc cây con cũng được coi là cây con nhị phân hoàn chỉnh với kích thước bằng tổng của cây con bên trái và bên phải cộng với một (đối với gốc hiện tại).
-
Người ta thấy rằng nếu cây con bên trái là hoàn chỉnh và bên phải là hoàn hảo và chiều cao của bên trái lớn hơn bên phải một thì gốc cây con là cây con nhị phân hoàn chỉnh với kích thước bằng tổng của cây con bên trái và bên phải cộng với một (đối với gốc hiện tại) . Nhưng cây con gốc không thể được khai báo là cây con nhị phân hoàn hảo vì trong trường hợp này, cây con bên trái của nó không hoàn hảo.
-
Nếu không, cây con này không thể được coi là một cây nhị phân hoàn chỉnh và chỉ cần trả về cây con hoàn chỉnh có kích thước lớn nhất được tìm thấy cho đến nay trong các cây con bên trái hoặc bên phải. cũng hoàn hảo.
-
Ví dụ
//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;
} Đầu ra
Size : 4 Inorder Traversal : 10 45 60 70