二元樹完整實作：建立、四種走訪、葉節點顯示、樹狀列印與記憶體釋放

二元樹資料結構定義

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2

typedef int Status;

typedef struct BiNode {
    char Data;
    struct BiNode* lChild;
    struct BiNode* rChild;
} BiNode, *PBiNode;

核心功能函數

1. 建立二元樹（前序輸入，# 表空節點）

Status CreateTree(BiNode** pTree) {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        *pTree = NULL;
    } else {
        *pTree = (BiNode*)malloc(sizeof(BiNode));
        (*pTree)->Data = ch;
        CreateTree(&((*pTree)->lChild));
        CreateTree(&((*pTree)->rChild));
    }
    return OK;
}

// 輸入範例：abd##e##cf##g##
// 對應樹結構：
//       a
//     /   \
//    b     c
//   / \   / \
//  d   e f   g

2. 三種深度優先走訪

Status PreOrderTraval(BiNode* T) {
    if (T) {
        Visit(T->Data);
        PreOrderTraval(T->lChild);
        PreOrderTraval(T->rChild);
    }
    return OK;
}

Status InOrderTraval(BiNode* T) {
    if (T) {
        InOrderTraval(T->lChild);
        Visit(T->Data);
        InOrderTraval(T->rChild);
    }
    return OK;
}

Status PostOrderTraval(BiNode* T) {
    if (T) {
        PostOrderTraval(T->lChild);
        PostOrderTraval(T->rChild);
        Visit(T->Data);
    }
    return OK;
}

Status Visit(char Data) {
    printf("%c", Data);
    return OK;
}

3. 樹狀結構列印

Status Display(BiNode* T, int Level) {
    if (!T) return OK;
    Display(T->lChild, Level + 1);
    for (int i = 0; i < Level - 1; ++i) printf("  ");
    if (Level >= 1) printf("--");
    printf("%c\n", T->Data);
    Display(T->rChild, Level + 1);
    return OK;
}

// 輸出範例：
//       --g
//     --c
//       --f
//   --a
//       --e
//     --b
//       --d

4. 葉節點顯示

Status ShowLeaves(BiNode* T) {
    if (T) {
        ShowLeaves(T->lChild);
        ShowLeaves(T->rChild);
        if (!T->lChild && !T->rChild)
            Visit(T->Data);
    }
    return OK;
}
// 輸出：d e f g

5. 遞迴釋放整棵樹

Status DelTree(BiNode* T) {
    if (T) {
        DelTree(T->lChild);
        DelTree(T->rChild);
        printf("Deleting %c\n", T->Data);
        free(T);
    }
    return OK;
}

主程式流程

int main() {
    BiNode* pRoot = NULL;
    CreateTree(&pRoot);
    
    printf("PreOrder: ");  PreOrderTraval(pRoot);  printf("\n");
    printf("InOrder: ");   InOrderTraval(pRoot);   printf("\n");
    printf("PostOrder: "); PostOrderTraval(pRoot); printf("\n");
    
    printf("ShowLeaves: "); ShowLeaves(pRoot); printf("\n");
    printf("Tree Structure:\n"); Display(pRoot, 0);
    
    printf("Deleting Tree:\n"); DelTree(pRoot);
    printf("BiTree Deleted.\n");
    return 0;
}

教學重點總結

• 遞迴結構：所有操作均採用遞迴，符合樹的遞迴定義
• 記憶體管理：malloc 建立節點，free 後序釋放
• 輸入格式：前序序列，# 代表空指標
• 錯誤處理：配置失敗呼叫 exit(OVERFLOW)
• 擴充性：可輕易加入搜尋、插入、刪除、高度計算等功能