在二元樹中，每個子節點只有兩個節點（左和右）。樹結構只是資料的表示。二元搜尋樹（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。
#includeusing 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中文網其他相關文章！
