二叉樹基本操作完整指南

一、數據結構定義

struct BiTree {
    char data;
    struct BiTree *lchild, *rchild;
};

二、先序序列創建二叉樹

輸入格式：先序遍歷序列，# 表示空節點。
遞歸構建：讀取字符，若為 # 返回 NULL，否則創建節點，遞歸構建左右子樹。

struct BiTree* createBiTree(struct BiTree *bt) {
    char ch = getchar();
    if (ch == '#') {
        bt = NULL;
    } else {
        bt = (struct BiTree*)malloc(sizeof(struct BiTree));
        bt->data = ch;
        bt->lchild = createBiTree(bt->lchild);
        bt->rchild = createBiTree(bt->rchild);
    }
    return bt;
}

三、深度優先遍歷（遞歸實現）

四、層序遍歷（廣度優先，隊列實現）

使用靜態數組模擬循環隊列：

#define MAX 100
struct BiTree* Queue[MAX];
int front = 0, rear = 0;

void levelOrder(struct BiTree *bt) {
    if (!bt) return;
    Queue[rear++] = bt;
    while (front != rear) {
        struct BiTree *p = Queue[front++];
        printf("%c ", p->data);
        if (p->lchild) Queue[rear++] = p->lchild;
        if (p->rchild) Queue[rear++] = p->rchild;
    }
}

五、完整主程序

int main() {
    struct BiTree *bt = NULL;
    printf("請按先序輸入二叉樹（# 表示空節點）：\n");
    bt = createBiTree(bt);
    
    printf("先序: "); preOrder(bt); printf("\n");
    printf("中序: "); inOrder(bt); printf("\n");
    printf("後序: "); postOrder(bt); printf("\n");
    printf("層序: "); levelOrder(bt); printf("\n");
    return 0;
}

測試示例

輸入：ABD##E##CF##G##（對應樹：A 根，左子樹 B(D,E)，右子樹 C(F,G)）

先序: A B D E C F G
中序: D B E A F C G
後序: D E B F G C A
層序: A B C D E F G

複雜度與注意事項

• 時間：所有遍歷 O(n)，n 為節點數。
• 空間：遞歸遍歷 O(h) 棧空間（h 為樹高），層序 O(w) 隊列空間（w 為最大寬度）。
• 輸入緩衝區：getchar() 會讀取換行符，實際使用時需處理（如 scanf(" %c", &ch) 跳過空白）。
• 內存釋放：程序結束前應遞歸釋放所有節點（此處省略）。