使用層次序列構建二叉樹（C語言實現）

在數據結構學習過程中，二叉樹的構建方式通常有遞歸建樹（前序/中序）和層次建樹（廣度優先）兩種。本文將介紹一種基于輔助隊列實現的層次建樹方法，并結合前序、中序、后序遍歷結果來驗證構建的正確性。

---

🌳 示例結構

輸入層次序列：a b c d e f g

預期構建出的二叉樹結構如下：

        a/   \b     c/ \   / \d   e f   g

---

🧠 思路解析

層次建樹的關鍵是 廣度優先遍歷的順序插入節點。為了實現這一目標，我們需要：

• 使用一個結構體指針隊列，保存待填左右孩子的節點。
• 每讀入一個字符，就創建一個新樹節點，并嘗試插入到當前隊首節點的左或右孩子位置。
• 如果左右孩子都已填滿，就將當前隊首出隊，指向下一個節點。

---

🛠? 關鍵數據結構

// 樹節點結構體
typedef struct BiTNode {char data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;// 輔助隊列節點（保存 BiTree 指針）
typedef struct tag {BiTNode *p;struct tag *pnext;
} tag_t, *ptag_t;

---

🧩 核心建樹邏輯

BiTree tree = NULL; // 根節點
ptag_t phead = NULL, ptail = NULL, listpnew = NULL, pre = NULL;
char c;while(scanf("%c", &c)) {if(c == '\n') break;BiTree pnew = (BiTree)calloc(1, sizeof(BiTNode));pnew->data = c;listpnew = (ptag_t)calloc(1, sizeof(tag_t));listpnew->p = pnew;if(tree == NULL) {tree = pnew;phead = ptail = listpnew;pre = listpnew;} else {ptail->pnext = listpnew;ptail = listpnew;if(pre->p->lchild == NULL) {pre->p->lchild = pnew;} else if(pre->p->rchild == NULL) {pre->p->rchild = pnew;pre = pre->pnext; // 移動到下一個節點}}
}

---

🔁 遍歷驗證

前序遍歷（PreOrder）：

void PreOrder(BiTree p) {if(p != NULL) {printf("%c", p->data);PreOrder(p->lchild);PreOrder(p->rchild);}
}

中序遍歷（InOrder）：

void InOrder(BiTree p) {if(p != NULL) {InOrder(p->lchild);printf("%c", p->data);InOrder(p->rchild);}
}

后序遍歷（PostOrder）：

void PostOrder(BiTree p) {if(p != NULL) {PostOrder(p->lchild);PostOrder(p->rchild);printf("%c", p->data);}
}

---

完整代碼

//層次建樹   借助一個輔助隊列
//          a
//        b   c
//    d   e   f   g#include <iostream>
#include<stdio.h>
#include<stdlib.h>//借助輔助隊列來進行建樹
typedef struct LinkNode{char datac; //數據結點}LinkNode; //建立一個結點//這里沒有使用標準的鏈隊列來實現 相應的層次建樹
typedef struct {LinkNode *front, *rear;
}LinkQueue;   //建立隊列#建立數的結點  使用的是鏈式的存儲typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;
}BiTNode , * BiTree;//而是建立一個輔助隊列 tag
typedef struct tag{
//    BiTree p;  //樹的某一結點的地址值BiTNode *p;struct tag *pnext;}tag_t , *ptag_t;//前序遍歷
void PreOrder(BiTree p){if(p!=NULL){printf("%c",p->data);PreOrder(p->lchild);PreOrder(p->rchild);}}//中序遍歷
void InOrder(BiTree p){if(p!=NULL){InOrder(p->lchild);printf("%c",p->data);InOrder(p->rchild);}}//后序遍歷
void PostOrder(BiTree p){if(p!=NULL){PostOrder(p->lchild);PostOrder(p->rchild);printf("%c",p->data);}
}int main() {BiTree pnew; //用來指向新申請的數結點BiTree tree =NULL; //tree 是指向樹根的，代表樹ptag_t phead= NULL,ptail =NULL, listpnew =NULL, pre =NULL; //初始化隊列 定義一個pre 指向執行的當前元素char c;//abcdefwhile(scanf("%c",&c)){if(c=='\n'){break;}//calloc申請空間  大小是兩個參數相乘，并對空間進行初始化  賦值為0;//malloc 申請以后還需要對其進行賦值 malloc 返回的是 void * 類型的 也需要進行強制轉換樹申請結點pnew =(BiTree) calloc(1,sizeof(BiTNode));pnew->data = c;//隊列結點申請空間listpnew = (ptag_t) calloc(1,sizeof(tag_t));  //申請一個結構體類型的結點 返回一個指針類型的listpnew->p =pnew;//如果是數的第一個結點if(tree==NULL){tree = pnew;  //tree 指向根的頭結點//第一個結點 即是隊列頭也是 隊列尾phead = ptail = listpnew;pre = listpnew; //  用來判斷當前結點 的左右孩子是否滿了}else {//元素直接入隊ptail ->pnext = listpnew;ptail =listpnew;//接下來把元素放入樹中if(pre->p->lchild ==NULL){pre ->p ->lchild =pnew;  // pre -> p 左孩子為空 就放入左孩子}else if(pre->p->rchild==NULL){pre->p->rchild =pnew;pre = pre->pnext;  // !!! 左右孩子都滿了，指向下一個節點}}}PreOrder(tree);printf("\n");InOrder(tree);printf("\n");PostOrder(tree);return 0;//這沒有對樹進行相應的輸出  ，使用調試發現建樹完成
}
//D:\TextOPT\C_CPP_code\For408\DateS\5\SqBinaryTree1\cmake-build-debug\SqBinaryTree1.exe
//123456789
//124895367
//849251637
//894526731

📌 完整輸出樣例

以輸入：abcdefg（按層次順序輸入，以回車結束）為例：

輸入：
abcdefg?輸出：
前序遍歷：abdecfg
中序遍歷：dbeafcg
后序遍歷：debgfca

輸出對應的樹結構：

        a/   \b     c/ \   / \d   e f   g

---

? 總結

• 使用輔助隊列可以按層次方式構建二叉樹，代碼邏輯清晰，效率也較高。
• 在建樹過程中，記得及時更新隊列指針（例如 pre = pre->pnext;）以避免插入錯誤。
• 可結合三種遍歷結果驗證建樹的正確性。

---