数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中计算落在给定范围内的BST节点数
给定一个由节点组成的二叉搜索树和一个范围，任务是计算落在给定范围内的节点数并显示结果。
二叉搜索树 (BST) 是一种树，其中所有节点都遵循以下属性：
节点的左子树中的键小于或等于其父节点的键。
节点的右子树中的键大于其父节点的键。
因此，BST 将其所有子树划分为两个部分：左子树和右子树，可以定义为：
左子树(键) ≤ 节点(键) ≤ 右子树(键)
例如
输入：
范围：[11, 40]
输出：计数为：5
解释：在给定的二叉搜索树中，范围[11, 40]之间的节点值为14、19、27、31和35，因此共有5个节点。
下面程序中使用的方法如下：
创建一个节点结构，包含数据、左指针、右指针，并创建一个范围。
创建一个函数来插入用户将输入的新节点。
创建另一个函数来计算落在给定范围内的节点数。
检查根是否为NULL，如果是，则返回。
现在，检查如果root->data = Start 且 root->data = End，则返回1。
现在，检查如果root->data <= high && root->data >= low，则返回1 + getCount(root->left, End, Start) + 递归调用计数函数(root->right, End, Start)
否则如果，root->data < End，则返回递归调用计数函数(root->right, End, Start)
否则，返回递归调用计数函数(root->left, End, Start)
示例
#include<iostream>
using namespace std;
// A BST node
struct node{
int data;
struct node* left, *right;
};
// Utility function to create new node
node *newNode(int data){
node *temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
int findcount(node *root, int low, int high){
// Base case
if (!root){
return 0;
}
if (root->data == high && root->data == low){
return 1;
}
// If current node is in range, then include it in count and
// recur for left and right children of it
if (root->data <= high && root->data >= low){
return 1 + findcount(root->left, low, high) +
findcount(root->right, low, high);
}
else if (root->data < low){
return findcount(root->right, low, high);
}
// Else recur for left child
else{
return findcount(root->left, low, high);
}
}
// main function
int main(){
// Let us construct the BST shown in the above figure
node *root = newNode(27);
root->left = newNode(14);
root->right = newNode(35);
root->left->left = newNode(10);
root->left->right = newNode(19);
root->right->left = newNode(31);
root->right->right = newNode(42);
int low = 10;
int high = 50;
cout << "Count of nodes between [" << low << ", " << high
<< "] is " << findcount(root, low, high);
return 0;
}输出
如果运行以上代码，我们将得到以下输出：
Count of nodes between [10, 50] is 7
更新于：2020年5月15日
204 次查看
广告