C語言二叉樹完整實現教學：從構建到遍歷與釋放

二叉樹資料結構的C語言實現詳解

二叉樹是電腦科學中最基礎且重要的非線性資料結構之一。本文提供一個完整的C語言實現範例，涵蓋節點定義、樹的建立、四種遍歷方式（先序、中序、後序、葉子節點）、圖形化顯示以及記憶體釋放等核心操作。適合資料結構初學者參考學習。

核心資料結構定義

首先定義二叉樹節點結構，包含資料欄位與左右子節點指標：

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

搭配狀態碼常數：OK、ERROR、OVERFLOW 等，方便函數回傳執行狀態。

樹的建立：遞迴預序輸入法

CreateTree 採用「預序序列 + # 代表空節點」的方式遞迴建樹。輸入範例 abd##e##cf##g## 可建立一棵完整二叉樹。程式碼採用雙重指標 BiNode** 以便在函數內修改根節點指標。

四大遍歷演算法實現

• 先序遍歷：根 → 左 → 右
• 中序遍歷：左 → 根 → 右
• 後序遍歷：左 → 右 → 根
• 葉子節點列印：判斷左右子節點皆為 NULL

所有遍歷函數均採用遞迴實現，並透過 Visit() 回呼函數輸出節點資料，體現關注點分離原則。

圖形化顯示與記憶體管理

Display() 以縮排方式將樹結構以 90 度旋轉形式列印於終端機，直觀展示層級關係。DelTree() 採用後序遍歷釋放節點記憶體，避免記憶體洩漏，並列印刪除過程供除錯參考。

主程式流程示範

main() 函數完整串聯：建樹 → 三種遍歷輸出 → 顯示葉子 → 圖形化列印 → 釋放記憶體。編譯執行後可觀察完整生命週期。

教學重點總結

1. 雙重指標在樹操作中的關鍵作用
2. 遞迴思維處理樹狀結構的通用模式
3. 遍歷順序對應不同應用場景（如中序得排序序列）
4. 記憶體釋放順序必須為後序，否則會導致指標失效

完整原始碼已包含於本文，可直接複製編譯執行（建議使用支援 C99 的編譯器，並移除 conio.h 相關函數以提升跨平台相容性）。