二叉樹創建：僅憑先序遍歷能否確定一棵樹？帶標記先序創建法

理論結論

• 無標記先序遍歷不能唯一確定二叉樹：同一先序序列可對應多棵不同結構的樹。
• 先序 + 中序 / 後序 + 中序 才能唯一重建 (前提：節點值唯一)。

實驗課常見做法：帶空節點標記的先序創建

輸入序列中用特殊值 (如 -1, #, 0) 表示空指針，遞歸構建：

輸入示例

// 先序：根 左右
// 樹結構：    1
//           /   \
//          2     3
//         / \   / \
//        4  5  6   7
// 輸入序列：1 2 4 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1

遞歸創建代碼

typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

Node* createTree(int *arr, int *index) {
    int val = arr[(*index)++];
    if (val == -1) return NULL;  // 空節點標記
    
    Node *node = (Node*)malloc(sizeof(Node));
    node->data = val;
    node->left = createTree(arr, index);
    node->right = createTree(arr, index);
    return node;
}

// 主函數調用
int main() {
    int pre[] = {1,2,4,-1,-1,5,-1,-1,3,6,-1,-1,7,-1,-1};
    int idx = 0;
    Node *root = createTree(pre, &idx);
    // 後續遍歷驗證...
}

關鍵點

1. 標記消除歧義：空節點標記將隱式結構顯式化，一一對應樹形。
2. 遞歸順序：先構建根，再遞歸構建左子樹，最後右子樹 (先序特性)。
3. 索引傳遞：用指針/引用傳遞數組索引，保證各遞歸層級共享同一遍歷位置。

擴展：其他遍歷創建

總結

實驗要求「先序創建」實際上是「帶標記先序創建」，標記 (如 -1) 將不確定性轉為確定性，是數據結構教學中經典的樹構建練習。