劍指Offer：從上往下打印二叉樹（層序遍歷，九度OJ 1523）

題目描述

從上到下、從左到右逐層打印二叉樹節點值（即層序遍歷 / 廣度優先搜索 BFS）。

輸入格式

• 多測試用例，EOF 結束
• 每用例第一行：n（1 ≤ n ≤ 1000），節點數，編號 1~n
• 第二行：n 個整數，第 i 個為節點 i 的值
• 接下來 n 行：每行一個字符 C_i 及對應孩子編號
  • d：雙孩子，後接左右孩子編號
  • l：只有左孩子，後接左孩子編號
  • r：只有右孩子，後接右孩子編號
  • z：無孩子
• 節點 1 為根

樣例

輸入：
7
8 6 5 7 10 9 11
d 2 5
d 3 4
z
z
d 6 7
z
z

輸出：
8 6 10 5 7 9 11

解題思路：標準 BFS（廣度優先搜索）

算法步驟

1. 掃描根節點，將其孩子入隊
2. 循環取隊頭節點，輸出其值，將其左、右孩子（若存在）依序入隊
3. 隊列為空時結束

關鍵點：先入左孩子，再入右孩子，保證同層從左到右輸出。

完整代碼

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

#define MAXSIZE 1005

typedef struct TreeNode {
    int num;
    int lchild;
    int rchild;
} TreeNode;

typedef struct TreeArr {
    TreeNode arr[MAXSIZE];
} TreeArr;

int Queue[MAXSIZE] = {0};
int front = 0, rear = 0;
int result[MAXSIZE] = {0};
int res_top = 0;

void findTree(TreeArr *a, int n, int idx);

int main() {
    int n;
    while (scanf("%d", &n) != EOF && n >= 1 && n <= 1000) {
        TreeArr *a = (TreeArr *)malloc(sizeof(TreeArr));
        
        // 初始化
        memset(Queue, 0, sizeof(int) * MAXSIZE);
        memset(result, 0, sizeof(int) * MAXSIZE);
        front = rear = res_top = 0;
        for (int i = 0; i < MAXSIZE; i++) {
            a->arr[i].num = 0;
            a->arr[i].lchild = 0;
            a->arr[i].rchild = 0;
        }
        
        // 讀取節點值
        for (int i = 1; i <= n; i++) scanf("%d", &a->arr[i].num);
        
        // 讀取孩子關係
        for (int i = 1; i <= n; i++) {
            char c;
            int n1, n2;
            scanf("\n%c", &c);
            if (c == 'd') {
                scanf("%d %d", &n1, &n2);
                a->arr[i].lchild = n1;
                a->arr[i].rchild = n2;
            } else if (c == 'l') {
                scanf("%d", &n1);
                a->arr[i].lchild = n1;
            } else if (c == 'r') {
                scanf("%d", &n1);
                a->arr[i].rchild = n1;
            }
        }
        
        // BFS 遍歷
        findTree(a, n, 1);
        while (front != rear) {
            findTree(a, n, Queue[front++]);
        }
        
        // 輸出
        for (int i = 0; i < n - 1; i++) printf("%d ", result[i]);
        printf("%d\n", result[n-1]);
        
        free(a);
    }
    return 0;
}

void findTree(TreeArr *a, int n, int idx) {
    if (idx <= n) result[res_top++] = a->arr[idx].num;
    if (a->arr[idx].lchild != 0) Queue[rear++] = a->arr[idx].lchild;
    if (a->arr[idx].rchild != 0) Queue[rear++] = a->arr[idx].rchild;
}

/**************************************************************
 Problem: 1523
 Result: Accepted
 Time: 0 ms
 Memory: 920 kb
 **************************************************************/

複雜度分析

• 時間複雜度：O(n)，每個節點入隊出隊各一次
• 空間複雜度：O(n)，隊列與結果陣列