Xây BST từ preorder traversal (Phương pháp 1 - Khoảng giá trị) trong C++

Cho preorder traversal của BST. Xây dựng cây. Ví dụ: [10, 5, 1, 7, 40, 50].

Thuật toán: Giới hạn khoảng giá trị (Range)

• Mỗi nút có khoảng {min...max} hợp lệ
• Khởi tạo: {INT_MIN...INT_MAX}
• Phần tử đầu trong khoảng → tạo gốc
• Cây con trái: khoảng {INT_MIN...root->data}
• Cây con phải: khoảng {root->data...INT_MAX}
• Đệ quy với chỉ số preorder toàn cục

Chương trình C++

#include <iostream> 
using namespace std; 

class node {
public:
    int data;
    node *left;
    node *right;
};

node* getNode(int data) {
    node* temp = new node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

node* makeTreeUtil(int pre[], int* preord_index, int key, int min, int max, int size) {
    if (*preord_index >= size) return NULL;
    node* root = NULL;
    if (key > min && key < max) {
        root = getNode(key);
        *preord_index += 1;
        if (*preord_index < size) {
            root->left = makeTreeUtil(pre, preord_index, pre[*preord_index], min, key, size);
            root->right = makeTreeUtil(pre, preord_index, pre[*preord_index], key, max, size);
        }
    }
    return root;
}

node* makeTree(int pre[], int size) {
    int preord_index = 0;
    return makeTreeUtil(pre, &preord_index, pre[0], INT_MIN, INT_MAX, size);
}

void inord(node* node) {
    if (node == NULL) return;
    inord(node->left);
    cout << node->data << " ";
    inord(node->right);
}

int main() {
    int pre[] = {10, 5, 1, 7, 40, 50};
    int size = sizeof(pre) / sizeof(pre[0]);
    node *root = makeTree(pre, size);
    cout << "Inorder traversal: ";
    inord(root);
}

Kết quả

Inorder traversal: 1 5 7 10 40 50

So sánh 2 phương pháp

• Phương pháp 1 (Range): Đệ quy, dễ hiểu, O(n) thời gian, O(h) stack đệ quy
• Phương pháp 2 (Stack): Lặp, O(n) thời gian, O(n) stack tường minh