在二叉树中，每个子节点只有两个节点（左和右）。树结构只是数据的表示。二叉搜索树（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）进行翻译的详细内容。