數據結構實戰：C 語言實現二叉樹順序存儲（含完整可運行代碼與操作演示）

順序存儲核心思想

利用數組下標隱式表示父子關系：根節點存 T[0]，節點 i 的左子節點在 2i+1，右子節點在 2i+2，父節點在 (i-1)/2。適用於完全二叉樹或滿二叉樹；一般二叉樹需用特殊值（如空格 ' '）標記空節點，可能造成空間浪費。

核心數據結構定義

#define MAX_TREE_SIZE 100
typedef char TElemType;
typedef TElemType SqBiTree[MAX_TREE_SIZE];  // 0號單元存根節點
TElemType Nil = ' ';  // 空節點標記

typedef struct { int level, order; } position;  // (層號, 本層序號)

關鍵操作實現精選

初始化與創建

void InitBiTree(SqBiTree T) {
    for (int i = 0; i < MAX_TREE_SIZE; ++i) T[i] = Nil;
}

// 按層序輸入創建（輸入 '#' 表示空節點）
void CreateBiTree(SqBiTree T) {
    char ch; int i = 0;
    while ((ch = getchar()) != '\n' && i < MAX_TREE_SIZE) {
        if (ch != '#') T[i] = ch;
        ++i;
    }
}

深度計算（利用完全二叉樹性質）

int BiTreeDepth(SqBiTree T) {
    if (T[0] == Nil) return 0;
    int i = MAX_TREE_SIZE - 1;
    while (T[i] == Nil) --i;  // 找最後非空節點
    int depth = 0;
    while (i >= 0) { i = (i - 1) / 2; ++depth; }  // 往上跳至根
    return depth;
}

遍歷算法（遞歸下標法）

void PreTraverse(SqBiTree T, int i, void (*Visit)(TElemType)) {
    if (T[i] == Nil) return;
    Visit(T[i]);
    PreTraverse(T, 2*i+1, Visit);
    PreTraverse(T, 2*i+2, Visit);
}

void LevelOrderTraverse(SqBiTree T, void (*Visit)(TElemType)) {
    int i = MAX_TREE_SIZE - 1;
    while (T[i] == Nil) --i;
    for (int j = 0; j <= i; ++j)
        if (T[j] != Nil) Visit(T[j]);
}

插入與刪除子樹（利用輔助隊列）

插入：將原子樹遷移為新子樹的右子樹，再掛接新子樹。刪除：層序遍歷待刪子樹根，入隊所有後代下標，逐個置 Nil。

完整可運行主程序功能演示

• 創建樹 → 輸出深度、根節點
• 四種遍歷：先序、中序、後序、層序
• 查詢節點：值、雙親、左右孩子、左右兄弟
• 修改節點值、插入子樹、刪除子樹、逐層打印
• 清空樹驗證

效果圖說明

截圖展示了交互式菜單操作流程與各功能輸出結果，驗證代碼完整性。

優缺點總結

適用場景建議

• 堆、完全二叉樹、靜態決策樹等結構固定、節點稠密的場景
• 教學演示、嵌入式環境無動態分配能力時
• 一般業務二叉樹請優先使用鏈式存儲（動態分配節點）