一步步演算法：二元搜尋樹（BST）完整實作指南

二元搜尋樹（Binary Search Tree, BST）是資料結構基石，也是紅黑樹、AVL 樹、B+ 樹等進階結構的基礎。本文從節點定義出發，逐步實作建立、查找、遍歷、統計節點數與計算樹高等核心操作，附完整 C 語言程式碼。

節點結構定義

每個節點包含資料、父節點、左/右子節點指標：

typedef struct TreeNode {
    int data;
    struct TreeNode *parent;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

BST 性質：任意節點的左子樹鍵值 < 節點鍵值 < 右子樹鍵值。

核心操作實作

1. 建立新節點

TreeNode* create_node(int data) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    if (!node) return NULL;
    node->data = data;
    node->parent = node->left = node->right = NULL;
    return node;
}

2. 遞迴查找

TreeNode* find(TreeNode *root, int key) {
    if (!root) return NULL;
    if (key == root->data) return root;
    return key < root->data ? find(root->left, key) : find(root->right, key);
}

利用 BST 有序性，每次比較排除一半子樹，平均 O(log n)，最壞 O(n)（退化成鏈表）。

3. 中序遍歷（輸出遞增序列）

void inorder_print(TreeNode *root) {
    if (!root) return;
    inorder_print(root->left);
    printf("%d ", root->data);
    inorder_print(root->right);
}

左-根-右順序恰好產生遞增序列，驗證 BST 性質的最佳方式。

4. 統計節點總數

int count_nodes(TreeNode *root) {
    if (!root) return 0;
    return 1 + count_nodes(root->left) + count_nodes(root->right);
}

5. 計算樹高

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

樹高定義：根到最深葉節點的邊數（或節點數-1）。平衡樹操作（如 AVL 旋轉）需頻繁查詢高度。

進階話題：插入與刪除

本文著重基礎查詢操作，插入與刪除涉及樹結構修改，關鍵點：

• 插入：同查找路徑至 NULL 處掛接新節點，維護 parent 指標
• 刪除：三種情況（無子、單子、雙子），雙子時用中序前驅/後繼替代

掌握上述五大基礎操作，是理解平衡樹旋轉、區間查詢等進階主題的前提。

工程建議

1. 遞迴深度：極端不平衡樹可能導致堆疊溢位，生產環境可改用迭代或顯式堆疊
2. 記憶體管理：搭配釋放函式避免洩漏，考慮記憶體池優化頻繁分配
3. 泛型化：以 void* + 比較函式指標支援任意型別

總結

BST 以優雅的遞迴結構實現動態有序集合，核心操作簡潔高效。熟練掌握其遞迴思維、指標操作與邊界處理，是演算法工程師的基本功，也是通往紅黑樹、B+ 樹等工業級索引結構的必經之路。