数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究用 C++ 统计二叉树中二叉搜索树的数量
给定一个二叉树作为输入。目标是在其中找到作为子树存在的二叉搜索树 (BST) 的数量。BST 是一棵二叉树，其左子节点小于根节点，右子节点大于根节点。
例如
输入
输入值创建后的树如下所示：
输出
Count the Number of Binary Search Trees present in a Binary Tree are: 2
解释
我们得到一个整数数组，用于形成一棵二叉树，我们将检查其中是否存在二叉搜索树。每个根节点都表示二叉搜索树，所以在给定的二叉树中，我们可以看到不存在其他二叉搜索树，因此计数为 2，这是二叉树中叶节点的总数。
输入
输入值创建后的树如下所示：
输出
Count the Number of Binary Search Trees present in a Binary Tree are: 6
解释
我们得到一个整数数组，用于形成一棵二叉树，我们将检查其中是否存在二叉搜索树。每个根节点都表示二叉搜索树，所以在给定的二叉树中，我们可以看到有 4 个叶节点和两个形成 BST 的子树，因此计数为 6。
下面程序中使用的方法如下：
在这种方法中，我们将找到节点 N 左子树中节点的最大值，并检查它是否小于 N。此外，我们还将在节点 N 的右子树中找到最小值，并检查它是否大于 N。如果为真，则它是一个 BST。自下而上遍历二叉树并检查上述条件，并递增 BST 的计数。
每个 `node_data` 节点包含的信息包括：存在的 BST 数量、该树中的最大值、最小值、如果该子树是 BST 则为 true 的布尔值。
函数 `BST_present(struct tree_node* parent)` 查找以 `parent` 为根的二叉树中存在的 BST 的数量。
如果 `parent` 为 NULL，则返回 `{0, min, max, true}`，其中 `min` 为 INT_MIN，`max` 为 INT_MAX。
如果左子节点和右子节点都为 NULL，则返回 `{1, parent->data, parent->data, true}`。
设置 `node_data Left = BST_present(parent->left);` 和 `node_data Right = BST_present(parent->right);`
取节点 n1 并设置 `n1.lowest = min(parent->data, (min(Left.lowest, Right.lowest)))` 为其右子树中的最小值。
设置 `n1.highest = max(parent->data, (max(Left.highest, Right.highest)));` 为其左子树中的最大值。
如果 `(Left.check && Right.check && parent->data > Left.highest && parent->data < Right.lowest)` 返回 true，则设置 `n1.check = true`，因为它是一个 BST。
将 BST 的计数增加为 `n1.total_bst = 1 + Left.total_bst + Right.total_bst;`
否则，设置 `n1.check = false`，并将计数设置为 `n1.total_bst = Left.total_bst + Right.total_bst;`。
最后返回 n1。
示例
#include <bits/stdc++.h>
using namespace std;
struct tree_node{
struct tree_node* left;
struct tree_node* right;
int data;
tree_node(int data){
this−>data = data;
this−>left = NULL;
this−>right = NULL;
}
};
struct node_data{
int total_bst;
int highest, lowest;
bool check;
};
node_data BST_present(struct tree_node* parent){
if(parent == NULL){
int max = INT_MAX;
int min = INT_MIN;
return { 0, min, max, true };
}
if(parent−>left == NULL){
if(parent−>right == NULL){
return { 1, parent−>data, parent−>data, true };
}
}
node_data Left = BST_present(parent−>left);
node_data Right = BST_present(parent−>right);
node_data n1;
n1.lowest = min(parent−>data, (min(Left.lowest, Right.lowest)));
n1.highest = max(parent−>data, (max(Left.highest, Right.highest)));
if(Left.check && Right.check && parent−>data > Left.highest && parent−>data < Right.lowest){
n1.check = true;
n1.total_bst = 1 + Left.total_bst + Right.total_bst;
} else{
n1.check = false;
n1.total_bst = Left.total_bst + Right.total_bst;
}
return n1;
}
int main(){
struct tree_node* root = new tree_node(3);
root−>left = new tree_node(7);
root−>right = new tree_node(4);
root−>left−>left = new tree_node(5);
root−>right−>right = new tree_node(1);
root−>left−>left−>left = new tree_node(10);
cout<<"Count the Number of Binary Search Trees present in a Binary Tree are: "<<BST_present(root).total_bst;
return 0;
}输出
如果我们运行以上代码，它将生成以下输出：
Count the Number of Binary Search Trees present in a Binary Tree are: 2
1K+ 次浏览
