C++の二分木に存在する二分探索木の数を数える

例

入力

値を入力した後に作成されるツリーを以下に示します-

出力

Count the Number of Binary Search Trees present in a Binary Tree are: 2

説明

二分木を形成するために使用される整数値の配列が与えられ、そこに二分探索木が存在するかどうかを確認します。すべてのルートノードは二分探索木を表すため、特定の二分木には他の二分探索木が存在しないことがわかります。したがって、カウントは2であり、これは二分木のリーフノードの総数です。

入力

値を入力した後に作成されるツリーを以下に示します-

出力

Count the Number of Binary Search Trees present in a Binary Tree are: 6

説明

二分木を形成するために使用される整数値の配列が与えられ、そこに二分探索木が存在するかどうかを確認します。すべてのルートノードは二分探索木を表すため、特定の二分木には、BSTを形成している4つのリーフノードと2つのサブツリーがあることがわかります。したがって、カウントは6です。

以下のプログラムで使用されるアプローチは次のとおりです-

このアプローチでは、ノードNの左側のサブツリーでノードの最大値を見つけ、それがN未満かどうかを確認します。また、ノードNの右側のサブツリーで最小値を見つけて、それがより大きいかどうかを確認します。 N. trueの場合、それはBSTです。ボトムアップ方式でバイナリツリーをトラバースし、上記の条件とBSTの増分カウントを確認します

• すべてのnode_dataのノードには、存在するBSTの数、そのツリーの最大値、最小値、そのサブツリーがBSTの場合はブール値trueなどの情報が含まれます。

• 関数BST_present（struct tree_node * parent）は、親をルートとする二分木内に存在するBSTの数を検索します。

• 親がNULLの場合、{0、min、max、true}を返します。ここで、minはINT-MIN、maxはINT_MAXです。

• 左と右の子がnullの場合、{1、parent-> data、parent-> data、true}

  を返します。

• node_data Left =BST_present（parent-> left）;を設定します。およびnode_dataRight=BST_present（parent-> right）;

• ノードn1を取得し、n1.lowest =min（parent-> data、（min（Left.lowest、Right.lowest）））を右側のサブツリーの最下位に設定します。

• n1.highest =max（parent-> data、（max（Left.highest、Right.highest）））;を設定します。左側のサブツリーで最も高い位置にあります。

• if（Left.check &&Right.check &&parent-> data> Left.highest &&parent-> data

• bstの数をn1.total_bst=1 + Left.total_bst + Right.total_bst;

  として増やします。

• それ以外の場合は、n1.check =falseに設定し、n1.total_bst =Left.total_bst+Right.total_bstとしてカウントします。

• 最後にn1を返します。

例

#include <bits/stdc++.h>
using namespace std;
struct tree_node{
   struct tree_node* left;
   struct tree_node* right;
   int data;
   tree_node(int data){
      this−>data = data;
      this−>left = NULL;
      this−>right = NULL;
   }
};
struct node_data{
   int total_bst;
   int highest, lowest;
   bool check;
};
node_data BST_present(struct tree_node* parent){
   if(parent == NULL){
      int max = INT_MAX;
      int min = INT_MIN;
      return { 0, min, max, true };
   }
   if(parent−>left == NULL){
      if(parent−>right == NULL){
         return { 1, parent−>data, parent−>data, true };
      }
   }
   node_data Left = BST_present(parent−>left);
   node_data Right = BST_present(parent−>right);
   node_data n1;
   n1.lowest = min(parent−>data, (min(Left.lowest, Right.lowest)));
   n1.highest = max(parent−>data, (max(Left.highest, Right.highest)));
   if(Left.check && Right.check && parent−>data > Left.highest && parent−>data < Right.lowest){
      n1.check = true;
      n1.total_bst = 1 + Left.total_bst + Right.total_bst;
   } else{
      n1.check = false;
      n1.total_bst = Left.total_bst + Right.total_bst;
   }
   return n1;
}
int main(){
   struct tree_node* root = new tree_node(3);
   root−>left = new tree_node(7);
   root−>right = new tree_node(4);
   root−>left−>left = new tree_node(5);
   root−>right−>right = new tree_node(1);
   root−>left−>left−>left = new tree_node(10);
   cout<<"Count the Number of Binary Search Trees present in a Binary Tree are: "<<BST_present(root).total_bst;
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count the Number of Binary Search Trees present in a Binary Tree are: 2