您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C 語言實作二元樹基本操作完整指南

編輯：關於C

前言

二元樹是資料結構的核心主題，其遞迴特性使得大多數操作（建立、遍歷、搜尋、刪除）皆以遞迴實作最為自然。本文提供一個完整、可編譯執行的 C 語言二元樹基本操作實作，涵蓋初始化、建立、清除、深度計算、節點搜尋、插入、刪除子樹、尋找父節點/左子節點/左兄弟等核心功能。

資料結構定義

#define MAX 100
#define ERROR 0
#define OK 1

#ifndef Type
typedef char Type;  // 節點資料型別，預設為 char
#endif

typedef struct Bitree {
    Type data;
    struct Bitree *lchild;
    struct Bitree *rchild;
} BitNode, *BiTree;

核心函數實作

1. 初始化空樹

int InitBiTree(BiTree *T) {
    *T = NULL;
    return OK;
}

關鍵點：傳遞 BiTree*（指向指標的指標），以便在函數內修改呼叫端的樹根指標。

2. 遞迴建立樹（前序輸入，空格代表空節點）

int CreatBiTree(BiTree *T) {
    Type ch;
    scanf("%c", &ch);
    if (ch == ' ') {
        *T = NULL;
    } else {
        *T = (BiTree)malloc(sizeof(BitNode));
        (*T)->data = ch;
        CreatBiTree(&(*T)->lchild);
        CreatBiTree(&(*T)->rchild);
    }
    return OK;
}

3. 遞迴清除樹（後序釋放記憶體）

int ClearBiTree(BiTree *T) {
    if ((*T)->lchild) ClearBiTree(&(*T)->lchild);
    if ((*T)->rchild) ClearBiTree(&(*T)->rchild);
    if ((*T)->lchild == NULL && (*T)->rchild == NULL) {
        free(*T);
        *T = NULL;
    }
    return OK;
}

4. 判斷樹是否為空

int BiTreeEmpty(BiTree T) {
    return (T == NULL) ? OK : ERROR;
}

5. 計算樹的深度

int BiTreeDepth(BiTree T) {
    if (T == NULL) return 0;
    int hl = BiTreeDepth(T->lchild);
    int hr = BiTreeDepth(T->rchild);
    return (hl > hr ? hl : hr) + 1;
}

6. 取得根節點資料

BitNode Root(BiTree T) {
    if (T == NULL) { printf("No Root"); exit(0); }
    return *T;
}

7. 二元搜尋樹插入（依字元大小序）

int InserInc(BiTree *T, Type e) {
    BiTree temp = (BiTree)malloc(sizeof(BitNode));
    temp->data = e; temp->lchild = temp->rchild = NULL;
    if (*T == NULL) { *T = temp; return OK; }
    if (e < (*T)->data) return InserInc(&(*T)->lchild, e);
    else return InserInc(&(*T)->rchild, e);
}

8. 搜尋指定值節點

BiTree Search(BiTree T, Type val) {
    if (T == NULL) return NULL;
    if (T->data == val) return T;
    BiTree res = Search(T->lchild, val);
    return res ? res : Search(T->rchild, val);
}

9. 刪除指定節點的左/右子樹

int DeleteChild(BiTree *T, BiTree target, int flag) {
    BiTree tar = Search(*T, target->data);
    if (!tar) return ERROR;
    if (flag == 0) { ClearBiTree(&tar->lchild); tar->lchild = NULL; }
    else { ClearBiTree(&tar->rchild); tar->rchild = NULL; }
    return OK;
}

10. 尋找父節點、左子節點、左兄弟

// 父節點
BiTree Parent(BiTree T, Type e) {
    if (!T) return NULL;
    if ((T->lchild && T->lchild->data == e) || (T->rchild && T->rchild->data == e)) return T;
    BiTree p = Parent(T->lchild, e);
    return p ? p : Parent(T->rchild, e);
}

// 左子節點
BiTree LeftChild(BiTree T, Type e) {
    if (!T) return NULL;
    if (T->data == e) return T->lchild;
    BiTree res = LeftChild(T->lchild, e);
    return res ? res : LeftChild(T->rchild, e);
}

// 左兄弟（右子樹的左兄弟是左子樹根）
BiTree LeftSibling(BiTree T, Type e) {
    if (!T->lchild || !T->rchild) return NULL;
    if (T->lchild->data == e) return T->rchild;
    BiTree res = LeftSibling(T->lchild, e);
    return res ? res : LeftSibling(T->rchild, e);
}

主程式測試範例

int main() {
    BiTree T; BitNode root; BiTree temp;
    CreatBiTree(&T);  // 輸入範例：A B  C  D  (空格代表空節點)
    // 測試各功能...
    temp = LeftSibling(T, 'a');
    return 0;
}