在C++中，將二元樹中的最大二元搜尋樹（Largest BST in a Binary Tree）進行翻譯

在二元樹中，每個子節點只有兩個節點（左和右）。樹結構只是資料的表示。二元搜尋樹（BST）是滿足這些條件的特殊類型的二元樹-

• 與與其父節點相比，左子節點較小

• 右子節點的父節點比子節點大

假設給定一棵二元樹，我們有應該找出其中最大的二元搜尋樹(BST)。

在此任務中，我們將建立一個函數來尋找二元樹中最大的 BST。當二元樹本身是BST時，就可以確定整個二元樹的大小。舉個例子 -

輸入

  10
  /\
 5  15
 /\  \
1  8  7

如圖所示，在本例中突出顯示的 BST 子樹是最大的。 '3' 是子樹的大小，因此傳回值是子樹的大小。

輸入

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

輸出

#

5

節點長度小於其父節點長度的子樹最多具有三個大小的BST 節點。

尋找給定二元樹中最大 BST 的方法

對於每個節點 x，如果下列點有效，則二元樹是 BST。只有資料小於其父節點資料的節點才會出現在節點的左子樹。只能有一個節點比其父節點擁有更多資料。左子樹和右子樹都應該用二元搜尋樹（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++中，將二元樹中的最大二元搜尋樹（Largest BST in a Binary Tree）進行翻譯的詳細內容。更多資訊請關注PHP中文網其他相關文章！