二元搜尋樹（BST）C語言完整實現與操作詳解

二元搜尋樹定義與特性

二元搜尋樹（Binary Search Tree, BST）滿足：左子樹非空時所有節點值 < 根節點值；右子樹非空時所有節點值 > 根節點值；左右子樹各自也是 BST。最左節點為最小值，最右節點為最大值。插入、查找、刪除皆以遞迴實現。刪除節點時，若有兩個子節點，則在右子樹找後繼節點（最小值），將其值賦給待刪節點，再刪除後繼節點。

C語言實現代碼

#include <iostream>
#include <cstdlib>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 插入元素
TreeNode *insert(TreeNode *root, int val) {
    if (root == NULL) {
        root = new TreeNode(val);
        return root;
    }
    if (val < root->val)
        root->left = insert(root->left, val);
    else if (val > root->val)
        root->right = insert(root->right, val);
    return root;
}

// 尋找最小值節點
TreeNode *findmin(TreeNode *root) {
    if (root == NULL) return NULL;
    if (root->left == NULL && root->right == NULL) return root;
    if (root->left) return findmin(root->left);
    return root; // 隱含處理 root->right 存在但 left 為空的情況
}

// 查找元素
bool find(TreeNode *root, int val) {
    if (root == NULL) return false;
    if (root->val == val) return true;
    if (val < root->val)
        return find(root->left, val);
    else
        return find(root->right, val);
}

// 刪除節點
TreeNode *delnum(TreeNode *root, int val) {
    if (root == NULL) return NULL;
    if (val > root->val)
        root->right = delnum(root->right, val);
    else if (val < root->val)
        root->left = delnum(root->left, val);
    else { // 找到目標節點
        if (root->left && root->right) { // 兩個子節點
            TreeNode *tmp = findmin(root->right);
            root->val = tmp->val;
            root->right = delnum(root->right, tmp->val);
        } else { // 0 或 1 個子節點
            if (root->left == NULL)
                root = root->right;
            else if (root->right == NULL)
                root = root->left;
        }
    }
    return root;
}

// 測試主程式
int main() {
    TreeNode *root = NULL;
    root = insert(root, 3);
    root = insert(root, 2);
    root = insert(root, 4);
    root = insert(root, 1);
    cout << find(root, 2) << endl;  // 輸出 1 (true)
    root = delnum(root, 2);
    cout << find(root, 2) << endl;  // 輸出 0 (false)
    system("pause");
    return 0;
}

關鍵操作解析

進階考量

• 平衡性： 普通 BST 在有序插入時退化為鏈結串列，實務上常用 AVL 樹、紅黑樹等自平衡 BST。
• 重複值處理： 本實現忽略重複值（val == root->val 不插入），實際應用可依需求修改（如計數器或允許重複進右子樹）。
• 記憶體管理： 刪除節點後需 delete 釋放記憶體（本範例為簡潔省略），C 語言中對應 free()。
• 非遞迴實現： 可用堆疊模擬遞迴，避免深度過大導致堆疊溢位。