AVL 平衡二叉樹的 C 語言非遞歸完整實現與操作詳解

數據結構定義

typedef enum { EH=0, LH=1, RH=-1 } bh_t;  // 平衡因子
typedef int ElemType;
typedef struct BSTNode {
    ElemType key;
    int bf;                 // 平衡因子
    struct BSTNode *lchild, *rchild, *parent;
} BSTNode, *BSTree;

核心操作

1. 查找

searchAVL 非遞歸查找，返回是否存在並記錄父節點。

2. 輔助函數

• minNode/maxNode：獲取子樹最小/最大節點。
• preNode/nextNode：中序前驅/後繼（用於刪除時尋找替代節點）。

3. 旋轉平衡

四種不平衡情況對應兩大平衡函數：

• leftbalance：LL（右單旋）+ LR（先左後右雙旋）。
• rightbalance：RR（左單旋）+ RL（先右後左雙旋）。

旋轉中同步更新 parent 指針與 bf，區分插入/刪除場景調整平衡因子邏輯。

4. 插入

1. 查找插入位置，創建節點 bf=EH 掛接。
2. 沿祖先鏈向上回溯更新 bf，遇到不平衡調用對應 balance 函數，調整完畢即返回。

5. 刪除

1. 定位待刪節點，若有雙子則用前驅/後繼值覆蓋，轉為刪除葉子或單子節點。
2. 從實際刪除點父節點向上回溯更新 bf，不平衡時調用 balance 並結束。
3. 釋放節點，處理根節點被刪除情況。

6. 創建/銷燬/遍歷

createAVL 循環插入構建；destroyAVL 後序遞歸釋放；提供中序/先序遍歷驗證。

測試主程序

int data[] = {1,5,7,4,3,2,11,9,10,100};
BSTNode* root = createAVL(data, 10);
InOrderTraverse(root);  // 有序輸出
root = deleteNode(5, root);
... 連續刪除並打印驗證平衡性

特點總結

• 完全非遞歸實現，避免棧溢出，效率更高。
• 維護 parent 指針，便於向上回溯調整。
• 代碼經常規測試，插入/刪除/遍歷功能完備。