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의 order traversal을 사용할 것입니다. 이제 이 문제를 풀기 위한 알고리즘을 만들어 봅시다.

알고리즘

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.