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

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

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

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

• แผนผังย่อยด้านขวาของโหนดมีคีย์ที่มากกว่าคีย์ของโหนดหลัก

ดังนั้น BST จึงแบ่งทรีย่อยทั้งหมดออกเป็นสองส่วน ทรีย่อยด้านซ้ายและแผนผังย่อยด้านขวา และสามารถกำหนดเป็น −

left_subtree (คีย์) ≤ node (คีย์) ≤ right_subtree (คีย์)

ตัวอย่าง

ป้อนข้อมูล −

ช่วง:[11, 40]

ผลผลิต − นับเป็น:5

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

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

• สร้างโครงสร้างของโหนดที่มีข้อมูล ตัวชี้ซ้าย ตัวชี้ขวา และสร้างช่วง

• สร้างฟังก์ชันเพื่อแทรกโหนดใหม่ที่ผู้ใช้จะป้อน

• สร้างฟังก์ชันอื่นเพื่อนับโหนดที่อยู่ในช่วงที่กำหนด

• ตรวจสอบว่ารูทเป็น NULL หรือไม่ จากนั้นให้ส่งคืน

• ตอนนี้ ให้ตรวจสอบ IF root->data =Start AND root->data =End แล้วคืนค่า 1

• ตอนนี้ ให้ตรวจสอบ IF root->data <=high &&root->data>=low แล้วคืนค่า 1 + getCount(root->left, End, Start) + recursively_call_count_function(root->right, End, Start)

• อื่น ถ้า root->data right, End, Start)

• มิฉะนั้น return recursively_call_count_function(root->left, End, Start)

ตัวอย่าง

#include<iostream>
using namespace std;
// A BST node
struct node{
   int data;
   struct node* left, *right;
};
// Utility function to create new node
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){
   // Base case
   if (!root){
      return 0;
   }
   if (root->data == high && root->data == low){
      return 1;
   }
   // If current node is in range, then include it in count and
   // recur for left and right children of it
   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 recur for left child
   else{
      return findcount(root->left, low, high);
   }
}
// main function
int main(){
   // Let us construct the BST shown in the above figure
   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