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.

メソッド

ボトムアップ方式でツリーにアクセスするだけです。次に、子から親への再帰の発生に関して、サブツリーに関する情報を親に転送できます。転送された情報は、親が一定時間内にのみ完全なツリーテスト（親ノードに対して）を実行するために適用できます。この場合、左と右の両方のサブツリーは、それらが完全であるかどうか、完全であるかどうかを親情報に伝える必要があり、また、これまでに見つかった完全な二分木の最大サイズを返す必要があります。

最大サイズを親のデータと比較して完全な二分木プロパティを検証できるように、サブツリーは最大の完全なサブツリーを決定するために次の情報をツリーに転送する必要があることに注意してください。

• 左の子または右の子のサブツリーが完全で完全であるかどうかを確認するには、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