在C ++中找到给定二叉树中最大的完整子树

概念

对于给定的二叉树，任务是确定给定的二叉树中最大完整子树的大小。

完整二叉树–如果所有级别都被完全填充而没有最后一个级别，并且最后一个级别具有所有可能的键，则将一棵二叉树视为完整二叉树。已经注意到，所有完善二叉树都是完整二叉树，但是相反，不正确。已经看到，如果一棵树不完整，那么它也不是完美的二叉树。

输入项

输出结果

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.

方法

只需以自下而上的方式参观树。接下来关于从子级到父级递归的问题，我们可以将有关子树的信息传输到父级。父级可以仅在固定时间内应用传输的信息来执行“完整树测试”（针对父级节点）。在这种情况下，左子树和右子树都需要告诉父信息，无论它们是否完美以及是否完整，它们还需要返回到目前为止找到的完整二叉树的最大大小。

我们应该注意，子树需要在树上传递以下信息来确定最大的完整子树，以便我们可以将最大大小与父级数据进行比较，以验证Complete Binary Tree属性。

应该有一个布尔变量来验证左子树或右子树是否是Perfect和Complete。
再次，我们必须通过以下3种情况来验证从递归的左右子调用中找出父子树是否完整：

已经看到，如果左边的子树是完美的，右边的是完整的，并且高度也相同，则子树的根也被视为完整的二叉子树，其大小等于左右子树的总和加一（对于当前根）。
已经看到，如果左子树是完整的，而右是完美的，并且左的高度比右的高度大一，则子树的根是完整的二叉子树，其大小等于左和右子树的总和加一（对于当前根）。但是根子树不能被声明为完美的二进制子树，因为在这种情况下，它的左孩子不是完美的。
否则，该子树不能视为完整的二叉树，而只能返回迄今为止在左侧或右侧子树中找到的最大尺寸的完整子树。因此可以得出结论，如果树不完整，则不是完美也。

示例

//This is a C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
//树的节点结构
struct node1 {
   int data;
   struct node1* left;
   struct node1* right;
};
//用于创建新节点
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;
};
//返回类型的结构
//函数findPerfectBinaryTree-
struct returnType {
   //用于存储子树是否完美
   bool isPerfect;
   //用于存储子树是否完整
   bool isComplete;
   //表示树的大小
   int size1;
   //最大的完整子树的根
   node1* rootTree;
};
//显示返回高度的辅助函数
//给定大小的树的数量
int getHeight(int size1){
   return ceil(log2(size1 + 1));
}
//显示函数返回最大
//完整的二叉树
returnType findCompleteBinaryTree(struct node1* root){
   //声明returnType-
   //需要退回
   returnType rt1;
   //如果root为NULL，则将其视为两者
   //大小为0的完美和完整的二叉树
   if (root == NULL) {
      rt1.isPerfect = true;
      rt1.isComplete = true;
      rt1.size1 = 0;
      rt1.rootTree = NULL;
      return rt1;
   }
   //显示对左子对象和右子对象的递归调用
   returnType lv1 = findCompleteBinaryTree(root->left);
   returnType rv1 = findCompleteBinaryTree(root->right);
   //案例-A-
   //已经看到，如果左边的子树是完美的，右边的是
   //完成，并且高度也相同，然后子树根
   // is also完整的二叉树 with size equal to
   //左右子树的总和加上当前根的一个
   if (lv1.isPerfect == true && rv1.isComplete == true && getHeight(lv1.size1) == getHeight(rv1.size1)) {
      rt1.isComplete = true;
      //已经看到，如果正确的子树是完美的，则
      //根也很完美
      rt1.isPerfect = (rv1.isPerfect ? true : false);
      rt1.size1 = lv1.size1 + rv1.size1 + 1;
      rt1.rootTree = root;
      return rt1;
   }
   //案例-B-
   //已经看到左子树是否完整，右子树是否
   //也很完美，左边的高度比右边的高度大
   // then sub-tree root will be a完整的二叉树 with the size equal to
   //左右子树的总和加上当前根的一个.
   //但是子树不能是完美的二进制子树。
   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;
   }
   //案例-C-
   //否则，该子树不能是完整的二叉树
   //并简单地返回最大的完整子树
   //到现在为止在左侧或右侧子树中找到
   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;
}
//显示功能以打印树的有序遍历
void inorderPrint(node1* root){
   if (root != NULL) {
      inorderPrint(root->left);
      cout << root->data << " ";
      inorderPrint(root->right);
   }
}
//驱动程式码
int main(){
   //创建树
   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完整的二叉树
   struct returnType ans1 = findCompleteBinaryTree(root);
   cout << "Size : " << ans1.size1 << endl;
   //打印找到的子树的顺序遍历
   cout << "Inorder Traversal : ";
   inorderPrint(ans1.rootTree);
   return 0;
}

输出结果

Size : 4
Inorder Traversal : 10 45 60 70

基础教程