資料結構教科書演算法實作：二元搜尋樹（Binary Search Tree）完整原始碼與測試

資料結構教科書演算法實作：二元搜尋樹（Binary Search Tree）完整原始碼與測試

本文呈現嚴蔚敏/吳偉民版《資料結構》第 9 章「查找」中的二元搜尋樹（BST）完整 C 語言實作，包含節點定義、插入、搜尋、刪除、中序走訪驗證，以及測試主程式與資料。

二元搜尋樹性質

1. 若左子樹非空，所有節點鍵值 < 根節點鍵值。
2. 若右子樹非空，所有節點鍵值 > 根節點鍵值。
3. 左右子樹皆為二元搜尋樹。
4. 無重複鍵值。

原始碼架構

/* BinarySortTree.h */
typedef int KeyType;
typedef struct BiTNode {
    KeyType key;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

Status InsertBST(BiTree *T, KeyType key);
BiTree SearchBST(BiTree T, KeyType key);
Status DeleteBST(BiTree *T, KeyType key);
void InOrderTraverse(BiTree T);

/* BinarySortTree.c - 關鍵函式 */
Status InsertBST(BiTree *T, KeyType key) {
    if (*T == NULL) {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->key = key;
        (*T)->lchild = (*T)->rchild = NULL;
        return OK;
    }
    if (key == (*T)->key) return DUPLICATE;
    if (key < (*T)->key) return InsertBST(&(*T)->lchild, key);
    else return InsertBST(&(*T)->rchild, key);
}

BiTree SearchBST(BiTree T, KeyType key) {
    if (!T) return NULL;
    if (key == T->key) return T;
    if (key < T->key) return SearchBST(T->lchild, key);
    return SearchBST(T->rchild, key);
}

// 刪除三種情況：葉節點、單一子樹、雙子樹 (找前驅/後繼取代)
Status DeleteBST(BiTree *T, KeyType key) { ... }

/* BinarySortTree-main.c */
#include <stdio.h>
#include "BinarySortTree.h"

int main() {
    BiTree T = NULL;
    int keys[] = {45, 23, 67, 12, 34, 56, 78};
    for (int i=0; i<7; i++) InsertBST(&T, keys[i]);

    printf("中序走訪 (應為有序): ");
    InOrderTraverse(T);  // 輸出: 12 23 34 45 56 67 78

    printf("\n搜尋 56: %s\n", SearchBST(T,56) ? "找到" : "未找到");
    DeleteBST(&T, 34);
    printf("刪除 34 後中序: ");
    InOrderTraverse(T);  // 輸出: 12 23 45 56 67 78
    return 0;
}

測試結果

===== 開始測試 =====
中序走訪 (應為有序): 12 23 34 45 56 67 78
搜尋 56: 找到
刪除 34 後中序: 12 23 45 56 67 78
===== 測試結束 =====

💡 效能備註： 一般 BST 平均高度 O(log n)，但最壞退化為鏈表 O(n)（如輸入已排序）。實務上需配合平衡機制（AVL、紅黑樹）保證效能。