数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用 C++ 打印 BST 中给定范围内的键
在这个问题中，我们给定二叉搜索树的两个节点。我们需要打印树中介于 k1 和 k2 范围内的所有值。也就是说，我们需要打印所有大于 k1 且小于 k2 的值。并且，我们需要按值的升序打印所有这些键。
**二叉搜索树**是一种满足以下 3 个属性的树：
左子树的节点值小于节点的值。
右子树的节点值大于节点的值。
子树也必须是二叉搜索树。树中不允许有重复的节点。
**示例**，
让我们举个例子来更好地理解这个主题，
Input : k1 = 12 and k2 = 25. Output : 15, 20, 24
**树** -
**解释** - 在遍历树时，将遍历所有元素，并打印位于 12 到 25 范围内的元素，即对于节点 x，12 ≤ x ≥ 25 将被打印。
在这里，我们将使用 BST 的特性来找到我们的解决方案，即左子树中的所有元素都小于根，右子树中的所有元素都大于根节点。我们将使用 BST 的中序遍历来解决这个问题。现在，让我们创建一个算法来解决这个问题。
算法
Step 1 : Compare the root node with the k1 and k2. Step 2 : If root is greater than k1. Call left subtree for the search recursively. Step 3 : If root is smaller than k2. Call right subtree for the search recursively. Step 4 : If the root of the tree is in the range. Then print the root’s value.
示例
现在，基于此算法，让我们创建一个程序来解决问题。
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node *left;
node *right;
};
void nodesInRange(node *root, int k1, int k2){
if ( NULL == root )
return;
if ( k1 < root->data )
nodesInRange(root->left, k1, k2);
if ( k1 <= root->data && k2 >= root->data )
cout<<root->data<<"\t";
if ( k2 > root->data )
nodesInRange(root->right, k1, k2);
}
node* insert(int data){
node *temp = new node();
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
int main(){
node *root = new node();
int k1 = 12, k2 = 25;
root = insert(20);
root->left = insert(10);
root->right = insert(24);
root->left->left = insert(8);
root->left->right = insert(15);
root->right->right = insert(32);
cout<<”The values of node within the range are\t”;
nodesInRange(root, k1, k2);
return 0;
}输出
The values of node within the range are 15 20 24.
更新于: 2020-01-03
583 次查看
广告