PAT 甲級 1040 Complete Binary Search Tree：構建完全二叉搜尋樹並輸出層序遍歷

題目大意

給定 N（≤1000）個互不相同的非負整數鍵值，構建一棵完全二叉搜尋樹（CBST）：

• 滿足 BST 性質：左子樹鍵值 < 根 < 右子樹鍵值
• 滿足 CBT 結構：除最後一層外各層節點數達最大值，最後一層節點靠左排列

輸出該樹的層序遍歷（Level Order）序列。

關鍵觀察：CBT 結構固定，僅需填充鍵值

完全二叉樹的結構僅由節點總數 N 決定，與鍵值無關。若按層序編號（根為 1，左子 2i，右子 2i+1），則樹的拓撲結構完全確定。問題轉化為：將排序後的鍵值按中序遍歷順序填入這個固定結構，自然滿足 BST 性質。

演算法流程

1. 讀入 N 個鍵值，升序排序（qsort）
2. 遞歸中序遍歷固定結構樹（索引 1~N），依序取出排序陣列元素填入 inorder[]
3. inorder[] 即為層序遍歷結果（因為索引即層序編號）
4. 輸出 inorder[1] 到 inorder[N]

核心代碼（C 語言）

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) { return *(int*)a - *(int*)b; }

// 中序遍歷填充：n 為當前節點層序編號（1-based），i 為排序陣列當前索引（靜態保持）
void inOrder(int *sorted, int n, int *inorder, int N) {
    static int i = 0;
    if (n * 2 <= N) inOrder(sorted, n * 2, inorder, N);      // 左子樹
    inorder[n] = sorted[i++];                                 // 根節點
    if (n * 2 + 1 <= N) inOrder(sorted, n * 2 + 1, inorder, N); // 右子樹
}

int main() {
    int N; scanf("%d", &N);
    int keys[N];
    for (int i = 0; i < N; i++) scanf("%d", &keys[i]);

    qsort(keys, N, sizeof(int), cmp);

    int inorder[N + 1];  // 1-based 索引對應層序編號
    inOrder(keys, 1, inorder, N);

    for (int i = 1; i <= N; i++) {
        printf("%d%c", inorder[i], i == N ? '\n' : ' ');
    }
    return 0;
}

範例演示

輸入：10 1 2 3 4 5 6 7 8 9 0

排序後：0 1 2 3 4 5 6 7 8 9

中序填充過程（節點編號 → 鍵值）：

1→6, 2→3, 3→8, 4→1, 5→5, 6→7, 7→9, 8→0, 9→2, 10→4

輸出：6 3 8 1 5 7 9 0 2 4 ✅

設計亮點

• 無全域變數汙染：排序陣列索引用 static int i 封裝在遞歸函數內
• 索引即層序：利用 CBT 隱式陣列表示法（2i, 2i+1），無需顯式節點結構
• 時空優秀：O(N log N) 排序 + O(N) 遍歷，空間 O(N)