C語言實現二分查找樹（BST）完整操作集

二分查找樹簡介

二分查找樹（Binary Search Tree）是一種有序的二叉樹：每個節點的左子樹鍵值小於節點，右子樹鍵值大於節點。本文提供標準 C 實現，包含插入、刪除、查找、最值查詢等核心操作。

數據結構定義 tree.h

typedef int ElementType;
#ifndef TREE_H_INCLUDED
#define TREE_H_INCLUDED
struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

SearchTree MakeEmpty(SearchTree T);
Position Find(ElementType X, SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
ElementType Retrieve(Position P);
#endif

核心實現 tree.c

#include "tree.h"
#include "fatal.h"

struct TreeNode {
    ElementType Element;
    SearchTree Left;
    SearchTree Right;
};

/* 遞歸銷毀整棵樹 */
SearchTree MakeEmpty(SearchTree T) {
    if (T) {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

/* 遞歸查找 */
Position Find(ElementType X, SearchTree T) {
    if (!T) return NULL;
    if (X < T->Element) return Find(X, T->Left);
    else if (X > T->Element) return Find(X, T->Right);
    else return T;
}

/* 遞歸找最小值（最左節點） */
Position FindMin(SearchTree T) {
    if (!T) return NULL;
    else if (!T->Left) return T;
    else return FindMin(T->Left);
}

/* 非遞歸找最大值（最右節點） */
Position FindMax(SearchTree T) {
    if (T) while (T->Right) T = T->Right;
    return T;
}

/* 插入：遞歸尋找位置並創建節點 */
SearchTree Insert(ElementType X, SearchTree T) {
    if (!T) {
        T = malloc(sizeof(struct TreeNode));
        if (!T) FatalError("Out of space!!!");
        T->Element = X; T->Left = T->Right = NULL;
    } else if (X < T->Element)
        T->Left = Insert(X, T->Left);
    else if (X > T->Element)
        T->Right = Insert(X, T->Right);
    /* 重複值忽略 */
    return T;
}

/* 刪除：三種情況處理 */
SearchTree Delete(ElementType X, SearchTree T) {
    Position TmpCell;
    if (!T) Error("Element not found");
    else if (X < T->Element) T->Left = Delete(X, T->Left);
    else if (X > T->Element) T->Right = Delete(X, T->Right);
    else { /* 找到待刪節點 */
        if (T->Left && T->Right) { /* 兩個子節點 */
            TmpCell = FindMin(T->Right);        // 找右子樹最小值
            T->Element = TmpCell->Element;      // 替換值
            T->Right = Delete(T->Element, T->Right); // 刪除右子樹中該最小節點
        } else { /* 一個或零個子節點 */
            TmpCell = T;
            if (!T->Left) T = T->Right;
            else if (!T->Right) T = T->Left;
            free(TmpCell);
        }
    }
    return T;
}

ElementType Retrieve(Position P) { return P->Element; }

關鍵操作解析

刪除節點的三種情況

1. 葉子節點：直接釋放，父節點對應指針置 NULL。
2. 單子節點：用子節點替換被刪節點位置。
3. 雙子節點：找右子樹最小值（或左子樹最大值）替換節點值，然後在右子樹中刪除該最小值節點（轉化為情況 1 或 2）。

遞歸與非遞歸選擇

• Find、FindMin、Insert、Delete 均用遞歸，代碼簡潔直觀。
• FindMax 用迭代避免尾遞歸開銷（雖然現代編譯器可優化）。

使用示例

SearchTree T = NULL;
T = Insert(5, T);
T = Insert(3, T);
T = Insert(7, T);
Position p = Find(3, T);
if (p) printf("Found: %d\n", Retrieve(p));
T = Delete(3, T);
MakeEmpty(T); // 釋放所有內存

擴展建議

• 添加平衡機制（AVL、紅黑樹）避免退化為鏈表。
• 支持自定義比較函數以處理非整數類型。
• 實現中序遍歷輸出有序序列。