資料結構 C 語言實戰：二元樹與二元搜尋樹完整實作

編輯：關於C語言

前言：樹形結構是演算法核心

二元樹是非線性資料結構基石，二元搜尋樹（BST）更是動態查找、排序的高效結構。本文提供標準 C 完整實作，涵蓋建立、遍歷、查找、插入、刪除、深度計算等核心操作，程式碼模組化、註解完整，可直接納入專案或教學使用。

一、基礎二元樹結構與 11 大核心操作

節點定義


#define STACK_MAX_SIZE 30
#define QUEUE_MAX_SIZE 30
typedef char elemType;

struct BTreeNode {
    elemType data;
    struct BTreeNode *left;
    struct BTreeNode *right;
};

1. 初始化


void initBTree(struct BTreeNode **bt) { *bt = NULL; }

2. 由廣義表字串建立

格式範例："A(B(C), D(E(F, G), H(, I)))"


void createBTree(struct BTreeNode **bt, char *str) {
    struct BTreeNode *p, *stack[STACK_MAX_SIZE];
    int top = -1, k = 0, i = 0;
    *bt = NULL;

    while (str[i] != '\0') {
        switch (str[i]) {
            case ' ': break;
            case '(':
                if (top == STACK_MAX_SIZE - 1) exit(1);
                stack[++top] = p;
                k = 1; // 處理左子樹
                break;
            case ')':
                if (top == -1) exit(1);
                top--;
                break;
            case ',':
                k = 2; // 處理右子樹
                break;
            default: // 節點資料
                p = malloc(sizeof(struct BTreeNode));
                p->data = str[i];
                p->left = p->right = NULL;
                if (*bt == NULL) *bt = p;
                else if (k == 1) stack[top]->left = p;
                else stack[top]->right = p;
        }
        i++;
    }
}

3. 判空


int emptyBTree(struct BTreeNode *bt) { return bt == NULL; }

4. 求深度（遞迴）


int BTreeDepth(struct BTreeNode *bt) {
    if (bt == NULL) return 0;
    int dl = BTreeDepth(bt->left);
    int dr = BTreeDepth(bt->right);
    return (dl > dr ? dl : dr) + 1;
}

5. 查找節點（遞迴）


elemType *findBTree(struct BTreeNode *bt, elemType x) {
    if (bt == NULL) return NULL;
    if (bt->data == x) return &(bt->data);
    elemType *p = findBTree(bt->left, x);
    if (p) return p;
    return findBTree(bt->right, x);
}

6. 廣義表格式輸出（前序）


void printBTree(struct BTreeNode *bt) {
    if (bt != NULL) {
        printf("%c", bt->data);
        if (bt->left || bt->right) {
            printf("(");
            printBTree(bt->left);
            if (bt->right) printf(",");
            printBTree(bt->right);
            printf(")");
        }
    }
}

7. 清除樹（後序釋放）


void clearBTree(struct BTreeNode **bt) {
    if (*bt != NULL) {
        clearBTree(&((*bt)->left));
        clearBTree(&((*bt)->right));
        free(*bt);
        *bt = NULL;
    }
}

8-10. 三種深度優先遍歷


// 前序：根-左-右
void preOrder(struct BTreeNode *bt) {
    if (bt) {
        printf("%c ", bt->data);
        preOrder(bt->left);
        preOrder(bt->right);
    }
}

// 中序：左-根-右
void inOrder(struct BTreeNode *bt) {
    if (bt) {
        inOrder(bt->left);
        printf("%c ", bt->data);
        inOrder(bt->right);
    }
}

// 後序：左-右-根
void postOrder(struct BTreeNode *bt) {
    if (bt) {
        postOrder(bt->left);
        postOrder(bt->right);
        printf("%c ", bt->data);
    }
}

11. 層序遍歷（佇列實作）


void levelOrder(struct BTreeNode *bt) {
    struct BTreeNode *q[QUEUE_MAX_SIZE], *p;
    int front = 0, rear = 0;
    if (bt) q[++rear % QUEUE_MAX_SIZE] = bt;
    while (front != rear) {
        p = q[++front % QUEUE_MAX_SIZE];
        printf("%c ", p->data);
        if (p->left) q[++rear % QUEUE_MAX_SIZE] = p->left;
        if (p->right) q[++rear % QUEUE_MAX_SIZE] = p->right;
    }
}

二、二元搜尋樹 (BST) 專用操作

BST 性質：左子樹鍵值 < 根 < 右子樹鍵值。操作複雜度平均 O(log n)。

1. 查找（遞迴與迴圈）


// 遞迴
elemType *findBSTree1(struct BTreeNode *bst, elemType x) {
    if (!bst) return NULL;
    if (x == bst->data) return &(bst->data);
    return x < bst->data ? findBSTree1(bst->left, x) : findBSTree1(bst->right, x);
}

// 迴圈（推薦，無遞迴開銷）
elemType *findBSTree2(struct BTreeNode *bst, elemType x) {
    while (bst) {
        if (x == bst->data) return &(bst->data);
        bst = x < bst->data ? bst->left : bst->right;
    }
    return NULL;
}

2. 插入（遞迴與迴圈）


// 遞迴
void insertBSTree1(struct BTreeNode **bst, elemType x) {
    if (*bst == NULL) {
        *bst = malloc(sizeof(struct BTreeNode));
        (*bst)->data = x;
        (*bst)->left = (*bst)->right = NULL;
        return;
    }
    if (x < (*bst)->data) insertBSTree1(&((*bst)->left), x);
    else insertBSTree1(&((*bst)->right), x);
}

// 迴圈
void insertBSTree2(struct BTreeNode **bst, elemType x) {
    struct BTreeNode *p, *cur = *bst, *parent = NULL;
    while (cur) {
        parent = cur;
        cur = x < cur->data ? cur->left : cur->right;
    }
    p = malloc(sizeof(struct BTreeNode));
    p->data = x; p->left = p->right = NULL;
    if (!parent) *bst = p;
    else if (x < parent->data) parent->left = p;
    else parent->right = p;
}

3. 由陣列建立


void createBSTree(struct BTreeNode **bst, elemType a[], int n) {
    *bst = NULL;
    for (int i = 0; i < n; i++) insertBSTree1(bst, a[i]);
}

4. 刪除節點（三種情況完整處理）


int deleteBSTree(struct BTreeNode **bst, elemType x) {
    if (*bst == NULL) return 0;
    struct BTreeNode *temp = *bst;

    if (x < (*bst)->data) return deleteBSTree(&((*bst)->left), x);
    if (x > (*bst)->data) return deleteBSTree(&((*bst)->right), x);

    // 找到目標節點
    if ((*bst)->left == NULL) { *bst = (*bst)->right; free(temp); return 1; }
    if ((*bst)->right == NULL) { *bst = (*bst)->left; free(temp); return 1; }

    // 雙子樹皆存在：尋找中序前驅（左子樹最大值）
    if ((*bst)->left->right == NULL) {
        (*bst)->data = (*bst)->left->data;
        return deleteBSTree(&((*bst)->left), (*bst)->data);
    } else {
        struct BTreeNode *p1 = *bst, *p2 = p1->left;
        while (p2->right) { p1 = p2; p2 = p2->right; }
        (*bst)->data = p2->data;
        return deleteBSTree(&(p1->right), p2->data);
    }
}

三、測試主程式


int main() {
    struct BTreeNode *bt;
    char *expr = "A(B(C), D(E(F, G), H(, I)))";
    initBTree(&bt);
    createBTree(&bt, expr);

    printf("廣義表: "); printBTree(bt); printf("\n");
    printf("前序: "); preOrder(bt); printf("\n");
    printf("中序: "); inOrder(bt); printf("\n");
    printf("後序: "); postOrder(bt); printf("\n");
    printf("層序: "); levelOrder(bt); printf("\n");
    printf("深度: %d\n", BTreeDepth(bt));

    // BST 測試
    elemType arr[] = {30,50,20,40,25,70,54,23,80,92};
    struct BTreeNode *bst = NULL;
    createBSTree(&bst, arr, 10);
    printf("BST 中序(應有序): "); inOrder(bst); printf("\n");

    clearBTree(&bt);
    clearBTree(&bst);
    return 0;
}