数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中统计位于给定范围内的BST子树
给定一个二叉搜索树作为输入。目标是找到BST中节点值介于起始值和结束值之间的子树数量。如果起始值为5，结束值为50，则统计BST中所有节点权重大于等于5且小于等于50的子树。
输入 - 下面的树 - 范围 [3-6]
输出 - 位于范围内的树的数量 - 2
解释 - 只有节点4和6。它们的子树（NULL）位于3-6之间。
输入 - 下面的树：范围 [12-20]
输出 - 位于范围内的树的数量 - 3
解释 - 对于节点16、14和20。它们的子树位于12-20之间。
下面程序中使用的方法如下
结构体Btreenode用于创建一个树的节点，其信息部分为整数，自引用左指针和右指针指向子树。
函数Btreenode* insert(int data) 用于创建一个数据为信息且左右指针为NULL的节点。
通过对给定结构调用插入函数来创建BST。将节点添加到根节点的右边 (root->right = insert(70);) 和根节点的左边 (root->left = insert(30);)。
变量l和h用于存储范围的最小值和最大值。
变量count存储树内位于l和h范围内的BST的数量。初始值为0。
函数getBtreeCount(Btreenode* root, int low, int high, int* count) 获取BST的根、范围的左右边界和count的地址作为参数，并在每次递归调用时更新count的值。
对于当前根节点，检查它是否为NULL，如果是，则返回1，因为它不是树的一部分。
对于当前节点，检查其所有左子树和右子树节点是否位于给定范围内。通过递归调用getBtreeCount(root->left, low, high, count); 和 getBtreeCount(root->right, low, high, count);
如果两个子树都位于范围内，并且当前节点也位于范围内，则当前节点为根的树位于范围内。递增count。if (left && right && root->info >= low && root->info <= high) and ++*count; return 1.
最后，count将具有更新后的值，作为所有子树的数量。
- 打印count中的结果。
示例
#include <bits/stdc++.h>
using namespace std;
// A BST node
struct Btreenode {
int info;
Btreenode *left, *right;
};
int getBtreeCount(Btreenode* root, int low, int high, int* count){
// Base case
if (root == NULL)
return 1;
int left = getBtreeCount(root->left, low, high, count);
int right = getBtreeCount(root->right, low, high, count);
if (left && right && root->info >= low && root->info <= high) {
++*count;
return 1;
}
return 0;
}
Btreenode* insert(int data){
Btreenode* temp = new Btreenode;
temp->info = data;
temp->left = temp->right = NULL;
return (temp);
}
int main(){
/* BST for input
50
/ \
30 70
/ \ / \
20 40 60 80 */
Btreenode* root = insert(50);
root->left = insert(30);
root->right = insert(70);
root->left->left = insert(20);
root->left->right= insert(40);
root->right->left = insert(60);
root->right->right = insert(80);
int l = 10;
int h = 50;
int count=0;
getBtreeCount(root, l, h, &count);
cout << "Count of subtrees lying in range: " <<count;
return 0;
}输出
Count of subtrees lying in range: 3
194 次浏览
