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

เราได้รับ binary search tree ที่ประกอบด้วยโหนด และช่วง (range) งานคือคำนวณจำนวนโหนดที่อยู่ในช่วงที่กำหนดและแสดงผลลัพธ์

Binary Search Tree (BST) เป็นต้นไม้ที่โหนดทั้งหมดปฏิบัติตามคุณสมบัติด้านล่าง –

• ซับทรีด้านซ้ายของโหนดมีคีย์น้อยกว่าหรือเท่ากับคีย์ของโหนดพาเรนต์
• ซับทรีด้านขวาของโหนดมีคีย์มากกว่าคีย์ของโหนดพาเรนต์

ดังนั้น BST แบ่งซับทรีทั้งหมดเป็นสองส่วน: ซับทรีซ้ายและซับทรีขวา และสามารถนิยามได้ว่า –

left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

ตัวอย่าง

อินพุต –

Range: [11, 40]

เอาต์พุต – count is: 5

คำอธิบาย – ค่าโหนดระหว่างช่วง [11, 40] คือ 14, 19, 27, 31 และ 35 รวม 5 โหนดใน BST ที่กำหนด

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

• สร้างโครงสร้างโหนดที่มีข้อมูล, พอยน์เตอร์ซ้าย, ขวา และสร้างช่วง
• สร้างฟังก์ชันแทรกโหนดใหม่ที่ผู้ใช้ป้อน
• สร้างฟังก์ชันอีกตัวนับโหนดที่อยู่ในช่วงที่กำหนด
• ตรวจสอบ IF root เป็น NULL แล้วคืนค่า
• ตรวจสอบ IF root->data == Start AND root->data == End คืนค่า 1
• ตรวจสอบ IF root->data <= high && root->data >= low คืนค่า 1 + getCount(root->left, End, Start) + เรียกซ้ำ(root->right, End, Start)
• Else If root->data < End คืนค่า เรียกซ้ำ(root->right, End, Start)
• Else คืนค่า เรียกซ้ำ(root->left, End, Start)

ตัวอย่าง

#include <iostream>
using namespace std;

struct node{
    int data;
    struct node* left, *right;
};

node *newNode(int data){
    node *temp = new node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return (temp);
}

int findcount(node *root, int low, int high){
    if (!root){
        return 0;
    }
    if (root->data == high && root->data == low){
        return 1;
    }
    if (root->data <= high && root->data >= low){
        return 1 + findcount(root->left, low, high) + findcount(root->right, low, high);
    }
    else if (root->data < low){
        return findcount(root->right, low, high);
    }
    else{
        return findcount(root->left, low, high);
    }
}

int main(){
    node *root = newNode(27);
    root->left = newNode(14);
    root->right = newNode(35);
    root->left->left = newNode(10);
    root->left->right = newNode(19);
    root->right->left = newNode(31);
    root->right->right = newNode(42);
    int low = 10;
    int high = 50;
    cout << "Count of nodes between [" << low << ", " << high << "] is " << findcount(root, low, high);
    return 0;
}

เอาต์พุต

Count of nodes between [10, 50] is 7