Xây dựng BST từ thứ tự duyệt level order trong C++

Cho duyệt level order (cấp độ) của BST. Xây dựng lại cây. Ví dụ: [7, 4, 12, 3, 6, 8, 1, 5, 10].

Thuật toán

1. Phần tử đầu tiên = gốc
2. Phần tử tiếp theo: nếu < gốc → chèn trái, ngược lại → chèn phải
3. Đệ quy chèn cho tất cả phần tử

Chương trình C++

#include <iostream> 
using namespace std; 

class Node {
public:
    int data;
    Node *left, *right;
};

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

Node* lvlOrd(Node *root, int data) {
    if (root == NULL) {
        root = getNode(data);
        return root;
    }
    if (data <= root->data)
        root->left = lvlOrd(root->left, data);
    else
        root->right = lvlOrd(root->right, data);
    return root;
}

Node* makeTree(int arr[], int n) {
    if (n == 0) return NULL;
    Node *root = NULL;
    for (int i = 0; i < n; i++)
        root = lvlOrd(root, arr[i]);
    return root;
}

void inord(Node* root) {
    if (!root) return;
    inord(root->left);
    cout << root->data << " ";
    inord(root->right);
}

int main() {
    int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    Node *root = makeTree(arr, n);
    cout << "Inorder Traversal: ";
    inord(root);
}

Kết quả

Inorder Traversal: 1 3 4 5 6 7 8 10 12

Lưu ý

Đây là chèn lần lượt theo level order. Độ phức tạp O(n²) worst case (cây lệch). Có thuật toán O(n) dùng queue giữ khoảng giá trị hợp lệ cho mỗi nút.