C 語言二元樹先序建立與遍歷：找出節點 D 所在層級

題目要求：依先序序列 ABC@@D@@E@F@@ 建立二元樹（@ 代表空節點），並以先序遍歷找出字元 D 所在的層數（根節點為第 1 層）。

代碼審查與修正

原始代碼邏輯大致正確，但有兩個關鍵問題：

1. 輸入判斷錯誤：if (c == ' ') 應改為 if (c == '@')，題目明確以 @ 代表空節點。
2. 遞迴參數傳遞：creatBiTree(&(*T)->lchild) 雖能編譯，但建議改為 creatBiTree(&((*T)->lchild)) 以明確優先序，並統一風格。

修正後的完整代碼

#include <iostream>
using namespace std;

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void creatBiTree(BiTree *T) {
    char c;
    cin >> c;
    if (c == '@') {
        *T = NULL;
    } else {
        *T = new BiTNode;
        (*T)->data = c;
        creatBiTree(&((*T)->lchild));
        creatBiTree(&((*T)->rchild));
    }
}

void visit(char c, int level) {
    if (c == 'D') cout << c << " 在 " << level << " 層" << endl;
}

void preOrderTraverse(BiTree T, int level) {
    if (T) {
        visit(T->data, level);
        preOrderTraverse(T->lchild, level + 1);
        preOrderTraverse(T->rchild, level + 1);
    }
}

int main() {
    BiTree T = NULL;
    creatBiTree(&T); // 輸入: A B C @ @ D @ @ E @ F @ @
    preOrderTraverse(T, 1);
    return 0;
}

執行結果

輸入序列對應的樹結構中，D 為 B 的右子節點，層級為 3。程式將輸出：D 在 3 層。

常見誤區提醒

• 輸入緩衝區殘留換行符導致讀取錯誤，建議在 cin >> c 前加 cin >> ws 或改用 scanf(" %c", &c)（注意前面空格跳過空白）。
• 遞迴深度受限於棧大小，實際專案中大樹建議改用非遞迴或動態記憶體池。