在 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（对于当前根节点）。但是根子树不能声明为完美二叉子树，因为在这种情况下，它的左子节点不是完美的。

    • 否则，此子树不能被视为完全二叉树，只需返回迄今为止在左子树或右子树中找到的最大尺寸的完全子树。因此，可以得出结论，如果树不是完全的，那么它也不是完美的。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

现场演示

//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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告