นับทรีย่อย BST ที่อยู่ในช่วงที่กำหนดใน C++

เราได้รับต้นไม้การค้นหาไบนารีเป็นอินพุต เป้าหมายคือการค้นหาจำนวนทรีย่อยใน BST ซึ่งมีค่าโหนดอยู่ระหว่างช่วงเริ่มต้นและสิ้นสุด หากเริ่มต้นคือ 5 และสิ้นสุดคือ 50 จากนั้นนับทรีย่อยใน BST ที่โหนดทั้งหมดมีน้ำหนัก>=5 และ <=50

ป้อนข้อมูล − ต้นไม้ที่ระบุด้านล่าง − ช่วง [ 3-6 ]

ผลผลิต − จำนวนต้นไม้ที่อยู่ในระยะ − 2

คำอธิบาย - สำหรับโหนด 4 และ 6 เท่านั้น แผนผังย่อย ( NULL ) อยู่ระหว่าง 3-6

ป้อนข้อมูล − ต้นไม้ที่ระบุด้านล่าง:ช่วง [ 12-20 ]

ผลผลิต − จำนวนต้นไม้ที่อยู่ในระยะ − 3

คำอธิบาย − สำหรับโหนด 16, 14 และ 20 แผนผังย่อยอยู่ระหว่าง 12-20

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• โครงสร้าง Btreenode ใช้เพื่อสร้างโหนดของทรี โดยมีส่วนข้อมูลเป็นจำนวนเต็มและตัวชี้อ้างอิงซ้ายและขวาเพื่อชี้ไปยังทรีย่อย

• ฟังก์ชัน Btreenode* insert(int data) ใช้เพื่อสร้างโหนดที่มีข้อมูลเป็นข้อมูลและตัวชี้ซ้ายและขวาเป็น NULL

• สร้าง BST โดยใช้ฟังก์ชันแทรกโดยเรียกใช้โครงสร้างที่กำหนด วิธีเพิ่มโหนดทางขวาให้กับโหนดรูท ( root->right =insert(70); ) และทางซ้ายของรูท ( root->left =insert(30); )

• ตัวแปร l และ h ใช้เพื่อเก็บค่าต่ำสุดและสูงสุดของช่วง

• การนับตัวแปรจะเก็บการนับของ BST ภายในต้นไม้ที่อยู่ในช่วงระหว่าง l และชั่วโมง เริ่มแรก 0.

• ฟังก์ชัน getBtreeCount(รูท Btreenode*, int low, int high, int* count) รับรูทของ BST ขอบเขตด้านซ้ายและขวาของช่วงและที่อยู่ของการนับเป็นพารามิเตอร์ และอัปเดตค่าของการนับสำหรับการเรียกซ้ำแต่ละครั้ง

• สำหรับการตรวจสอบรูทปัจจุบันว่าเป็น NULL ถ้าใช่ ให้คืนค่า 1 เนื่องจากไม่ใช่ส่วนหนึ่งของทรี

• สำหรับโหนดปัจจุบัน ให้ตรวจสอบว่าโหนดทรีย่อยด้านซ้ายและขวาทั้งหมดอยู่ในช่วงที่กำหนดหรือไม่ โดยการเรียกซ้ำ getBtreeCount(root->left, low, high, count); andgetBtreeCount(root->ขวา ต่ำ สูง นับ);

• หากทรีย่อยทั้งสองอยู่ระหว่างช่วงและโหนดปัจจุบันยังอยู่ในช่วงนั้น ต้นไม้ที่รูทที่โหนดปัจจุบันจะอยู่ในช่วง นับเพิ่ม. ถ้า (left &&right &&root->info>=low &&root->info <=high) และ ++*count; กลับ 1.

• เมื่อสิ้นสุดการนับจะมีการอัปเดตค่าเป็นจำนวนทรีย่อยทั้งหมด

• พิมพ์ผลลัพธ์เป็นจำนวน

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
// A BST node
struct Btreenode {
   int info;
   Btreenode *left, *right;
};
int getBtreeCount(Btreenode* root, int low, int high, int* count){
   // Base case
   if (root == NULL)
      return 1;
      int left = getBtreeCount(root->left, low, high, count);
      int right = getBtreeCount(root->right, low, high, count);
      if (left && right && root->info >= low && root->info <= high) {
         ++*count;
      return 1;
   }
   return 0;
}
Btreenode* insert(int data){
   Btreenode* temp = new Btreenode;
   temp->info = data;
   temp->left = temp->right = NULL;
   return (temp);
}
int main(){
      /* BST for input
         50
        / \
       30 70
      / \ / \
20 40 60 80 */
   Btreenode* root = insert(50);
   root->left = insert(30);
   root->right = insert(70);
   root->left->left = insert(20);
   root->left->right= insert(40);
   root->right->left = insert(60);
   root->right->right = insert(80);
   int l = 10;
   int h = 50;
   int count=0;
   getBtreeCount(root, l, h, &count);
   cout << "Count of subtrees lying in range: " <<count;
   return 0;
}

ผลลัพธ์

Count of subtrees lying in range: 3