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

เราได้รับ Binary Search Tree (BST) เป็นอินพุต เป้าหมายคือหาจำนวน subtree ใน BST ที่มีค่าโหนดอยู่ในช่วง start ถึง end หาก start=5 และ end=50 ให้นับ subtree ที่โหนดทุกตัวมีค่า >=5 และ <=50

อินพุต − ต้นไม้ที่กำหนด − ช่วง [3-6]

เอาต์พุต − Count of tree lying in range − 2

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

อินพุต − ต้นไม้ที่กำหนด: ช่วง [12-20]

เอาต์พุต − Count of tree lying in range − 3

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

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

• โครงสร้าง Btreenode สร้างโหนดต้นไม้ มี info เป็นจำนวนเต็ม และ pointer left, right อ้างอิง subtree
• ฟังก์ชัน Btreenode* insert(int data) สร้างโหนดข้อมูล data และ left, right = NULL
• สร้าง BST ด้วย insert เรียกซ้ำเพื่อเพิ่มโหนดทางขวา (root->right = insert(70)) และซ้าย (root->left = insert(30))
• ตัวแปร l และ h เก็บค่าต่ำสุดและสูงสุดของช่วง
• ตัวแปร count นับ BST ภายในต้นไม้ที่อยู่ในช่วง l ถึง h เริ่มต้น 0
• ฟังก์ชัน getBtreeCount(Btreenode* root, int low, int high, int* count) รับ root ของ BST, ขอบเขตช่วง, ที่อยู่ของ count อัปเดต count ในแต่ละครั้งที่เรียกซ้ำ
• ตรวจสอบ root เป็น NULL คืน 1 (ไม่ใช่ส่วนของต้นไม้)
• ตรวจสอบโหนดปัจจุบัน: เรียกซ้ำ getBtreeCount สำหรับ left และ right subtree
• ถ้าทั้งสอง subtree อยู่ในช่วง และโหนดปัจจุบันอยู่ในช่วง (root->info >= low && root->info <= high) ให้ ++*count และคืน 1
• สุดท้าย count จะมีค่าที่อัปเดตแล้วเป็นจำนวน subtree ทั้งหมด
• พิมพ์ผลลัพธ์ใน count

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

struct Btreenode {
    int info;
    Btreenode *left, *right;
};

int getBtreeCount(Btreenode* root, int low, int high, int* count) {
    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 สำหรับอินพุต
            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