Đếm số nút BST nằm trong một phạm vi nhất định trong C ++

Chúng ta được cung cấp một cây tìm kiếm nhị phân bao gồm các nút và cả một dải ô và nhiệm vụ là tính số nút nằm trong dải ô đã cho và hiển thị kết quả.

Cây tìm kiếm nhị phân (BST) là cây trong đó tất cả các nút tuân theo các thuộc tính được đề cập bên dưới -

• Cây con bên trái của một nút có khóa nhỏ hơn hoặc bằng khóa của nút cha của nó.

• Cây con bên phải của một nút có khóa lớn hơn khóa của nút cha của nó.

Như vậy, BST chia tất cả các cây con của nó thành hai phân đoạn; cây con bên trái và cây con bên phải và có thể được định nghĩa là -

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

Ví dụ

Đầu vào -

Phạm vi:[11, 40]

Đầu ra - số đếm là:5

Giải thích - Các giá trị nút giữa phạm vi [11, 40] là 14, 19, 27, 31 và 35 nên có tổng cộng 5 nút trong một cây tìm kiếm nhị phân nhất định.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Tạo cấu trúc của một nút chứa dữ liệu, con trỏ trái, con trỏ phải và tạo một phạm vi

• Tạo một hàm để chèn một mã mới mà người dùng sẽ nhập.

• Tạo một hàm khác để đếm các nút nằm trong một phạm vi nhất định.

• Kiểm tra NẾU gốc là NULL rồi trả về

• Bây giờ, hãy kiểm tra IF root-> data =Start AND root-> data =End rồi trả về 1.

• Bây giờ, hãy kiểm tra IF root-> data <=high &&root-> data> =low, sau đó trả về 1 + getCount (root-> left, End, Start) + recursently_call_count_ Chức năng (root-> right, End, Start)

• Khác Nếu, root-> data right, End, Start)

• Khác, trả về recursently_call_count_ Chức năng (root-> left, End, Start)

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -

Count of nodes between [10, 50] is 7