數(shù)據(jù)結(jié)構(gòu)第五章

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

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

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

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

如果一棵非空的二叉樹只有一個葉子，且其余結(jié)點均只有一個孩子第11頁，課件共67頁，創(chuàng)作于2023年2月ABCDEFG圖5.2.2一棵滿二叉樹123456789101112圖5.2.4一棵順序二叉樹圖5.2.5一棵非順序二叉樹12345678912圖5.2.8退化的二叉樹AIDB12472852(a)(b)第12頁，課件共67頁，創(chuàng)作于2023年2月5.2.2二叉樹的性質(zhì)

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

性質(zhì)2:深度為h的二叉樹至多有2h-1個結(jié)點。可以由性質(zhì)1推出上述結(jié)論。顯然，深度為h的二叉樹的最大結(jié)點應(yīng)為各層最大結(jié)點之和即為：（第i層上的最大結(jié)點數(shù)）=2i-1=2h-1第14頁，課件共67頁，創(chuàng)作于2023年2月5.2.2二叉樹的性質(zhì)

性質(zhì)3:包括n（n>0）個元素的二叉樹的邊數(shù)為n-1。證明：二叉樹中每個元素（除根結(jié)點外）有且僅有一個雙親結(jié)點。而孩子結(jié)點與雙親結(jié)點之間有且僅有一條邊，因此包含n個元素的二叉樹的邊數(shù)是n-1。第15頁，課件共67頁，創(chuàng)作于2023年2月5.2.2二叉樹的性質(zhì)

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

個結(jié)點。Ａ)２9

Ｂ)２8

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

個。Ａ)２k-1

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

。Ａ)高度Ｂ)層次Ｃ)深度Ｄ)度DCC課堂練習(xí)：第19頁，課件共67頁，創(chuàng)作于2023年2月

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

第20頁，課件共67頁，創(chuàng)作于2023年2月二叉樹的抽象數(shù)據(jù)類型Dset： 有限元素集合。Rset： 如果不空，被分為根結(jié)點、左子樹和右子樹；每個子樹仍然是一個二叉樹。OPSet：PreOrder(*BT)二叉樹的前序遍歷遞歸算法PreOrderN(*BT)二叉樹的前序遍歷非遞歸算法InOrder(*BT)二叉樹的中序遍歷遞歸算法InOrderN(*BT)二叉樹的中序遍歷非遞歸算法第21頁，課件共67頁，創(chuàng)作于2023年2月二叉樹的抽象數(shù)據(jù)類型PostOrder(*BT)二叉樹的后序遍歷遞歸算法PostOrderN(*BT)二叉樹的后序遍歷非遞歸算法LevelOrderTL(*BT)左至右，上至下層次遍歷LevelOrderTR(*BT))右至左，上至下層次遍歷MakeNode(&x)構(gòu)造結(jié)點MakeBinaryTree(*root,*left,*right)聯(lián)接三個結(jié)點為二叉樹BinaryHeight(*BT)求二叉樹的高度BinaryDelete(*BT)二叉樹的刪除算法第22頁，課件共67頁，創(chuàng)作于2023年2月5.3.1二叉樹的存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)按二叉樹的結(jié)點“自上而下、從左至右”編號，用一組連續(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第23頁，課件共67頁，創(chuàng)作于2023年2月討論：不是完全二叉樹怎么辦？答：一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結(jié)點”，其內(nèi)容為空。AB^C^^^D^…E[0][1][2][3][4][5][6][7][8].[15]ABECD缺點：①浪費空間；②插入、刪除不便

第24頁，課件共67頁，創(chuàng)作于2023年2月二、鏈?zhǔn)酱鎯Y(jié)構(gòu)

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

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

（相應(yīng)地，訪問樹中結(jié)點時也只能從根開始）注：如果需要倒查某結(jié)點的雙親，可以再增加一個雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。第25頁，課件共67頁，創(chuàng)作于2023年2月優(yōu)點：①不浪費空間；②插入、刪除方便

ABCDEFG

AB

C

D

E

F

G^^^^^^^^第26頁，課件共67頁，創(chuàng)作于2023年2月問：含有n個結(jié)點的二叉樹中，共有鏈接域有2n個，空閑的（不用的）鏈接域有n+1個（為什么？）證明：根據(jù)性質(zhì)4：n0=n2+1,有葉子結(jié)點空閑的鏈接域為2n2+2度為1的結(jié)點空閑的鏈接域為n-n0-n2=n-2n2-1,則總的空閑鏈接域為2n0+n1=n+1第27頁，課件共67頁，創(chuàng)作于2023年2月5.4.4二叉樹的其它操作

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

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

第28頁，課件共67頁，創(chuàng)作于2023年2月2)構(gòu)造一棵二叉子樹（或二叉樹）

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

root->LChild=left; root->RChild=right;}第29頁，課件共67頁，創(chuàng)作于2023年2月ABCDEFG圖5.4.4一棵二叉樹

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

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

第32頁，課件共67頁，創(chuàng)作于2023年2月ADBCDLRADLRDLR>B>>D>>CDLR前序遍歷序列：ABDC前序遍歷:第33頁，課件共67頁，創(chuàng)作于2023年2月ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:第34頁，課件共67頁，創(chuàng)作于2023年2月ADBC

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

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

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

PreOrder(BT->LChild); PreOrder(BT->RChild); }}第40頁，課件共67頁，創(chuàng)作于2023年2月主程序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第41頁，課件共67頁，創(chuàng)作于2023年2月前序遍歷的非遞歸算法

DLR#defineMaxStackSize100typedefstruct{ BinaryTreeNode *element; int top; int MaxSize;}Stack；StackS;第42頁，課件共67頁，創(chuàng)作于2023年2月非遞歸前序算法遍歷思想：A。結(jié)點指針非空時或堆棧非空時:如果結(jié)點指針非空時，首先訪問“根”結(jié)點；結(jié)點指針為空時，轉(zhuǎn)C步驟；B。然后將訪問過的結(jié)點指針（一個“根”的指針）進(jìn)棧，再將指針指向訪問過的結(jié)點的左子樹的根，轉(zhuǎn)A步驟；C。堆棧非空時，退棧，指針指向退棧結(jié)點的右子樹結(jié)點，轉(zhuǎn)A。第43頁，課件共67頁，創(chuàng)作于2023年2月

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

步驟訪問結(jié)點棧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第44頁，課件共67頁，創(chuàng)作于2023年2月二叉樹的前序遍歷非遞歸算法while(p||!IsEmpty(&S)){ if(p){ cout<<p->data<<"";//訪問“根”結(jié)點

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

p=p->LChild;//指針指向訪問過的“根”結(jié)點左子樹.}else //左子樹為空時，利用堆?；厮返?5頁，課件共67頁，創(chuàng)作于2023年2月二叉樹的前序遍歷非遞歸算法if(!IsEmpty(&S)){Pop(&S,p);/從堆棧中彈出回朔結(jié)點指針（該結(jié)點已訪問過）

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

} 第46頁，課件共67頁，創(chuàng)作于2023年2月2.中序遍歷的遞歸算法

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

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

InOrder(BT->RChild); }}第47頁，課件共67頁，創(chuàng)作于2023年2月中序遍歷的非遞歸算法

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

步驟訪問結(jié)點棧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二叉樹第49頁，課件共67頁，創(chuàng)作于2023年2月do{ while(p){ //找最左子樹

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

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

} if(!IsEmpty(S)){ //左子樹為空時，利用堆?；厮?/p>

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

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

p=p->RChild; //指針指向回朔結(jié)點的右子樹}}while（（p）||!IsEmpty(S)）;第50頁，課件共67頁，創(chuàng)作于2023年2月3.二叉樹的后序遍歷LRDvoidPostOrder(BinaryTreeNode*BT){//二叉樹的中序遍歷遞歸算法

if(BT) { PostOrder(BT->LChild); PostOrder(BT->RChild); Cout<<BT->data<<""; //訪問二叉樹的結(jié)點}}第51頁，課件共67頁，創(chuàng)作于2023年2月后序遍歷的非遞歸算法

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

第52頁，課件共67頁，創(chuàng)作于2023年2月堆棧數(shù)據(jù)元素struct{ BinaryTreeNode *ptr; boolB;//B為false時，表示第一次進(jìn)棧；B為true時，表示第二次進(jìn)棧

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

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

p=p->LChild; //指針指向該“根”結(jié)點左子樹}else第56頁，課件共67頁，創(chuàng)作于2023年2月if(!IsEmpty(S)){//左子樹為空時，利用堆?；厮?/p>

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

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

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

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

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

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

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

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

//棧占用的最大輔助空間精確值：樹深為k的遞歸遍歷需要k+1個輔助單元第58頁，課件共67頁，創(chuàng)作于2023年2月5.4.3二叉樹的層次遍歷操作

介紹從上至下的兩種遍歷過程層次遍歷時，將使用一個隊列作為輔助，來完成遍歷過程typedefstruct{ BinaryTreeNode *element; int front; int rear; int MaxSize;}Queue；如果一個結(jié)點被訪問后，則其先準(zhǔn)備訪問的孩子就應(yīng)該先進(jìn)隊，后訪問的孩子后進(jìn)隊。第59頁，課件共67頁，創(chuàng)作于2023年2月1.從上至下，

從左至右（Top_Left）ABCDEFG圖5.4.4一棵二叉樹第60頁，課件共67頁，創(chuàng)作于2023年2月while(p){ cout<<p->data<<""; //訪問該結(jié)點

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

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