数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++实现二叉树中最大的二叉搜索树
在二叉树中，每个子节点只有两个节点（左节点和右节点）。树结构只是数据的简单表示。二叉搜索树 (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，并相应地返回值。
更新于：2022年3月7日
392 次浏览
广告