數(shù)據(jù)結(jié)構(gòu)第五章第一頁，共六十七頁，2022年，8月28日樹的基本概念二叉樹遍歷二叉樹線索二叉樹樹的應(yīng)用特點(diǎn)：非線性結(jié)構(gòu)，一個直接前驅(qū)，但可能有多個直接后繼。（一對多或1:n）二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)二叉樹的運(yùn)算第二頁，共六十七頁，2022年，8月28日樹適于反應(yīng)層次關(guān)系的數(shù)據(jù)對象的研究。層次化的數(shù)據(jù)之間可能有:祖先—后代、上級—下級、整體—部分等其它類似的關(guān)系。學(xué)院法學(xué)院工商學(xué)院信息學(xué)院金融學(xué)院人文學(xué)院會計(jì)學(xué)院財(cái)稅學(xué)院計(jì)算機(jī)系信息系統(tǒng)計(jì)系圖5.1.1一棵學(xué)院信息的樹第三頁，共六十七頁，2022年，8月28日5.1.1樹的定義

由一個或多個(n≥0)結(jié)點(diǎn)組成的有限集合T，有且僅有一個結(jié)點(diǎn)稱為根（root）當(dāng)n>1時，其余的結(jié)點(diǎn)分為m(m≥0)個互不相交的有限集合T1,T2，…，Tm。每個集合本身又是棵樹，被稱作這個根的子樹。樹的定義具有遞歸性，即“樹中還有樹”。第四頁，共六十七頁，2022年，8月28日一棵樹至少包含一個樹結(jié)點(diǎn)，不存在不含樹結(jié)點(diǎn)的樹；樹中結(jié)點(diǎn)存在著層次關(guān)系，但同一層上的樹結(jié)點(diǎn)之間是無序的。一棵樹的每個結(jié)點(diǎn)都是某個子樹的根。第五頁，共六十七頁，2022年，8月28日若干術(shù)語——（也稱父親）即上層的那個結(jié)點(diǎn)(直接前驅(qū))——即下層結(jié)點(diǎn)的子樹的根(直接后繼)——同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）——即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）——即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)——即該結(jié)點(diǎn)下層子樹中的任一結(jié)點(diǎn)ABCGEIDHFJFLK根葉子森林有序樹無序樹——即根結(jié)點(diǎn)(沒有前驅(qū))——即終端結(jié)點(diǎn)(沒有后繼)——指m棵不相交的樹的集合(例如刪除A后的子樹個數(shù))雙親孩子兄弟堂兄弟祖先子孫——結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一）——結(jié)點(diǎn)各子樹可互換位置。第六頁，共六十七頁，2022年，8月28日——即樹的數(shù)據(jù)元素——結(jié)點(diǎn)掛接的子樹數(shù)結(jié)點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的層次終端結(jié)點(diǎn)分支結(jié)點(diǎn)樹的度樹的深度(或高度)ABCGEIDHFJFLK——從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）——即度為0的結(jié)點(diǎn)，即葉子——即度不為0的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)）——所有結(jié)點(diǎn)度中的最大值（Max{各結(jié)點(diǎn)的度}）——指所有結(jié)點(diǎn)中最大的層數(shù)（Max{各結(jié)點(diǎn)的層次}）問：右上圖中的結(jié)點(diǎn)數(shù)＝；樹的度＝；樹的深度＝1334（有幾個直接后繼就是幾度，亦稱“次數(shù)”）第七頁，共六十七頁，2022年，8月28日ABCDEFGHIJKLM結(jié)點(diǎn)A的度：?結(jié)點(diǎn)B的度：?結(jié)點(diǎn)M的度：?葉子：?結(jié)點(diǎn)A的孩子：?結(jié)點(diǎn)B的孩子：?結(jié)點(diǎn)I的雙親：?結(jié)點(diǎn)L的雙親：?結(jié)點(diǎn)B，C，D為?結(jié)點(diǎn)K，L為?樹的度：?結(jié)點(diǎn)A的層次：?結(jié)點(diǎn)M的層次：?樹的深度：?結(jié)點(diǎn)F，G為?結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的?320B，C，DE，F(xiàn)314K，L，F(xiàn)，G，M，I，JDE兄弟兄弟4堂兄弟祖先第八頁，共六十七頁，2022年，8月28日5.2.1二叉樹的定義定義：二叉樹是n(n0)個結(jié)點(diǎn)的有限集，它或?yàn)榭諛?n=0)，或由一個根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成特點(diǎn)每個結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn))二叉樹的子樹有左、右之分，且其次序不能任意顛倒基本形態(tài)A只有根結(jié)點(diǎn)的二叉樹空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空第九頁，共六十七頁，2022年，8月28日2.

二叉樹的定義與樹的定義的區(qū)別二叉樹存在著空樹；但樹不能為空。二叉樹中的每一個結(jié)點(diǎn)只可能有0個，1個或2個孩子，也就是說，二叉樹不存在度大于2的結(jié)點(diǎn)；而樹中的每個結(jié)點(diǎn)可以有多個子樹。二叉樹的子樹有左右之分，兩者不能顛倒；但樹的子樹一般是無序的。除以上區(qū)別外，上一節(jié)引入樹的有關(guān)術(shù)語對于二叉樹也適用。第十頁，共六十七頁，2022年，8月28日3.滿二叉樹的定義 若二叉樹中所有分枝結(jié)點(diǎn)的度數(shù)都為2，且葉子結(jié)點(diǎn)都在同一層上，則稱這類二叉樹為滿二叉樹。5.完全二叉樹的定義若二叉樹中所有分枝結(jié)點(diǎn)的度數(shù)要就為2，要就為0，稱這類二叉樹為完全二叉樹。4.順序二叉樹的定義:

對滿二叉樹從上至下，從左至右地從1開始編號，結(jié)果是每個結(jié)點(diǎn)都可以與滿二叉樹中編號為1至n的結(jié)點(diǎn)一一對應(yīng)6.退化二叉樹的定義:

如果一棵非空的二叉樹只有一個葉子，且其余結(jié)點(diǎn)均只有一個孩子第十一頁，共六十七頁，2022年，8月28日ABCDEFG圖5.2.2一棵滿二叉樹123456789101112圖5.2.4一棵順序二叉樹圖5.2.5一棵非順序二叉樹12345678912圖5.2.8退化的二叉樹AIDB12472852(a)(b)第十二頁，共六十七頁，2022年，8月28日5.2.2二叉樹的性質(zhì)

性質(zhì)1:在二叉樹的第i層上最多有2i-1個結(jié)點(diǎn)（i≥1）。用歸納法證明它。當(dāng)i=1時，21-1=1，這時只有一個根結(jié)點(diǎn)，顯然結(jié)論是正確的。假設(shè)，對于所有的j（1≤j<i）結(jié)論也成立，即第j層上至多有2j-1個結(jié)點(diǎn)，那么，我們也可以證明當(dāng)j=i時結(jié)論也成立，證明如下：由歸納法假設(shè)知道，第i-1層上至多有2i-2個結(jié)點(diǎn)，由于二叉樹的每個結(jié)點(diǎn)至多有兩個孩子，所以第i層上最大結(jié)點(diǎn)數(shù)應(yīng)為第i-1層上最大結(jié)點(diǎn)數(shù)的兩倍，即第i層上最多結(jié)點(diǎn)數(shù)為：2*2i-2=2i-1。故結(jié)論得證。第十三頁，共六十七頁，2022年，8月28日5.2.2二叉樹的性質(zhì)

性質(zhì)2:深度為h的二叉樹至多有2h-1個結(jié)點(diǎn)。可以由性質(zhì)1推出上述結(jié)論。顯然，深度為h的二叉樹的最大結(jié)點(diǎn)應(yīng)為各層最大結(jié)點(diǎn)之和即為：（第i層上的最大結(jié)點(diǎn)數(shù)）=2i-1=2h-1第十四頁，共六十七頁，2022年，8月28日5.2.2二叉樹的性質(zhì)

性質(zhì)3:包括n（n>0）個元素的二叉樹的邊數(shù)為n-1。證明：二叉樹中每個元素（除根結(jié)點(diǎn)外）有且僅有一個雙親結(jié)點(diǎn)。而孩子結(jié)點(diǎn)與雙親結(jié)點(diǎn)之間有且僅有一條邊，因此包含n個元素的二叉樹的邊數(shù)是n-1。第十五頁，共六十七頁，2022年，8月28日5.2.2二叉樹的性質(zhì)

1. 性質(zhì)1:在二叉樹的第i層上最多有2i-1個結(jié)點(diǎn)（i≥1）。性質(zhì)2:深度為h的二叉樹至多有2h-1個結(jié)點(diǎn)。性質(zhì)3:包括n（n>0）個元素的二叉樹的邊數(shù)為n-1。性質(zhì)4:對于任何一棵二叉樹，若其終端結(jié)點(diǎn)數(shù)為n0，其度為2的結(jié)點(diǎn)數(shù)為n2，則有：n0=n2+1。5.性質(zhì)5:若一棵滿二叉樹有n個結(jié)點(diǎn),則深度h第十六頁，共六十七頁，2022年，8月28日性質(zhì)6 一棵有n個結(jié)點(diǎn)的順序二叉樹，如從左至右、從上至下的，對每個結(jié)點(diǎn)從1開始編號，對于其中任意編號為i的結(jié)點(diǎn)（1≤i≤n）有：(1)若i1,則i的父親是i/2；若i=1，則i是根結(jié)點(diǎn)，無父親。(2)若2i≤n，則i的左孩子是2i；若2i>n，則i無左孩子。(3)若2i+1≤n，則i的右孩子是2i+1；若2i+1>n，則i無右孩子。第十七頁，共六十七頁，2022年，8月28日123114589126710圖5.2.9順序二叉樹父子關(guān)系152178525777ii+12i2i+12i+2i/2第十八頁，共六十七頁，2022年，8月28日3.深度為9的二叉樹中至少有

個結(jié)點(diǎn)。Ａ)２9

Ｂ)２8

Ｃ)９Ｄ)２9－12.深度為Ｋ的二叉樹的結(jié)點(diǎn)總數(shù)，最多為

個。Ａ)２k-1

Ｂ)log2kＣ)２k－１Ｄ)２k1.樹Ｔ中各結(jié)點(diǎn)的度的最大值稱為樹Ｔ的

。Ａ)高度Ｂ)層次Ｃ)深度Ｄ)度DCC課堂練習(xí)：第十九頁，共六十七頁，2022年，8月28日

4：具有3個結(jié)點(diǎn)的二叉樹可能有幾種不同形態(tài)？

第二十頁，共六十七頁，2022年，8月28日二叉樹的抽象數(shù)據(jù)類型Dset： 有限元素集合。Rset： 如果不空，被分為根結(jié)點(diǎn)、左子樹和右子樹；每個子樹仍然是一個二叉樹。OPSet：PreOrder(*BT)二叉樹的前序遍歷遞歸算法PreOrderN(*BT)二叉樹的前序遍歷非遞歸算法InOrder(*BT)二叉樹的中序遍歷遞歸算法InOrderN(*BT)二叉樹的中序遍歷非遞歸算法第二十一頁，共六十七頁，2022年，8月28日二叉樹的抽象數(shù)據(jù)類型PostOrder(*BT)二叉樹的后序遍歷遞歸算法PostOrderN(*BT)二叉樹的后序遍歷非遞歸算法LevelOrderTL(*BT)左至右，上至下層次遍歷LevelOrderTR(*BT))右至左，上至下層次遍歷MakeNode(&x)構(gòu)造結(jié)點(diǎn)MakeBinaryTree(*root,*left,*right)聯(lián)接三個結(jié)點(diǎn)為二叉樹BinaryHeight(*BT)求二叉樹的高度BinaryDelete(*BT)二叉樹的刪除算法第二十二頁，共六十七頁，2022年，8月28日5.3.1二叉樹的存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)按二叉樹的結(jié)點(diǎn)“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。ABCDEFGHI[0][1][2][3][4][5][6][7][8]問：順序存儲后能否復(fù)原成唯一對應(yīng)的二叉樹形狀？答：若是完全/滿二叉樹則可以做到唯一復(fù)原。而且有規(guī)律：下標(biāo)值為i的雙親，其左孩子的下標(biāo)值必為2(i+1)-1，其右孩子的下標(biāo)值必為2(i＋1)

例如，對應(yīng)[2]C的兩個孩子必為[5]和[6],即B的左孩子必是F,右孩子必為G。ABCGEIDHF012第二十三頁，共六十七頁，2022年，8月28日討論：不是完全二叉樹怎么辦？答：一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。AB^C^^^D^…E[0][1][2][3][4][5][6][7][8].[15]ABECD缺點(diǎn)：①浪費(fèi)空間；②插入、刪除不便

第二十四頁，共六十七頁，2022年，8月28日二、鏈?zhǔn)酱鎯Y(jié)構(gòu)

用二叉鏈表即可方便表示。dataleft_childright_childdataleft_childright_childtypedefstruct

BinaryTreeNode{ EType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;}BinaryTreeNode；一般從根結(jié)點(diǎn)開始存儲。

（相應(yīng)地，訪問樹中結(jié)點(diǎn)時也只能從根開始）注：如果需要倒查某結(jié)點(diǎn)的雙親，可以再增加一個雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。第二十五頁，共六十七頁，2022年，8月28日優(yōu)點(diǎn)：①不浪費(fèi)空間；②插入、刪除方便

ABCDEFG

AB

C

D

E

F

G^^^^^^^^第二十六頁，共六十七頁，2022年，8月28日問：含有n個結(jié)點(diǎn)的二叉樹中，共有鏈接域有2n個，空閑的（不用的）鏈接域有n+1個（為什么？）證明：根據(jù)性質(zhì)4：n0=n2+1,有葉子結(jié)點(diǎn)空閑的鏈接域?yàn)?n2+2度為1的結(jié)點(diǎn)空閑的鏈接域?yàn)閚-n0-n2=n-2n2-1,則總的空閑鏈接域?yàn)?n0+n1=n+1第二十七頁，共六十七頁，2022年，8月28日5.4.4二叉樹的其它操作

構(gòu)造一棵二叉樹的結(jié)點(diǎn)BinaryTreeNode*MakeNode(EType&x) {//構(gòu)造結(jié)點(diǎn)

BinaryTreeNode *ptr; Ptr=newBinaryTreeNode; if(ptr) returnNULL; ptr->data=x; ptr->LChild=NULL; ptr->RChild=NULL; return ptr;}x=‘A’;BinaryTreeNode*Aptr=MakeNode(&x);

第二十八頁，共六十七頁，2022年，8月28日2)構(gòu)造一棵二叉子樹（或二叉樹）

voidMakeBinaryTree(BinaryTreeNode*root,BinaryTreeNode*left,BinaryTreeNode*right){//聯(lián)接root，left,right所指的結(jié)點(diǎn)指針為二叉樹

root->LChild=left; root->RChild=right;}第二十九頁，共六十七頁，2022年，8月28日ABCDEFG圖5.4.4一棵二叉樹

MakeBinaryTree(E,G,NULL); MakeBinaryTree(B,D,E); MakeBinaryTree(C,NULL,F); MakeBinaryTree(A,B,C);用MakeBinaryTree構(gòu)造下圖給出的樹。第三十頁，共六十七頁，2022年，8月28日5.4二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)下的操作5.4.1遍歷二叉樹遍歷定義——遍歷用途——遍歷方法——指按某條搜索路線遍訪每個結(jié)點(diǎn)且不重復(fù)（又稱周游）。它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。對每個結(jié)點(diǎn)的查看通常都是“先左后右”。TraversingBinaryTree第三十一頁，共六十七頁，2022年，8月28日遍歷規(guī)則———二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、L、R以根結(jié)點(diǎn)為參照系注：“前、中、后”的意思是指訪問的結(jié)點(diǎn)D是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。D、L、R的組合定義了六種可能的遍歷方案：LDR,LRD,DLR,DRL,RDL,RLD若限定先左后右，則有三種實(shí)現(xiàn)方案：

DLRLDRLRD前序遍歷中序遍歷后序遍歷

第三十二頁，共六十七頁，2022年，8月28日ADBCDLRADLRDLR>B>>D>>CDLR前序遍歷序列：ABDC前序遍歷:第三十三頁，共六十七頁，2022年，8月28日ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:第三十四頁，共六十七頁，2022年，8月28日ADBC

LRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:B第三十五頁，共六十七頁，2022年，8月28日+*A*/EDCB先序遍歷結(jié)果+**/ABCDE—前綴表示法中序遍歷結(jié)果A/B*C*D+E—中綴表示法后序遍歷結(jié)果AB/C*D*E+—后綴表示法例1：用二叉樹表示算術(shù)表達(dá)式先序遍歷結(jié)果中序遍歷結(jié)果后序遍歷結(jié)果層次遍歷結(jié)果第三十六頁，共六十七頁，2022年，8月28日ABCDEFGABCGEIDHF例1先序遍歷結(jié)果ABDHIECFG中序遍歷結(jié)果HDIBEAFCG后序遍歷結(jié)果HIDEBFGCA例1例2例2先序遍歷結(jié)果ABCDEGF中序遍歷結(jié)果CBEGDFA后序遍歷結(jié)果CGEFDBA第三十七頁，共六十七頁，2022年，8月28日構(gòu)造二叉樹：一步是先構(gòu)造結(jié)點(diǎn)，第二步是將產(chǎn)生的結(jié)點(diǎn)聯(lián)接在一起。計(jì)算二叉樹的深度：比較左子樹和右子樹的高度，取其最大值刪除二叉樹：從葉子開始，先刪除左子樹，再刪除右子樹，最后刪除根結(jié)點(diǎn)。統(tǒng)計(jì)二叉樹結(jié)點(diǎn)數(shù)：在遍歷時，每次訪問一個結(jié)點(diǎn)時，就在統(tǒng)計(jì)個數(shù)的計(jì)數(shù)器中加一。插入結(jié)點(diǎn)或刪除結(jié)點(diǎn)：二叉樹的操作第三十八頁，共六十七頁，2022年，8月28日5.4.2二叉樹的前序、中序、后序遍歷操作

對于二叉樹的遍歷，將用遞歸算法和非遞歸算法給予討論。遞歸算法簡單明晰，但由于遞歸本身的嵌套執(zhí)行過程，會影響到算法執(zhí)行的效率；非遞歸算法相對較復(fù)雜，實(shí)現(xiàn)中運(yùn)用棧結(jié)構(gòu)類型，算法的效率相對效高，第三十九頁，共六十七頁，2022年，8月28日1）前序遍歷的遞歸算法voidPreOrder(BinaryTreeNode*BT){//二叉樹的前序遍歷遞歸算法

if(BT) { cout<<BT->data<<"";//訪問二叉樹的結(jié)點(diǎn)

PreOrder(BT->LChild); PreOrder(BT->RChild); }}第四十頁，共六十七頁，2022年，8月28日主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC第四十一頁，共六十七頁，2022年，8月28日前序遍歷的非遞歸算法

DLR#defineMaxStackSize100typedefstruct{ BinaryTreeNode *element; int top; int MaxSize;}Stack；StackS;第四十二頁，共六十七頁，2022年，8月28日非遞歸前序算法遍歷思想：A。結(jié)點(diǎn)指針非空時或堆棧非空時:如果結(jié)點(diǎn)指針非空時，首先訪問“根”結(jié)點(diǎn)；結(jié)點(diǎn)指針為空時，轉(zhuǎn)C步驟；B。然后將訪問過的結(jié)點(diǎn)指針（一個“根”的指針）進(jìn)棧，再將指針指向訪問過的結(jié)點(diǎn)的左子樹的根，轉(zhuǎn)A步驟；C。堆棧非空時，退棧，指針指向退棧結(jié)點(diǎn)的右子樹結(jié)點(diǎn)，轉(zhuǎn)A。第四十三頁，共六十七頁，2022年，8月28日

ABCDE圖5.4.3二叉樹表5.4.1二叉樹前序遍歷非遞歸過程

步驟訪問結(jié)點(diǎn)棧S內(nèi)容P的指向初態(tài)

A1AAB2BABC3C

ABC空(C的左孩子)4

AB空(C的右孩子)5

AD6D

AD空(D的左孩子)7

AE8E

AE空(E的左孩子)9

A空(E的右孩子)10

空空(A的右孩子)P第四十四頁，共六十七頁，2022年，8月28日二叉樹的前序遍歷非遞歸算法while(p||!IsEmpty(&S)){ if(p){ cout<<p->data<<"";//訪問“根”結(jié)點(diǎn)

Push(&S,p);/根結(jié)點(diǎn)指針進(jìn)棧，以后回朔時再退棧

p=p->LChild;//指針指向訪問過的“根”結(jié)點(diǎn)左子樹.}else //左子樹為空時，利用堆棧回朔第四十五頁，共六十七頁，2022年，8月28日二叉樹的前序遍歷非遞歸算法if(!IsEmpty(&S)){Pop(&S,p);/從堆棧中彈出回朔結(jié)點(diǎn)指針（該結(jié)點(diǎn)已訪問過）

p=p->RChild;//指針指向回朔結(jié)點(diǎn)的右子樹

} 第四十六頁，共六十七頁，2022年，8月28日2.中序遍歷的遞歸算法

LDRvoidInOrder(BinaryTreeNode*BT){//二叉樹的中序遍歷遞歸算法

if(BT) { InOrder(BT->LChild); cout<<BT->data<<""; //訪問二叉樹的結(jié)點(diǎn)

InOrder(BT->RChild); }}第四十七頁，共六十七頁，2022年，8月28日中序遍歷的非遞歸算法

首先結(jié)點(diǎn)指針（一個“根”的指針）進(jìn)棧，然后將結(jié)點(diǎn)指針指向進(jìn)棧結(jié)點(diǎn)的左子樹的根，重復(fù)A步，直到指針指向空。（最后一個進(jìn)棧的是最左子樹）；堆棧非空時，從堆棧中退出一個指向子樹的“根”的指針，訪問該指針?biāo)附Y(jié)點(diǎn)，轉(zhuǎn)到C步驟。堆棧為空時，結(jié)束算法；然后將指針指向訪問過結(jié)點(diǎn)的右子樹的根，重新從A步驟做起。第四十八頁，共六十七頁，2022年，8月28日表5.4.2二叉樹中序遍歷非遞歸過程

步驟訪問結(jié)點(diǎn)棧S內(nèi)容P的指向初態(tài)

A1

AB2

ABC3

ABC空(C的左孩子)4CAB空(C的右孩子)5BAD6

AD空(D的左孩子)7DAE8

AE空(E的左孩子)9EA空(E的右孩子)10A空空(A的右孩子)ABCDE圖5.4.3二叉樹第四十九頁，共六十七頁，2022年，8月28日do{ while(p){ //找最左子樹

Push(S,p);//“根”結(jié)點(diǎn)（未訪問）指針進(jìn)棧，以后回朔時再退棧

p=p->LChild;//指針指向該“根”結(jié)點(diǎn)左子樹

} if(!IsEmpty(S)){ //左子樹為空時，利用堆棧回朔

Pop(S,p);//從堆棧中彈出回朔結(jié)點(diǎn)指針（該結(jié)點(diǎn)未訪問過）

cout<<p->data<<""; //訪問“根”結(jié)點(diǎn)

p=p->RChild; //指針指向回朔結(jié)點(diǎn)的右子樹}}while（（p）||!IsEmpty(S)）;第五十頁，共六十七頁，2022年，8月28日3.二叉樹的后序遍歷LRDvoidPostOrder(BinaryTreeNode*BT){//二叉樹的中序遍歷遞歸算法

if(BT) { PostOrder(BT->LChild); PostOrder(BT->RChild); Cout<<BT->data<<""; //訪問二叉樹的結(jié)點(diǎn)}}第五十一頁，共六十七頁，2022年，8月28日后序遍歷的非遞歸算法

后序遍歷的非遞歸算法中結(jié)點(diǎn)的進(jìn)棧不是一次，每個結(jié)點(diǎn)要進(jìn)棧兩次。第一次進(jìn)棧時，是在遍歷左子樹的過程中將“根”結(jié)點(diǎn)進(jìn)棧，待左子樹訪問完后，退出這個“根”結(jié)點(diǎn)，但不能立即訪問.借助于這個“根”去找該“根”的右子樹，并遍歷這個右子樹，直到該右子樹全部遍歷以后，再退出該“根”結(jié)點(diǎn)，訪問之。將堆棧數(shù)據(jù)元素的結(jié)構(gòu)中增加一個數(shù)據(jù)項(xiàng)，用于記載第幾次進(jìn)棧。

第五十二頁，共六十七頁，2022年，8月28日堆棧數(shù)據(jù)元素struct{ BinaryTreeNode *ptr; boolB;//B為false時，表示第一次進(jìn)棧；B為true時，表示第二次進(jìn)棧

}SType;typedefstruct{ SType *element int top; int MaxSize;}Stack；StackS;第五十三頁，共六十七頁，2022年，8月28日非遞歸后序遍歷算法思想：A) 當(dāng)結(jié)點(diǎn)非空時或堆棧非空時，執(zhí)行A步驟，否則，結(jié)束算法。B) 當(dāng)結(jié)點(diǎn)指針非空時，結(jié)點(diǎn)的進(jìn)棧標(biāo)志設(shè)為false，結(jié)點(diǎn)指針及進(jìn)棧標(biāo)志進(jìn)棧，然后將結(jié)點(diǎn)指針指向進(jìn)棧結(jié)點(diǎn)的左子樹的根，重復(fù)B步，直到指針為空（最后一個進(jìn)棧的是最左子樹）；結(jié)點(diǎn)指針為空時，轉(zhuǎn)C步驟。C) 堆棧非空時，從堆棧中退出一個結(jié)點(diǎn)的指針；如果退出的結(jié)點(diǎn)進(jìn)棧標(biāo)志為true，說明該結(jié)點(diǎn)是第二次退棧，則訪問該結(jié)點(diǎn)，并將指針強(qiáng)制設(shè)為空，準(zhǔn)備下一次退棧，并轉(zhuǎn)C步驟；第五十四頁，共六十七頁，2022年，8月28日ABCDE圖5.4.3二叉樹第五十五頁，共六十七頁，2022年，8月28日while（（p）||!IsEmpty(S)）if(p) //找最左子樹{ temp.B=false; //準(zhǔn)備進(jìn)棧的結(jié)點(diǎn)進(jìn)棧標(biāo)志設(shè)為第一次進(jìn)棧

temp.ptr=p; Push(S,temp);//“根”結(jié)點(diǎn)（未訪問）指針及標(biāo)志進(jìn)棧，以后回朔時再退棧

p=p->LChild; //指針指向該“根”結(jié)點(diǎn)左子樹}else第五十六頁，共六十七頁，2022年，8月28日if(!IsEmpty(S)){//左子樹為空時，利用堆棧回朔

Pop(S,temp); //從堆棧中彈出回朔結(jié)點(diǎn)指針及標(biāo)志（該結(jié)點(diǎn)未訪問過）

p=temp.prt; //p指向退棧結(jié)點(diǎn)

if(temp.B){ cout<<p->data<<""; //訪問該結(jié)點(diǎn)

p=NULL; //將p設(shè)為空的目的是為強(qiáng)制退棧作準(zhǔn)備

}else { temp.B=true;//改變進(jìn)棧標(biāo)志，準(zhǔn)備重新進(jìn)棧

Push(S,temp); p=p->RChild;//指針指向“根”的右子樹

}}第五十七頁，共六十七頁，2022年，8月28日對遍歷的分析：從前面的三種遍歷算法可以知道： 從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個結(jié)點(diǎn)經(jīng)過3次。AFEDCBG第1次經(jīng)過時訪問，是先序遍歷第2次經(jīng)過時訪問，是中序遍歷第3次經(jīng)過時訪問，是后序遍歷2.二叉樹遍歷的時間效率和空間效率時間效率:O(n)

//每個結(jié)點(diǎn)只訪問一次空間效率:O(n)

//棧占用的最大輔助空間精確值：樹深為k的遞歸遍歷需要k+1個輔助單元第五十八頁，共六十七頁，2022年，8月28日5.4.3二叉樹的層次遍歷操作

介紹從上至下的兩種遍歷過程層次遍歷時，將使用一個隊(duì)列作為輔助，來完成遍歷過程typedefstruct{ BinaryTreeNode *element; int front; int rear; int MaxSize;}Queue；如果一個結(jié)點(diǎn)被訪問后，則其先準(zhǔn)備訪問的孩子就應(yīng)該先進(jìn)隊(duì)，后訪問的孩子后進(jìn)隊(duì)。第五十九頁，共六十七頁，2022年，8月28日1.從上至下，

從左至右（Top_Left）ABCDEFG圖5.4.4一棵二叉樹第六十頁，共六十七頁，2022年，8月28日while(p){ cout<<p->data<<""; //訪問該結(jié)點(diǎn)

if(p->LChild) Enqueue(&Q,p->LChild); //左子樹進(jìn)隊(duì)

if(p->RChild) Enqueue(&Q,p-