資料結構：二叉樹順序與鏈式儲存結構詳解

資料結構：二叉樹順序與鏈式儲存結構詳解

順序儲存結構

適用於完全二叉樹。按層次編號 (根為 1)，節點 i 儲存於陣列下標 i-1。

#define MAX_SIZE 100
typedef TElemType SqBiTree[MAX_SIZE];

一般二叉樹需補齊空節點對應完全二叉樹位置，空間浪費大，適合滿/完全二叉樹 (如堆)。

鏈式儲存結構

1. 二叉鏈表 (最常用)

typedef struct BTNode {
    ElemType data;
    struct BTNode *Lchild, *Rchild;
} BTNode;

三域：資料、左孩子指標、右孩子指標。

2. 三叉鏈表

typedef struct BTNode_3 {
    ElemType data;
    struct BTNode_3 *Lchild, *Rchild, *parent;
} BTNode_3;

增加父節點指標，便於向上遍歷。

遍歷二叉樹 基礎概念

• 定義：按指定規律訪問所有節點，每節點恰好一次
• 訪問：對節點處理 (輸出、修改等)
• 六種排列：DLR, LDR, LRD, DRL, RDL, RLD。約定先左後右 → 三種主流：

已知先序+中序 或 後序+中序 可唯一確定二叉樹。

先序遍歷算法

遞歸版

void PreorderTraverse(BTNode *T) {
    if (T == NULL) return;
    visit(T->data);
    PreorderTraverse(T->Lchild);
    PreorderTraverse(T->Rchild);
}

非遞歸版 (堆疊)

#define MAX_STACK_SIZE 50
void PreorderTraverse(BTNode *T) {
    BTNode *Stack[MAX_STACK_SIZE], *p = T, *q;
    int top = 0;
    if (T == NULL) { printf("Empty!\n"); return; }
    do {
        visit(p->data);
        q = p->Rchild; if (q != NULL) Stack[top++] = q;
        p = p->Lchild;
        if (p == NULL && top != 0) { top--; p = Stack[top]; }
    } while (p != NULL);
}