컨셉
주어진 Binary Tree와 관련하여 작업은 주어진 Binary Tree에서 최대 완전한 하위 트리의 크기를 결정하는 것입니다.
완전한 이진 트리 – 이진 트리는 모든 레벨이 마지막 레벨 없이 완전히 채워지고 마지막 레벨에 가능한 한 모든 키가 남아 있는 경우 완전한 이진 트리로 처리됩니다. 모든 Perfect Binary Tree는 Complete Binary 트리이지만 사실이 아닌 경우 반전. 트리가 완전하지 않으면 Perfect Binary Tree도 아님을 알 수 있습니다.
입력
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.
방법
상향식으로 트리를 방문하기만 하면 됩니다. 다음으로 자식에서 부모로 재귀적으로 올 때와 관련하여 하위 트리에 대한 정보를 부모에게 전송할 수 있습니다. 전달된 정보는 일정한 시간에만 전체 트리 테스트(부모 노드에 대한)를 수행하기 위해 부모가 적용할 수 있습니다. 이 경우, 왼쪽과 오른쪽 서브트리는 모두 부모 정보에 완전 여부와 완전 여부를 알려야 하며 현재까지 발견된 완전한 바이너리 트리의 최대 크기도 반환해야 합니다.
최대 크기를 상위 데이터와 비교하여 완전한 이진 트리 속성을 확인할 수 있도록 하위 트리는 가장 큰 완전한 하위 트리를 결정하기 위해 다음 정보를 트리 위로 전송해야 합니다.
-
왼쪽 자식 또는 오른쪽 자식 하위 트리가 Perfect and Complete인지 여부를 확인하려면 bool 변수가 있어야 합니다.
-
다시 우리는 재귀의 왼쪽 및 오른쪽 자식 호출에서 상위 하위 트리가 완료되었는지 여부를 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