Chúng tôi được cung cấp một cây tìm kiếm nhị phân làm đầu vào. Mục đích là để tìm số lượng cây con trong BST mà có giá trị nút ở giữa phạm vi bắt đầu và kết thúc. Nếu bắt đầu là 5 và kết thúc là 50. Các cây con của tài khoản trong BST có tất cả các nút có trọng số> =5 và <=50.
Đầu vào - cây cho bên dưới - phạm vi [3-6]
Đầu ra - Số cây nằm trong phạm vi - 2
Giải thích - Chỉ dành cho các nút 4 và 6. Các cây con (NULL) của chúng nằm trong khoảng từ 3 đến 6.
Đầu vào - cây được đưa ra bên dưới:range [12-20]
Đầu ra - Số cây nằm trong phạm vi - 3
Giải thích - Đối với các nút 16, 14 và 20. Các cây con của chúng nằm giữa 12-20.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Cấu trúc Btreenode được sử dụng để tạo một nút của cây, với phần thông tin là số nguyên và các con trỏ trái và phải tự tham chiếu để trỏ đến các cây con.
-
Hàm Btreenode * insert (int data) được sử dụng để tạo một nút với dữ liệu là thông tin và con trỏ trái và phải là NULL.
-
Tạo một BST bằng cách sử dụng chức năng chèn bằng cách gọi nó cho một cấu trúc nhất định. Để thêm các nút vào bên phải nút gốc (root-> right =insert (70);) và vào bên trái của root (root-> left =insert (30);).
-
Các biến l và h được sử dụng để lưu trữ giá trị nhỏ nhất và lớn nhất của một dải ô.
-
Số lượng biến lưu trữ số lượng BST bên trong cây nằm trong khoảng giữa l vàh. Ban đầu là 0.
-
Hàm getBtreeCount (Btreenode * root, int low, int high, int * count) lấy gốc của BST, ranh giới bên trái và bên phải của phạm vi và địa chỉ của số đếm làm tham số và cập nhật giá trị của số lượng cho mỗi lần gọi đệ quy.
-
Để kiểm tra gốc hiện tại nếu nó là NULL, nếu có trả về 1 vì nó không phải là một phần của cây.
-
Đối với các nút hiện tại, hãy kiểm tra tất cả các nút cây con bên trái và bên phải của nó xem chúng có nằm trong phạm vi đã cho hay không. Bằng cách gọi đệ quy getBtreeCount (root-> left, low, high, count); andgetBtreeCount (root-> right, low, high, count);
-
Nếu cả hai cây con nằm giữa phạm vi và nút hiện tại cũng nằm trong phạm vi thì cây gốc tại nút hiện tại nằm trong phạm vi. Số lượng tăng dần. if (left &&right &&root-> info> =low &&root-> info <=high) và ++ * count; trả về 1.
-
Ở cuối số đếm sẽ có giá trị được cập nhật là tổng số của tất cả các cây con.
- In kết quả dưới dạng số đếm.
Ví dụ
#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;
} Đầu ra
Count of subtrees lying in range: 3