數據結構定義
typedef char Type; // 數據域類型，可改為 int/float 等
typedef struct Bitree {
Type data;
struct Bitree *lchild;
struct Bitree *rchild;
} BitNode, *BiTree;
核心操作函數速查表
| 函數 | 功能 | 關鍵遞歸邏輯 |
|---|
InitBiTree | 初始化空樹 | *T = NULL |
CreatBiTree | 前序輸入創建（空格表示空節點） | 讀字符→空格置NULL→否則malloc節點→遞歸建左/右子樹 |
ClearBiTree | 後序遞歸釋放所有節點 | 先釋左/右子樹，最後釋放自身並置NULL |
BiTreeEmpty | 判空 | T == NULL |
BiTreeDepth | 求樹深度 | max(左深,右深)+1，空樹深度0 |
Root | 返回根節點副本 | 空樹報錯退出，否則返回 *T |
InserInc | 按字母序插入（BST插入） | e < 根→左，else →右，遞歸找空位掛接 |
Search | 查找值為 p 的節點 | 根匹配返回，否則遞歸查左再查右 |
DeleteChild | 刪除指定節點的左/右子樹 | Search定位父節點→ClearBiTree清空子樹→置NULL |
Parent | 查找值為 e 的節點的父節點 | 檢查左右孩子匹配，否則遞歸查左/右子樹 |
LeftChild | 返回左孩子節點 | 匹配根返回 lchild，否則遞歸查左/右子樹 |
LeftSibling | 返回左兄弟（即父節點的右孩子） | 若當前節點是右孩子，返回左孩子；否則遞歸查左/右子樹 |
關鍵遞歸模式解析
1. 創建樹：前序輸入 + 雙重指針修改實參
int CreatBiTree(BiTree *T) {
Type ch; scanf("%c", &ch);
if (ch == ' ') *T = NULL;
else {
*T = (BiTree)malloc(sizeof(BitNode));
(*T)->data = ch;
CreatBiTree(&(*T)->lchild); // 傳遞子樹指針的地址
CreatBiTree(&(*T)->rchild);
}
return OK;
}
核心點：參數用 BiTree*（即 BitNode**），遞歸時傳 &(*T)->lchild，使函數能修改調用者的指針變量。
2. 清空樹：後序釋放 + 雙重指針置 NULL
int ClearBiTree(BiTree *T) {
if ((*T)->lchild) ClearBiTree(&(*T)->lchild);
if ((*T)->rchild) ClearBiTree(&(*T)->rchild);
if ((*T)->lchild == NULL && (*T)->rchild == NULL) {
free(*T); *T = NULL; // 釋放葉子節點並斷開父節點連接
}
return OK;
}
3. 查找父節點/兄弟節點：利用返回值回溯
BiTree Parent(BiTree T, Type e) {
if (!T) return NULL;
if ((T->lchild && T->lchild->data == e) || (T->rchild && T->rchild->data == e))
return T; // 當前節點即父節點
BiTree cur = Parent(T->lchild, e);
return cur ? cur : Parent(T->rchild, e); // 左找到返回，否則查右
}
測試主函數
int main() {
BiTree T;
CreatBiTree(&T); // 輸入示例: "ABD E CF G " (空格代表空)
// 測試各操作...
BiTree temp = LeftSibling(T, 'A'); // 查找 A 的左兄弟
return 0;
}
遞歸思維養成：三步法
- 終止條件：空樹
T==NULL、葉子節點、找到目標值。
- 遞歸假設：相信左/右子樹的同名函數已正確實現功能。
- 問題分解：當前節點做微小處理（比較、賦值、打印），其餘交給遞歸。
常見錯誤與修正
| 錯誤現象 | 原因 | 修正 |
|---|
| 創建樹後根節點為 NULL | 參數用 BiTree T 值傳遞，函數內修改不影響外部 | 改用 BiTree *T，調用傳 &T |
| ClearBiTree 後外部指針未置 NULL，野指針 | 函數內 free(T); T=NULL 只修改形參副本 | 參數用 BiTree *T，釋放後 *T=NULL |
| Search/Parent 返回錯誤節點 | 未檢查子節點是否為 NULL 直接訪問 ->data | 先判 T->lchild && T->lchild->data == e |
