Đếm số cây tìm kiếm nhị phân trong cây nhị phân C++

Cho một cây nhị phân, đếm số cây con là BST (cây tìm kiếm nhị phân). BST thỏa mãn: nút trái < gốc < nút phải.

Ý tưởng

• Duyệt bottom-up, tại mỗi nút kiểm tra: max cây con trái < giá trị nút < min cây con phải.
• Mỗi nút trả về cấu trúc chứa: số BST trong cây con, giá trị min, max, và cờ check cho biết cây con đó có phải BST không.
• Nếu là BST thì cộng 1 vào tổng, ngược chỉ cộng tổng của hai cây con.

Ví dụ hoàn chỉnh

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

struct tree_node {
    struct tree_node* left;
    struct tree_node* right;
    int data;
    tree_node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

struct node_data {
    int total_bst;
    int highest, lowest;
    bool check;
};

node_data BST_present(struct tree_node* parent) {
    if (parent == NULL) {
        int max = INT_MAX;
        int min = INT_MIN;
        return { 0, min, max, true };
    }
    if (parent->left == NULL && parent->right == NULL) {
        return { 1, parent->data, parent->data, true };
    }
    node_data Left = BST_present(parent->left);
    node_data Right = BST_present(parent->right);
    node_data n1;
    n1.lowest = min(parent->data, min(Left.lowest, Right.lowest));
    n1.highest = max(parent->data, max(Left.highest, Right.highest));
    if (Left.check && Right.check && parent->data > Left.highest && parent->data < Right.lowest) {
        n1.check = true;
        n1.total_bst = 1 + Left.total_bst + Right.total_bst;
    } else {
        n1.check = false;
        n1.total_bst = Left.total_bst + Right.total_bst;
    }
    return n1;
}

int main() {
    struct tree_node* root = new tree_node(3);
    root->left = new tree_node(7);
    root->right = new tree_node(4);
    root->left->left = new tree_node(5);
    root->right->right = new tree_node(1);
    root->left->left->left = new tree_node(10);
    cout << "Số cây BST trong cây nhị phân: " << BST_present(root).total_bst;
    return 0;
}

Kết quả

Số cây BST trong cây nhị phân: 2