Đếm cây con BST nằm trong phạm vi cho trước trong C++

Chúng ta được cho một cây tìm kiếm nhị phân (BST) làm đầu vào. Mục tiêu là tìm số lượng cây con trong BST có giá trị nút nằm trong phạm vi từ start đến end. Nếu start là 5 và end là 50. Thì đếm các cây con trong BST mà tất cả các nút có trọng số >= 5 và <= 50.

Ví dụ

Đầu vào − cây cho dưới đây − phạm vi [3-6]

Đầu ra − Số cây nằm trong phạm vi − 2

Giải thích − Với nút 4 và 6. Cây con của chúng (NULL) nằm giữa 3-6.

Đầu vào − cây cho dưới đây: phạm vi [12-20]

Đầu ra − Số cây nằm trong phạm vi − 3

Giải thích − Với nút 16, 14 và 20. Cây con của chúng nằm giữa 12-20.

Phương pháp sử dụng trong chương trình dưới đây

• Cấu trúc Btreenode dùng để tạo nút của cây, với phần info là số nguyên và con trỏ trái, phải tham chiếu đến cây con.
• Hàm Btreenode* insert(int data) tạo nút với data là info và con trỏ trái, phải là NULL.
• Tạo BST bằng hàm insert bằng cách gọi nó cho cấu trúc đã cho. Thêm nút bên phải gốc (root->right = insert(70);) và bên trái gốc (root->left = insert(30);).
• Biến l và h lưu giá trị tối thiểu và tối đa của một phạm vi.
• Biến count lưu số lượng BST bên trong cây nằm trong phạm vi giữa l và h. Khởi tạo 0.
• Hàm getBtreeCount(Btreenode* root, int low, int high, int* count) nhận gốc BST, giới hạn trái, phải của phạm vi và địa chỉ count làm tham số và cập nhật giá trị count cho mỗi lời gọi đệ quy.
• Với gốc hiện tại kiểm tra nếu là NULL, nếu đúng trả về 1 vì nó không phải phần tử của cây.
• Với nút hiện tại, kiểm tra tất cả nút cây con trái và phải của nó có nằm trong phạm vi cho trước không. Bằng lời gọi đệ quy getBtreeCount(root->left, low, high, count); và getBtreeCount(root->right, low, high, count);
• Nếu cả hai cây con đều nằm trong phạm vi và nút hiện tại cũng nằm trong phạm vi thì cây có gốc tại nút hiện tại nằm trong phạm vi. Tăng count. if (left && right && root->info >= low && root->info <= high) và ++*count; return 1.
• Cuối cùng count sẽ có giá trị cập nhật là số lượng tất cả cây con.
• In kết quả trong count.

Ví dụ mã nguồn

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

// Nút BST
struct Btreenode { 
    int info; 
    Btreenode *left, *right; 
}; 

int getBtreeCount(Btreenode* root, int low, int high, int* count) { 
    // Trường hợp cơ sở
    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 cho đầu vào
          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 << "Số cây con nằm trong phạm vi: " << count; 
    return 0; 
}

Kết quả

Số cây con nằm trong phạm vi: 3