In các khóa BST trong phạm vi đã cho bằng C ++

Trong bài toán này, chúng ta có hai nút của cây tìm kiếm nhị phân. Và chúng ta phải in tất cả các giá trị trong khoảng từ k1 đến k2 xảy ra trong cây. Đó là chúng ta phải in tất cả các giá trị lớn hơn k1 và nhỏ hơn k2. Và chúng tôi phải in tất cả các khóa này theo thứ tự tăng dần các giá trị của chúng.

Cây tìm kiếm nhị phân là một cây tuân theo 3 thuộc tính sau -

• Cây con bên trái có các nút có giá trị nhỏ hơn giá trị của nút.

• Cây con bên phải có một nút có giá trị lớn hơn giá trị của nút.

• Cây con được lấy cũng phải là cây tìm kiếm nhị phân. Không cho phép các nút trùng lặp trong cây.

Ví dụ ,

Hãy lấy một ví dụ để hiểu rõ hơn về chủ đề này,

Input : k1 = 12 and k2 = 25.
Output : 15, 20, 24

Cây -

Giải thích - Khi duyệt cây, tất cả các phần tử sẽ được duyệt và các phần tử nằm trong khoảng từ 12 đến 25, tức là đối với nút x, 12 ≤ x ≥ 25 sẽ được in.

Ở đây, chúng tôi sẽ sử dụng các tính chất của BST để tìm lời giải của chúng tôi. tức là tất cả các phần tử trong cây con bên trái đều nhỏ hơn gốc và tất cả các phần tử trong cây con bên phải đều lớn hơn nút gốc. Và chúng tôi sẽ sử dụng theo thứ tự của BST để giải quyết vấn đề này. Bây giờ, hãy tạo một thuật toán để giải quyết vấn đề này.

THUẬT TOÁN

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.

Ví dụ

Bây giờ, dựa trên thuật toán này, hãy tạo một chương trình để giải quyết vấn đề.

#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;
}

Đầu ra

The values of node within the range are 15 20 24.