Việc xây dựng lại cây nhị phân từ các dãy duyệt là bài toán kinh điển trong cấu trúc dữ liệu. Nguyên lý chung là sử dụng kỹ thuật chia để trị: tìm nút gốc của cây con hiện tại từ dãy thứ tự phù hợp (dãy tiền tự hoặc hậu tự), sau đó xác định vị trí của nút gốc trong dãy trung tự để phân chia thành hai cây con trái và phải.

1. Xây dựng từ dãy Tiền tự và Trung tự

Trong phương pháp này, nút đầu tiên của dãy tiền tự chính là nút gốc. Tìm vị trí của nút này trong dãy trung tự để xác định độ dài cây con trái (k) và cây con phải (n-k-1). Đệ quy tiếp tục trên các đoạn tương ứng.

// pre: con trỏ đến đoạn dãy tiền tự, in: con trỏ đến đoạn dãy trung tự, n: độ dài đoạn
Node* buildPreIn(char *pre, char *in, int n) {
    Node *root; char *p; int leftLen;
    if (n <= 0) return NULL;
    
    root = new Node();
    root->val = *pre;  // nút gốc

    // tìm vị trí nút gốc trong dãy trung tự
    for (p = in; p < in + n; p++)
        if (*p == *pre) break;
    
    leftLen = p - in;
    root->left = buildPreIn(pre + 1, in, leftLen);
    root->right = buildPreIn(pre + leftLen + 1, in + leftLen + 1, n - leftLen - 1);
    return root;
}

2. Xây dựng từ dãy Hậu tự và Trung tự

Ngược lại với tiền tự, nút gốc nằm ở cuối dãy hậu tự (vị trí n-1). Tìm nút này trong dãy trung tự để phân chia cây con.

Node* buildPostIn(char *post, char *in, int n) {
    Node *root; char rootVal, *p; int leftLen;
    if (n <= 0) return NULL;
    
    root = new Node();
    rootVal = *(post + n - 1);  // nút gốc là phần tử cuối hậu tự
    root->val = rootVal;

    for (p = in; p < in + n; p++)
        if (*p == rootVal) break;
    
    leftLen = p - in;
    root->left = buildPostIn(post, in, leftLen);
    root->right = buildPostIn(post + leftLen, in + leftLen + 1, n - leftLen - 1);
    return root;
}

3. Xây dựng từ dãy Tiền tự và Hậu tự

Trường hợp này phức tạp hơn vì không có thông tin trung tự để phân định rõ ràng. Cách tiếp cận: nút gốc là phần tử đầu tiên của dãy tiền tự. Sau đó, phần tử thứ hai của dãy tiền tự chính là nút gốc của cây con trái (nếu tồn tại). Tìm phần tử này trong dãy hậu tự để xác định ranh giới của cây con trái.

Lưu ý: khi cây con chỉ có một nút (n==1), không thể tìm được pre+1 nên cần xử lý riêng.

Node* buildPrePost(char *pre, char *post, int n) {
    Node *root; char *p; int leftLen;
    if (n <= 0) return NULL;
    
    root = new Node();
    root->val = *pre;
    
    if (n == 1) return root;  // chỉ một nút, không cần tìm
    
    // phần tử thứ hai của tiền tự là gốc cây con trái
    for (p = post; p < post + n; p++)
        if (*p == *(pre + 1)) break;
    
    leftLen = p - post + 1;  // +1 vì bao gồm cả nút gốc con trái
    root->left = buildPrePost(pre + 1, post, leftLen);
    root->right = buildPrePost(pre + leftLen + 1, post + leftLen, n - leftLen - 1);
    return root;
}

Ví dụ tổng hợp

Chương trình dưới đây đọc vào một dãy số nguyên, sau đó xây dựng cây nhị phân từ các dãy duyệt và in ra kết quả duyệt theo chiều rộng (level-order). Ba bộ dữ liệu mẫu cho ba trường hợp được cung cấp trong comment.

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

const int MAX = 1003;

struct Node {
    char val;
    Node *left, *right;
};

Node* buildPreIn(char *pre, char *in, int n) {
    Node *r; char *p; int k;
    if (n <= 0) return NULL;
    r = new Node();
    r->val = *pre;
    for (p = in; p < in + n; p++)
        if (*p == *pre) break;
    k = p - in;
    r->left = buildPreIn(pre + 1, in, k);
    r->right = buildPreIn(pre + k + 1, in + k + 1, n - k - 1);
    return r;
}

Node* buildPostIn(char *post, char *in, int n) {
    Node *r; char c, *p; int k;
    if (n <= 0) return NULL;
    r = new Node();
    c = *(post + n - 1);
    r->val = c;
    for (p = in; p < in + n; p++)
        if (*p == c) break;
    k = p - in;
    r->left = buildPostIn(post, in, k);
    r->right = buildPostIn(post + k, in + k + 1, n - k - 1);
    return r;
}

Node* buildPrePost(char *pre, char *post, int n) {
    Node *r; char *p; int k;
    if (n <= 0) return NULL;
    r = new Node();
    r->val = *pre;
    if (n == 1) return r;
    for (p = post; p < post + n; p++)
        if (*p == *(pre + 1)) break;
    k = p - post + 1;
    r->left = buildPrePost(pre + 1, post, k);
    r->right = buildPrePost(pre + k + 1, post + k, n - k - 1);
    return r;
}

void levelOrder(Node *root) {
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node *cur = q.front(); q.pop();
        cout << cur->val << " ";
        if (cur->left) q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
    cout << endl;
}

int main() {
    int n;
    char arr1[MAX], arr2[MAX];
    cin >> n;
    cin >> arr1;
    cin >> arr2;
    Node *root = buildPrePost(arr1, arr2, n);
    levelOrder(root);
    return 0;
}

/*
Bộ dữ liệu mẫu:
- Tiền tự + Hậu tự: 7 ABDGECF GDEBFCA
- Tiền tự + Trung tự: 7 ABDGCEF DGBAECF
- Hậu tự + Trung tự: 7 GDBEFCA DGBAECF
*/