พิมพ์คีย์ BST ในช่วงที่กำหนดใน C++

ในปัญหานี้ เราจะได้รับสองโหนดของแผนผังการค้นหาแบบไบนารี และเราต้องพิมพ์ค่าทั้งหมดในช่วง 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.