——本節(jié)內(nèi)容為Bilibili王道考研《數(shù)據(jù)結構》P43~P45視頻內(nèi)容筆記。

成都創(chuàng)新互聯(lián)主要從事成都做網(wǎng)站、成都網(wǎng)站設計、網(wǎng)頁設計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務。立足成都服務花垣,十多年網(wǎng)站建設經(jīng)驗,價格優(yōu)惠、服務專業(yè),歡迎來電咨詢建站服務:028-86922220

---

目錄

一、二叉樹的先中后序遍歷

1.先中后序遍歷

2.舉例

3.先中后序遍歷和前中后綴的關系

4.代碼實現(xiàn)

5.求遍歷序列

6.應用：求樹的深度

二、二叉樹的層次遍歷

1.層次遍歷

2.算法思想：

3.算法演示：

4.代碼實現(xiàn)：

三、由遍歷序列構造二叉樹

1.遍歷序列構造二叉樹

2.前序+中序

3.后序+中序

4.層序+中序

---

一、二叉樹的先中后序遍歷 1.先中后序遍歷

（1）二叉樹的遞歸特性：

①要么是個空二叉樹；

②要么是由“根結點+左子樹+右子樹”組成的二叉樹。

（2）基于此，給出三種遍歷方式：

①先序遍歷（先根遍歷）：根左右（NLR）

? ②中序遍歷（中根遍歷）：左根右（LNR）

? ③后序遍歷（后根遍歷）：左右根（LRN）

（3）先序遍歷、中序遍歷、后序遍歷

①先序遍歷：

先訪問根結點，再訪問該根結點的左子樹結點，最后訪問該根結點的右子樹結點；如果其左子樹或右子樹為分支結點，則需要對分支結點再進行一遍先序遍歷，這種訪問方式也是一種遞歸方式。

②中序遍歷：

? 先訪問根結點的左子樹結點，再訪問根結點，最后訪問根結點的右子樹結點；如果其左子樹或右子樹為分支結點，則需要對分支結點再進行一遍中序遍歷。

③后序遍歷：

先訪問根結點的左子樹結點，再訪問根結點的右子樹結點，最后訪問根結點；如果其左子樹或右子樹為分支結點，則需要對分支結點再進行一遍后序遍歷。

---

2.舉例

---

3.先中后序遍歷和前中后綴的關系

（1）先來看一個例子：

（2）求其先中后序遍歷遍歷序列分別為：

①先序遍歷：；

②中序遍歷：；

③后序遍歷：；

（3）求其前中后綴表達式：

①前綴表達式：；

②中綴表達式：；

③后綴表達式：；

（4）觀察（2）（3）可得在算術表達式“分析樹”中所得到的先中后序遍歷即為該算術表達式的前中后綴表達式，只不過其中中綴表達式要自己加界限符。

---

4.代碼實現(xiàn)

（1）先序遍歷代碼：

若二叉樹為空，則什么也不做；

若二叉樹非空：①訪問根結點；

②先序遍歷左子樹；

③先序遍歷右子樹。

typedef struct BiTNode {
	int data;
	struct BiTNode* lchild, * rchild;
}BiTNode,*BiTree;

void PreOrder(BiTree T)
{
	if (T != NULL)
	{
		visit(T);                訪問根結點，visit()執(zhí)行相關訪問操作的函數(shù)，比如打印...
		PreOrder(T->lchild);     //遞歸遍歷左子樹
		PreOrder(T->rchild);     //遞歸遍歷右子樹
	}
}

（2）中序遍歷代碼：

若二叉樹為空，則什么也不做；

若二叉樹非空：①中序遍歷左子樹；

②訪問根結點；

③中序遍歷右子樹。

void InOrder(BiTree T)
{
	if (T != NULL)
	{
		InOrder(T->lchild);		//遞歸遍歷左子樹
		visit(T);				//訪問根結點
		InOrder(T->rchild);		//遞歸遍歷右子樹
	}
}

（3）后序遍歷代碼：

若二叉樹為空，則什么也不做；

若二叉樹非空：①后序遍歷左子樹；

②后序遍歷右子樹；

③訪問根結點。

void PostOrder(BiTree T)
{
	if (T != NULL)
	{
		PostOrder(T->lchild);	//遞歸遍歷左子樹
		PostOrder(T->rchild);	//遞歸遍歷右子樹
		visit(T);				//訪問根結點
	}
}

---

5.求遍歷序列

（1）求先序遍歷序列

（2）求中序遍歷序列

（3）求后序遍歷序列?

---

6.應用：求樹的深度

后序遍歷算法變種之求樹的深度：

int treeDepth(BiTree T)
{
	if (T == NULL)
		return 0;
	else
	{
		int l = treeDepth(T->lchild);
		int r = treeDepth(T->rchild);
		return l >r ? l + 1 : r + 1;		//樹的深度=Max(左子樹深度,右子樹深度)+1
	}
}

---

二、二叉樹的層次遍歷 1.層次遍歷

如圖所示，層次遍歷即一層一層訪問數(shù)的結點：A B C D E F G H I J K L；

---

2.算法思想：

（1）初始化一個輔助隊列；

（2）根結點入隊；

（3）若隊列非空，則隊頭結點出隊，并訪問該結點，然后將其左、右子樹結點插入隊尾（如果有的話）。

---

3.算法演示：

---

4.代碼實現(xiàn)：

//二叉樹的結點（鏈式存儲）
typedef struct BiTNode {
	char data;
	struct BiTNode* lchild, * rchild;
}BiTNode,*BiTree;

//鏈式隊列結點
typedef struct LinkNode {
	BiTNode* data;                  //存指針而不是結點，節(jié)省內(nèi)存空間
	struct LinkNode* next;
}LinkNode;

typedef struct {
	LinkNode* front, * rear;		//隊頭隊尾指針
}LinkQueue;

//層序遍歷
void LevelOrder(BiTree T)
{
	LinkQueue Q;
	InitQueue(Q);						//初始化輔助隊列
	BiTree p;
	EnQueue(Q, T);						//將根結點入隊
	while (!IsEmpty(Q))					//隊列不空則循環(huán)
	{
		DeQueue(Q, p);					//對頭結點出隊
		visit(p);						//訪問出隊結點
		if (p->lchild != NULL)
			EnQueue(Q, p->lchild);		//左孩子入隊
		if (p->rchild != NULL)
			EnQueue(Q, p->rchild);		//右孩子入隊
	}
}

---

三、由遍歷序列構造二叉樹 1.遍歷序列構造二叉樹

（1）若只給出一棵二叉樹的前/中/后/層序遍歷中的一種，不能確定唯一一棵二叉樹。

（2）由遍歷序列構造二叉樹需要：

? ①前序+中序遍歷序列；

或②后序+中序遍歷序列；

或③層序+中序遍歷序列；

---

2.前序+中序

（1）方法：

①由前序遍歷序列判斷出根結點；

②由根結點在中序遍歷序列中的位置判斷出左子樹和右子樹的前序和中序遍歷序列；

③分別對左右子樹的前序和中序遍歷序列再進行①②的分析判斷出所有的結點；

（2）舉例：

①由前序遍歷序列第一個D判斷出D為根結點，其所在中序遍歷序列的位置判斷出：

左子樹中序序列：EAF；前序序列：AEF；

? 右子樹中序序列：HCBGI；前序序列：BCHGI；

如下圖：

②由左子樹前序序列判斷左子樹根結點為A，由其所在左子樹中序序列的位置判斷出：

? 根結點A的左子樹為E；右子樹為F；

③由右子樹前序序列判斷右子樹根結點為B，由其所在右子樹中序序列的位置判斷出：

? 根結點B的左子樹中序序列為HC；前序序列為CH；

? 根結點B的右子樹中序序列為GI；前序序列為GI；

如下圖：

④由所示橘色結點的前序序列CH判斷這里的根結點為C；由C所在中序序列的位置判斷出H為C的左子樹結點；

⑤由所示綠色結點的前序序列GI判斷這里的根結點為G；由G所在中序序列的位置判斷出I為G的右子樹結點；

如下圖：

---

3.后序+中序

（1）方法

①由后序遍歷序列判斷出根結點；

②由根結點在中序遍歷序列中的位置判斷出左子樹和右子樹的后序和中序遍歷序列；

③分別對左右子樹的后序和中序遍歷序列再進行①②的分析判斷出所有的結點；

（2）舉例：

①由后序遍歷序列判斷出根結點為D；由D在中序序列的位置判斷出：

D的左子樹中序序列：EAF；后序序列：EFA；

? D的右子樹中序序列：HCBGI；后序序列：HCIGB；

如下圖：

②由圖中橘色部分后序序列EFA判斷出這里的根結點為A；由A在中序序列EAF所在位置判斷出A的左子樹結點為E，右子樹結點為F；

③由圖中綠色部分后序序列HCIGB判斷出這里的根結點為B；由B在中序序列HCBGI所在位置判斷出：

B的左子樹結點的中序序列：HC；后序序列：HC；

? B的右子樹結點的中序序列：GI；后序序列：IG；

如下圖：

④由橘色部分后序序列HC判斷這里的根結點為C，由C在中序序列的位置判斷H為C的左子樹結點；

⑤由綠色部分后序序列IG判斷這里的根結點為G，由G在中序序列的位置判斷I為G的右子樹結點；

如下圖：

---

4.層序+中序

（1）方法：

①由層序遍歷序列判斷根結點；

②由根結點在中序序列中的位置判斷根結點的左右子樹的中序序列（注意可能會有空樹的情況）；

③由層序遍歷序列判斷下一層的根結點；

④由下一層根結點在中序序列中的位置判斷下一層根結點的左右子樹的中序序列（注意空樹）；

⑤反復以上分析，判斷出所有的結點；

（2）舉例：

①由層序遍歷序列判斷D為根結點；由D所在中序序列中的位置判斷：

D的左子樹中序序列：EAF；右子樹中序序列：HCBGI；

如下圖：

②由層序遍歷序列判斷第二層的根結點分別為A和B；由A和B在中序序列中的位置判斷：

? A的左子樹結點為E，右子樹結點為F；

? B的左子樹中序序列為HC，右子樹中序序列為GI；

如下圖：

③上圖所示，第三層分別為：E、F、HC中出一個、GI中出一個；

④由層序序列判斷HC中出C，GI中出G；

⑤最后由中序序列判斷H為C的左子樹結點；I為G的右子樹結點，如下圖：

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

標題名稱：數(shù)據(jù)結構——二叉樹的先中后序遍歷-創(chuàng)新互聯(lián)
標題鏈接：http://sd-ha.com/article14/podge.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供標簽優(yōu)化、營銷型網(wǎng)站建設、網(wǎng)站制作、定制開發(fā)、網(wǎng)站改版、小程序開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)