資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告