C++ 根據先序中序遍歷重建二叉樹並打印後序與樹形結構

問題描述

輸入先序遍歷 ABCDE 和中序遍歷 BADCE，輸出後序遍歷 BDECA 並在控制台以樹形圖顯示：

A
|_B
|_C
  |_D
  |_E

核心算法

1. 遞歸重建：先序首元素為根，在中序中找到根的位置，左側為左子樹，右側為右子樹，遞歸構建。
2. 後序遍歷：左-右-根。
3. 樹形打印：先序遍歷計算每個節點的行列坐標，用字符數組模擬畫布，繪製連線字符（│ ─ ├ └）。

關鍵代碼結構

struct Node { char data; Node *left, *right; int row, col; };

Node* rebuild(string pre, string in) {
    if (pre.empty()) return nullptr;
    Node* root = new Node{pre[0], nullptr, nullptr, 0, 0};
    size_t pos = in.find(pre[0]);
    root->left = rebuild(pre.substr(1, pos), in.substr(0, pos));
    root->right = rebuild(pre.substr(pos+1), in.substr(pos+1));
    return root;
}

void postorder(Node* r) {
    if (!r) return;
    postorder(r->left);
    postorder(r->right);
    cout << r->data;
}

// 打印邏輯參考原帖完整代碼，核心是計算 row/col 並填充字符矩陣

參考資源

• 二叉樹控制台打印算法
• 先序中序重建樹