C++ でバイナリ ツリー内の最大の BST を変換する

バイナリ ツリーでは、各子ノードには 2 つのノード (左と右) しかありません。ツリー構造はデータを表現したものにすぎません。二分探索ツリー (BST) は、次の条件を満たす特別なタイプの二分木です -

• 左の子ノードは親ノードに比べて小さいです

• 右側の子ノードの親ノードが子ノードより大きい

与えられた二分木があると仮定すると、最大の二分探索木 (BST) を見つける必要があります。

このタスクでは、バイナリ ツリー内で最大の BST を見つける関数を作成します。二分木そのものがBSTである場合には、二分木全体のサイズを求めることができる。例:

Enter

  10
  /\
 5  15
 /\  \
1  8  7

図に示すように、この例では強調表示されている BST サブツリーが最大です。 「3」はサブツリーのサイズなので、戻り値はサブツリーのサイズになります。

入力

    52
    / \
   37 67
   /\ / \
 12 27 57 77
          /\
         72 87

出力

5

ノードの長さが親ノードの長さより短いサブツリーには、 3 つの BST ノードの最大サイズ。

指定されたバイナリ ツリーで最大の BST を見つける方法

各ノード x について、次の点が有効であれば、バイナリ ツリーは BST です。親ノードのデータよりも小さいデータを持つノードのみが、ノードの左側のサブツリーに表示されます。親より多くのデータを持つことができるのは 1 つのノードだけです。左側のサブツリーと右側のサブツリーは両方とも二分探索ツリー (BST) で表す必要があります。

アルゴリズムは次のとおりです -

バイナリ ツリーからの順序トラバーサルを再帰を使用して実行します。現在のノード「ROOT」については、次の処理を実行します。 -

• それが有効な BST のルートである場合は、そのサイズを返します。

• それ以外の場合は、左右のサブツリーで最大の BST が見つかります。

例

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left;
   struct Node *right;
};
struct Node *
newNode (int data) {
   struct Node *node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
struct Detail {
   int size;
   int max;
   int min;
   int ans;
   bool isBST;
};
bool isBST (Node * root, int min, int max) {
   if (root == NULL) {
      return true;
   }
   if (root->data < min || root->data > max) {
      return false;
   }
   return isBST (root->left, min, root->data - 1) &&
   isBST (root->right, root->data + 1, max);
}
int size (Node * root) {
   if (root == NULL) {
      return 0;
   }
   return 1 + size (root->left) + size (root->right);
}
int largestBST (Node * root) {
   // Current Subtree is BST.
   if (isBST (root, INT_MIN, INT_MAX) == true) {
      return size (root);
   }
   // Find largest BST in left and right subtrees.
   return max (largestBST (root->left), largestBST (root->right));
}
int main () {
   struct Node *root = newNode (67);
   root->left = newNode (72);
   root->right = newNode (77); root->left->left = newNode (57);
   printf ("Size of the largest BST is %d", largestBST (root));
   return 0;
}

出力

Size of the largest BST is 2

結論

この質問では、二分木と二分探索木とは何かを学びました。また、再帰を利用して特定のバイナリ ツリー内で最大の BST を見つける方法も説明します。再帰の助けを借りて、各ノードの下のサブツリーが BST であるかどうかを調べ、対応する値を返します。

以上がC++ でバイナリ ツリー内の最大の BST を変換するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。