二叉樹完整實踐：建樹、遞歸/非遞歸遍歷、求高度

資料結構定義

#define STACK_SIZE 100

typedef struct TreeNode {
    char data;
    struct TreeNode *left, *right;
} *Tree, Node;   // Tree = Node*

// 手寫棧供非遞歸中序使用
typedef struct {
    Node node[STACK_SIZE];  // 存節點副本（非指標）
    int top;
} Stack;

樹的建立（先序輸入，'a' 代表空）

void create_tree(Tree *t) {
    char buf[2];
    scanf("%1s", buf);      // 讀單字符，跳過空白/換行
    char ch = buf[0];

    if (ch == 'a') { *t = NULL; return; }

    *t = (Tree)malloc(sizeof(Node));
    (*t)->data = ch;
    create_tree(&(*t)->left);
    create_tree(&(*t)->right);
}

輸入範例：1 2 3 a 4 a a a a 對應樹：

      1
    /   \
   2     3
  / \   / \
 a   4 a   a
    / \
   a   a

三種遞歸遍歷

void pre_order(Tree t) {  // 根左右
    if (!t) return;
    putchar(t->data);
    pre_order(t->left);
    pre_order(t->right);
}

void in_order(Tree t) {   // 左根右
    if (!t) return;
    in_order(t->left);
    putchar(t->data);
    in_order(t->right);
}

void post_order(Tree t) { // 左右根
    if (!t) return;
    post_order(t->left);
    post_order(t->right);
    putchar(t->data);
}

非遞歸中序（手寫棧）

void in_order_stack(Tree t) {
    if (!t) return;
    Stack s; s.top = 0;
    Node *cur = (Node*)malloc(sizeof(Node));  // 臨時節點

    while (s.top > 0 || t) {
        if (t) {
            // 壓入副本
            s.node[s.top++] = *t;
            t = t->left;
        } else {
            *cur = s.node[--s.top];
            putchar(cur->data);
            t = cur->right;
        }
    }
    putchar('\n');
    free(cur);
}

求樹高

int tree_height(Tree t) {
    if (!t) return 0;
    int lh = tree_height(t->left);
    int rh = tree_height(t->right);
    return (lh > rh ? lh : rh) + 1;
}

主程式測試

int main() {
    Tree root = NULL;
    create_tree(&root);   // 輸入: 1 2 3 a 4 a a a a

    printf("pre: ");  pre_order(root);  putchar('\n');
    printf("in:  ");  in_order(root);   putchar('\n');
    printf("post:");  post_order(root);  putchar('\n');
    printf("Height: %d\n", tree_height(root));
    printf("in (stack): "); in_order_stack(root);
    return 0;
}

輸出驗證

pre: 1234
in:  2431
post: 4231
Height: 3
in (stack): 2 4 3 1

關鍵點提醒

• scanf("%c") 會讀走換行，改用 %1s 或 " %c"（前置空格跳白）。
• 棧存 節點副本 而非指標，避免原樹修改時副本失效；但副本佔空間，大型樹建議存指標。
• 非遞歸中序核心：一路向左壓棧，無左則彈出訪問再轉右。
• 釋放記憶體：實務上需後序遍歷遞歸 free，此處省略。