樹和二叉樹解析課件

第6章樹數(shù)據(jù)結構11/22/20221第6章樹數(shù)據(jù)結構10/11/202216.6哈夫曼樹

6.5樹和森林6.4線索二叉樹6.3遍歷二叉樹6.2二叉樹6.1樹的基本概念目錄11/22/202226.6哈夫曼樹6.5樹和森林6.4線索二叉樹6.36.1樹的基本概念6.1.1樹的定義1．樹的定義樹是由n（n≥0）個結點組成的有限集合。若n=0，稱為空樹；若n>0，則：（1）有一個特定的稱為根（root）的結點。它只有直接后繼，但沒有直接前驅；（2）除根結點以外的其它結點可以劃分為m（m≥0）個互不相交的有限集合T0，T1，…，Tm-1，每個集合Ti（i=0,1,…,m-1）又是一棵樹，稱為根的子樹，每棵子樹的根結點有且僅有一個直接前驅，但可以有0個或多個直接后繼。由此可知，樹的定義是一個遞歸的定義，即樹的定義中又用到了樹的概念。樹的結構參見圖6-1。11/22/202236.1樹的基本概念6.1.1樹的定義1．樹的定義樹11/22/2022410/11/20224在圖6-1(c)中，樹的根結點為A，該樹還可以分為三個互不相交子集T0，T1，T2，具體請參見圖6-2，其中T0={B，E，F(xiàn)，J，K，L}，T1={C，G}，T2={D，H，I，M}，其中的T0，T1，T2都是樹，稱為圖6-1（C）中樹的子樹，而T0，T1，T2又可以分解成若干棵不相交子樹。如T0可以分解成T00，T01兩個不相交子集，T00={E，J，K，L}，T01={F}，而T00又可以分為三個不相交子集T000，T001，T002，其中，T000={J}，T001={K}，T002={L}。11/22/20225在圖6-1(c)中，樹的根結點為A，該樹還可以分為三個互2．樹的邏輯結構描述一棵樹的邏輯結構可以用二元組描述為：tree=(k,R)k={ki∣1≤i≤n;n≥0,kielemtype}R={r}其中，n為樹中結點個數(shù)，若n=0，則為一棵空樹，n>0時稱為一棵非空樹，而關系r應滿足下列條件：（1）有且僅有一個結點沒有前驅,稱該結點為樹根;（2）除根結點以外,其余每個結點有且僅有一個直接前驅;（3）樹中每個結點可以有多個直接后繼(孩子結點)。11/22/202262．樹的邏輯結構描述一棵樹的邏輯結構可以用二元組描述為例如，對圖6-1(c)的樹結構,可以二元組表示為：K={A，B，C，D，E，F(xiàn)，G，H，I，J，K，L，M}R={r}r={(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)，(D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(H,M)}3．樹的基本運算樹的基本運算可以定義如下幾種：(1)inittree(&T)初始化樹T。(2)root(T)求樹T的根結點。11/22/20227例如，對圖6-1(c)的樹結構,可以二元組表示為：3．(3)parent(T,x)求樹T中，值為x的結點的雙親。(4)child(T,x,i)求樹T中，值為x的結點的第i個孩子。(5)addchild(y,i,x)把值為x的結點作為值為y的結點的第i個孩子插入到樹中。(6)delchild(x,i)刪除值為x的結點的第i個孩子。(7)traverse(T)遍歷或訪問樹T。11/22/20228(3)parent(T,x)10/11/202286.1.2基本術語1.結點指樹中的一個數(shù)據(jù)元素，一般用一個字母表示。2.度一個結點包含子樹的數(shù)目，稱為該結點的度。3.樹葉（葉子）度為0的結點，稱為葉子結點或樹葉，也叫終端結點。4.孩子結點若結點X有子樹，則子樹的根結點為X的孩子結點，也稱為孩子，兒子，子女等。如圖6-1（c）中A的孩子為B，C，D。11/22/202296.1.2基本術語1.結點2.度3.樹葉（葉子）45.雙親結點若結點X有子女Y，則X為Y的雙親結點。

6.祖先結點從根結點到該結點所經(jīng)過分枝上的所有結點為該結點的祖先，如圖6-1（c）中M的祖先有A，D，H。7.子孫結點某一結點的子女及子女的子女都為該結點子孫。8.兄弟結點具有同一個雙親的結點，稱為兄弟結點。11/22/2022105.雙親結點6.祖先結點7.子孫結點8.兄弟結點10/11/9.分枝結點除葉子結點外的所有結點，為分枝結點，也叫非終端結點。10．層數(shù)根結點的層數(shù)為1，其它結點的層數(shù)為從根結點到該結點所經(jīng)過的分支數(shù)目再加1。

11.樹的高度（深度）樹中結點所處的最大層數(shù)稱為樹的高度，如空樹的高度為0，只有一個根結點的樹高度為1。12.樹的度樹中結點度的最大值稱為樹的度。11/22/2022119.分枝結點10．層數(shù)11.樹的高度（深度）12.樹的度13.有序樹若一棵樹中所有子樹從左到右的排序是有順序的，不能顛倒次序。稱該樹為有序樹。14.無序樹若一棵樹中所有子樹的次序無關緊要，則稱為無序樹。15．森林（樹林）若干棵互不相交的樹組成的集合為森林。一棵樹可以看成是一個特殊的森林。11/22/20221213.有序樹14.無序樹15．森林（樹林）10/

6.1.3樹的表示1．樹形結構表示法具體參見圖6-1。11/22/2022136.1.3樹的表示1．樹形結構表示法10/11/22.凹入法表示法具體參見圖6-3。11/22/2022142.凹入法表示法10/11/2022143.嵌套集合表示法具體參見圖6-4。11/22/2022153.嵌套集合表示法10/11/2022154.廣義表表示法對圖6-1（c）的樹結構，廣義表表示法可表示為：（A（B（E（J，K，L），F(xiàn)），C（G），D（H（M），I）））6.1.4樹的性質性質1樹中的結點數(shù)等于所有結點的度加1。

證明：根據(jù)樹的定義，在一棵樹中，除根結點以外，每個結點有且僅有一個直接前驅，也就是說，每個結點與指向它的一個分支一一對應，所以，除根結點以外的結點數(shù)等于所有結點的分支數(shù)（即度數(shù)），而根結點無直接前驅，因此，樹中的結點數(shù)等于所有結點的度數(shù)加1。11/22/2022164.廣義表表示法6.1.4樹的性質性質1樹中的結點性質2度為k的樹中第i層上最多有ki-1個結點（i≥1）。下面用數(shù)學歸納法證明：對于i=1，顯然成立，假設對于i-1層，上述條件成立，即第i-1層最多有ki-2個結點，對于第i層，結點數(shù)最多為第i-1層結點數(shù)的k倍（因為度為k），故第i層的結點數(shù)為ki-2*k=ki-1。性質3深度為h的k叉樹最多有個結點。證明：由性質2可知，若每一層的結點數(shù)最多，則整個k叉樹結點數(shù)最多，共有=k0+k1+…+kh-1=。當一棵K叉樹上的結點數(shù)達到時，稱為滿K叉樹。11/22/202217性質2度為k的樹中第i層上最多有ki-1個結點（i≥1性質4具有n個結點的k叉樹的最小深度為logk(n(k-1)+1)。（請注意，x表示取不小于x的最小整數(shù)，或叫做對x上取整。）證明：設具有n個結點的k叉樹的深度為h，即在該樹的前面h-1層都是滿的，即每一層的結點數(shù)等于ki-1個(1≤i≤h-1)，第h層（即最后一層）的結點數(shù)可能滿，也可能不滿，這時，該樹具有最小的深度。由性質3知道，結點數(shù)n應滿足下面條件：<n≤，通過轉換為：kh-1<n(k-1)+1≤kh，再取以k為底的對數(shù)后，可以得到：h-1<logk(n(k-1)+1)≤h，即有：logk(n(k-1)+1)≤h<logk(n(k-1)+1)+1，而h只能取整數(shù)，所以，該k叉樹的最小深度為h=logk(n(k-1)+1)。11/22/202218性質4具有n個結點的k叉樹的最小深度為logk(n(k-

樹的存儲結構

1．雙親表示它是以一組連續(xù)的存儲單元來存放樹中的結點，每個結點有兩個域：一個是data域，存放結點信息，另一個是parent域，用來存放雙親的位置(指針)。該結構的具體描述見圖6-21。11/22/202219樹的存儲結構1．雙親表示該結構的具體描述見圖6-22．孩子表示法將一個結點所有孩子鏈接成一個單鏈表形，而樹中有若干個結點，故有若干個單鏈表，每個單鏈表有一個表頭結點，所有表頭結點用一個數(shù)組來描述，具體描述參見圖6-2211/22/2022202．孩子表示法將一個結點所有孩子鏈接成一個單鏈表形，而3．雙親孩子表示法將第1、2兩種方法結合起來，則得到雙親孩子表示法，具體參見圖6-23。11/22/2022213．雙親孩子表示法10/11/2022214。孩子兄弟表示法類似于二叉鏈表，但第一根鏈指向第一個孩子，第二根鏈指向下一個兄弟。將圖6-21(a)的樹用孩子兄弟表示法表示，見圖6-24。11/22/2022224。孩子兄弟表示法10/11/2022226.2二叉樹6.2.1二叉樹的定義1．二叉樹的定義和樹結構定義類似，二叉樹的定義也可以遞歸形式給出：二叉樹是n（n≥0）個結點的有限集，它或者是空集（n=0），或者由一個根結點及兩棵不相交的左子樹和右子樹組成。二叉樹的特點是每個結點最多有兩個孩子，或者說，在二叉樹中，不存在度大于2的結點，并且二叉樹是有序樹（樹為無序樹），其子樹的順序不能顛倒，因此，二叉樹有五種不同的形態(tài)，參見圖6-5。11/22/2022236.2二叉樹6.2.1二叉樹的定義1．二叉樹的定義11/22/20222410/11/2022242．二叉樹的基本運算

（1）inittree(&T)二叉樹的初始化。（2）root(T)求二叉樹的根結點。（3）parent(T,x)求二叉樹T中值為x的結點的雙親。（4）lchild(T,x)求二叉樹T中值為x的結點的左孩子。11/22/2022252．二叉樹的基本運算（1）inittree(&T)（2）r（5）rchild(T,x)求二叉樹T中值為x的結點的右孩子。（6）lbrother(T,x)求二叉樹T中值為x的結點的左兄弟。（7）rbrother(T,x)求二叉樹T中值為x的結點的右兄弟。

（8）traverse(T)遍歷二叉樹T。11/22/202226（5）rchild(T,x)（6）lbrother(T,x)（9）createtree(&T)建立一棵二叉樹T。（10）addlchild(&T,x,y)在二叉樹T中，將值為y的結點作為值為x的結點的左孩子插入。（11）addrchild(&T,x,y)在二叉樹T中，將值為y的結點作為值為x的結點的右孩子插入。（12）dellchild(&T,x)在二叉樹T中，刪除值為x的結點的左孩子。（13）delrchild(&t,x)在二叉樹T中，刪除值為x的結點的右孩子。

11/22/202227（9）createtree(&T)（10）addlchil6.2.2二叉樹的性質性質1若二叉樹的層數(shù)從1開始，則二叉樹的第k層結點數(shù)，最多為2k-1個（k>0）?？梢杂脭?shù)學歸納法證明之。性質2深度（高度）為k的二叉樹最大結點數(shù)為2k-1（k>0）。

證明：深度為k的二叉樹，若要求結點數(shù)最多，則必須每一層的結點數(shù)都為最多，由性質1可知，最大結點數(shù)應為每一層最大結點數(shù)之和。既為20+21+…+2k-1=2k-1。11/22/2022286.2.2二叉樹的性質性質1若二叉樹的層數(shù)從1開始，則二性質3對任意一棵二叉樹，如果葉子結點個數(shù)為n0，度為2的結點個數(shù)為n2，則有n0=n2+1。證明：設二叉樹中度為1的結點個數(shù)為n1，根據(jù)二叉樹的定義可知，該二叉樹的結點數(shù)n=n0+n1+n2。又因為在二叉樹中，度為0的結點沒有孩子，度為1的結點有1個孩子，度為2的結點有2個結孩子，故該二叉樹的孩子結點數(shù)為n0*0+n1*1+n2*2，而一棵二叉樹中，除根結點外所有都為孩子結點，故該二叉樹的結點數(shù)應為孩子結點數(shù)加1即：n=n0*0+n1*1+n2*2+1因此,有n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。為繼續(xù)給出二叉樹的其它性質，先定義兩種特殊的二叉樹。11/22/202229性質3對任意一棵二叉樹，如果葉子結點個數(shù)為n0，度為2的滿二叉樹深度為k具有2-k-1個結點的二叉樹，稱為滿二叉樹。從上面滿二叉樹定義可知，必須是二叉樹的每一層上的結點數(shù)都達到最大，否則就不是滿二叉樹。完全二叉樹如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編號為1~n的結點一一對應，則稱這棵二叉樹為完全二叉樹。從完全二叉樹定義可知，結點的排列順序遵循從上到下、從左到右的規(guī)律。所謂從上到下，表示本層結點數(shù)達到最大后，才能放入下一層。從左到右，表示同一層結點必須按從左到右排列，若左邊空一個位置時不能將結點放入右邊。11/22/202230滿二叉樹深度為k具有2-k-1個結點的二叉樹，稱為滿二叉從滿二叉樹及完全二叉樹定義還可以知道，滿二叉樹一定是一棵完全二叉樹，反之完全二叉樹不一定是一棵滿二叉樹。滿二叉樹的葉子結點全部在最底層，而完全二叉樹的葉子結點可以分布在最下面兩層。深度為4的滿二叉樹和完全二叉樹如圖6-6所示。11/22/202231從滿二叉樹及完全二叉樹定義還可以知道，滿二叉樹一定是一棵性質4具有n個結點的完全二叉樹高度為log2(n)+1或log2（n+1）。(注意x表示取不大于x的最大整數(shù)，也叫做對x下取整，x表示取不小于x的最小整數(shù)，也叫做對x上取整。)證明：設該完全二叉樹高度為k，則該二叉樹的前面k-1層為滿二叉樹，共有2k-1-1個結點，而該二叉具有k層，第k層至少至少有1個結點，最多有2k-1個結點。因此有下面的不等式成立：-----（2k-1–1）+1≤n≤（2k-1-1）+2k-1，即有2k-1≤n≤2k-1。由式子后半部分可知,n≤2k-1…①由式子前半部分可知2k-1≤n…②由①有n+1≤2k，同時取對數(shù)得：log2(n+1)≤k故k≥log2(n+1),即k=log2(n+1)。即得到第二個結論。由②有2k-1≤n,同時取對數(shù)得：k≤log2n+1即k=log2n+1,即第一個結論成立,證畢。11/22/202232性質4具有n個結點的完全二叉樹高度為log2(n)+性質5如果將一棵有n個結點的完全二叉樹從上到下，從左到右對結點編號1，2，…，n，然后按此編號將該二叉樹中各結點順序地存放于一個一維數(shù)組中，并簡稱編號為j的結點為j(1≤j≤n)，則有如下結論成立：（1）若j=1，則結點j為根結點，無雙親，否則j的雙親為j/2；（2）若2j≤n，則結點j的左子女為2j,否則無左子女。即滿足2j>n的結點為葉子結點；（3）若2j+1≤n，則結點j的右子女為2j+1，否則無右子女；（4）若結點j序號為奇數(shù)且不等于1，則它的左兄弟為j-1；（5）若結點j序號為偶數(shù)且不等于n，它的右兄弟為j+1；（6）結點j所在層數(shù)(層次)為log2j+1；11/22/202233性質5如果將一棵有n個結點的完全二叉樹從上到下，從左到右對結6.2.3二叉樹的存貯結構1．順序存貯結構將一棵二叉樹按完全二叉樹順序存放到一個一維數(shù)組中，若該二叉樹為非完全二叉樹，則必須將相應位置空出來，使存放的結果符合完全二叉樹形狀。如圖6-7給出了順序存貯形式。11/22/2022346.2.3二叉樹的存貯結構1．順序存貯結構將一棵二叉樹對于一棵二叉樹,若采用順序存貯時,當它為完全二叉樹時,比較方便,若為非完全二叉樹,將會浪費大量存貯存貯單元。最壞的非完全二叉樹是全部只有右分支,設高度為K,則需占用2K-1個存貯單元,而實際只有k個元素,實際只需k個存儲單元。因此，對于非完全二叉樹，宜采用下面的鏈式存儲結構。2．二叉鏈表存貯結構（1）二叉鏈表表示將一個結點分成三部分,一部分存放結點本身信息,另外兩部分為指針,分別存放左、右孩子的地址。二叉鏈表中一個結點可描述為:11/22/202235對于一棵二叉樹,若采用順序存貯時,當它為完全二叉樹時,比對于圖6-7所示二叉樹,用二叉鏈表形式描述見圖6-8。

11/22/202236對于圖6-7所示二叉樹,用二叉鏈表形式描述見圖6-8。對于一棵二叉樹,若采用二叉鏈表存貯時,當二叉樹為非完全二叉樹時,比較方便,若為完全二叉樹時,將會占用較多存貯單元(存放地址的指針)。若一棵二叉樹有n個結點,采用二叉鏈表作存貯結構時,共有2n個指針域,其中只有n-1個指針指向左右孩子,其余n+1個指針為空,沒有發(fā)揮作用,被白白浪費掉了,(當然后面介紹的線索可利用它)。（2）二叉鏈表的數(shù)據(jù)類型二叉鏈表的數(shù)據(jù)類型描述如下:structbitree{elemtypedata;//結點數(shù)據(jù)類型bitree*lchild,*rchild;}//定義左、右孩子為指針型11/22/202237對于一棵二叉樹,若采用二叉鏈表存貯時,當二叉樹為非完全二(3)二叉鏈表的建立為了后面遍歷二叉樹方便，先介紹建立二叉鏈表的算法（假設elemtype為char型）。

假設二叉鏈表的數(shù)據(jù)類型描述如剛才所述，為建立二叉鏈表，用一個一維表數(shù)組來模擬隊列，存放輸入的結點，但是，輸入結點時，必須按完全二叉樹形式，才能使結點間滿足性質5，若為非完全二叉樹，則必須給定一些假想結點(虛結點)，使之符合完全二叉樹形式。為此，我們在輸入結點值時，存在的結點則輸入它對應的字符，不存在的結點(虛結點)，輸入逗號，最后以一個特殊符號“#”作為輸入的結束,表示建二叉鏈表已完成。建成的二叉鏈表可以由根指針root唯一確定。11/22/202238(3)二叉鏈表的建立假設二叉鏈表的數(shù)據(jù)類型描述如剛才所述算法描述如下：#include<iostream.h>typedefcharelemtype;structbitree{elemtypedata;bitree*lchild,*rchild;};bitree*create(){bitree*q[100];//定義q數(shù)組作為隊列存放二叉鏈表中結點，100為最大容量bitree*s;//二叉鏈表中的結點bitree*root;//二叉鏈表的根指針intfront=1,rear=0;//定義隊列的頭、尾指針11/22/202239算法描述如下：10/11/202239charch;//結點的data域值root=NULL;cin>>ch;while(ch!='#')//輸入值為#號,算法結束{s=NULL;if(ch!=',')//輸入數(shù)據(jù)不為逗號,表示不為虛結點,否則為虛結點 {s=newbitree;s->data=ch; s->lchild=NULL;s->rchild=NULL; } rear++; q[rear]=s;//新結點或虛結點進隊11/22/202240charch;//結點的dif(rear==1)root=s; else {if((s!=NULL)&&(q[front]!=NULL)) {if(rear%2==0)q[front]->lchild=s;//rear為偶數(shù),s為雙親左孩子 elseq[front]->rchild=s;}//rear為奇數(shù),s為雙親右孩子 if(rear%2==1)front++;}//出隊 cin>>ch;}returnroot;}11/22/202241if(rear==1)root=s;10/11/20224例如，對圖6-9所示的二叉樹，建立的二叉鏈表如圖6-10所示。11/22/202242例如，對圖6-9所示的二叉樹，建立的二叉鏈表如圖6-10對圖6-9(a)所示的二叉樹，要用算法建成圖6-10所示的二叉樹鏈表，從鍵盤輸入的數(shù)據(jù)應為：AB,,C,,,,D#↙其中#為輸入結束，↙為回車符。11/22/202243對圖6-9(a)所示的二叉樹，要用算法建成圖6-10所示6.3遍歷二叉樹

所謂遍歷二叉樹，就是遵從某種次序，訪問二叉樹中的所有結點，使得每個結點僅被訪問一次。這里提到的“訪問”是指對結點施行某種操作，操作可以是輸出結點信息，修改結點的數(shù)據(jù)值等，但要求這種訪問不破壞它原來的數(shù)據(jù)結構。在本書中，我們規(guī)定訪問是輸出結點信息data，且以二叉鏈表作為二叉樹的存貯結構。11/22/2022446.3遍歷二叉樹所謂遍歷二叉樹，就是遵從某種次序，訪由于二叉樹是一種非線性結構，每個結點可能有一個以上的直接后繼，因此，必須規(guī)定遍歷的規(guī)則,并按此規(guī)則遍歷二叉樹,最后得到二叉樹所有結點的一個線性序列。

令L,R,D分別代表二叉樹的左子樹、右子樹、根結點，則遍歷二叉樹有6種規(guī)則：DLR、DRL、LDR、LRD、RDL、RKD。若規(guī)定二叉樹中必須先左后右(左右順序不能顛倒)，則只有DLR、LDR、LRD三種遍歷規(guī)則。DLR稱為前根遍歷(或前序遍歷、先序遍歷、先根遍歷)，LDR稱為中根遍歷(或中序遍歷)，LRD稱為后根遍歷(或后序遍歷)。11/22/202245由于二叉樹是一種非線性結構，每個結點可能有一個以上的直接例如，可以利用上面介紹的遍歷算法，寫出如圖6-11所示二叉樹的三種遍歷序列為：先序遍歷序列：ABDGCEFH中序遍歷序列：BGDAECFH后序遍歷序列：GDBEHFCA11/22/202246例如，可以利用上面介紹的遍歷算法，寫出如圖6-11所示二另外，在編譯原理中，有用二叉樹來表示一個算術表達式的情形。在一棵二叉樹中，若用操作數(shù)代表樹葉，運算符代表非葉子結點，則這樣的樹可以代表一個算術表達式。若按前序、中序、后序對該二叉樹進行遍歷，則得到的遍歷序列分別稱為前綴表達式(或稱波蘭式)、中綴表達式、后綴表達式(遞波蘭式)。具體參見圖6-12。圖6-12所對應的前綴表達式：-*abc。圖6-12所對應的中綴表達式：a*b-c。圖6-12所對應的后綴表達式：ab*c-。11/22/202247另外，在編譯原理中，有用二叉樹來表示一個算術表達式的情二叉樹所對應的遍歷序列可以通過遞歸算法得到，也可以通過非遞歸算法得到。但有時要求直接寫出序列，故我們可以用圖6-13所示得到圖6-12的遍歷序列。從二叉樹的三種遞歸遍歷算法可以知道，三種遍歷算法不同之處在于訪問根結點和遍歷左、右子樹的順序不同，若遞歸算法中去掉與遞歸無關的語句——訪問根結點，則三個遍歷算法完全相同。于是對于二叉樹的遍歷，可以看成是從根結點出發(fā)，往左子樹走，若左子樹為空，返回，再進入右子樹，右子樹訪問完后，再返回根結點。這樣一來每個結點都被訪問三次，若將按順序第一次訪問的結點排列起來，則得到該二叉樹的先序序列，第二次訪問的結點排列起來，則得到該二叉樹的中序序列，第三次訪問的結點排列起來，則得到該二叉樹的后序序列。對于圖6-13中，第一次訪問到的結點用△表示,第二次訪問到的結點用○表示,第三次訪問的結點用□表示,按虛線順序將所有△排列,則得到先序序列為-*abc,將所有○排列起來則得到中序序列為a*b-c,將所有□排列起來則得到后序序列ab*c-。11/22/202248二叉樹所對應的遍歷序列可以通過遞歸算法得到，也可以通過非11/22/20224910/11/2022496.3.1前根遍歷所謂前根遍歷，就是根結點最先遍歷，其次左子樹，最后右子樹。1．遞歸遍歷前根遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結束;否則（1）輸出根結點；（2）前根遍歷左子樹;（3）前根遍歷右子樹;11/22/2022506.3.1前根遍歷1．遞歸遍歷前根遍歷二叉樹的遞歸遍歷算法描算法如下:voidpreorder(bitree*root){bitree*p;p=root;if(p!=NULL){cout<<p->data<<“”;preorder(p->lchild);preorder(p->rchild);}}11/22/202251算法如下:10/11/2022512．非遞歸遍歷利用一個一維數(shù)組作為棧，來存儲二叉鏈表中結點，算法思想為：從二叉樹根結點開始，沿左子樹一直走到末端(左孩子為空)為止，在走的過程中，訪問所遇結點，并依次把所遇結點進棧，當左子樹為空時，從棧頂退出某結點，并將指針指向該結點的右孩子。如此重復，直到棧為空或指針為空止。11/22/2022522．非遞歸遍歷利用一個一維數(shù)組作為棧，來存儲二叉鏈表中結算法如下：voidpreorder1(bitree*root){bitree*p,*s[100];inttop=0;//top為棧頂指針p=root;while((p!=NULL)||(top>0)){while(p!=NULL){cout<<p->data<<"";s[++top]=p;p=p->lchild;}p=s[top--];p=p->rchild;}}11/22/202253算法如下：10/11/2022536.3.2中根遍歷所謂中根遍歷，就是根在中間，先左子樹，然后根結點，最后右子樹。1．遞歸遍歷中根遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結束；否則⑴中根遍歷左子樹;⑵輸出根結點;⑶中根遍歷右子樹。11/22/2022546.3.2中根遍歷1．遞歸遍歷中根遍歷二叉樹的遞歸遍算法如下:voidinorder(biteee*root){bitree*p;p=root;if(p!=NULL){inorder(p->lchild);cout<<p->data<<“”;inorder(p->rchild);}}11/22/202255算法如下:10/11/2022552．非遞歸遍歷同樣利用一個一維數(shù)組作棧，來存貯二叉鏈表中結點，算法思想為：從二叉樹根結點開始，沿左子樹一直走到末端(左孩子為空)為止，在走的過程中，把依次遇到的結點進棧,待左子樹為空時,從棧中退出結點并訪問,然后再轉向它的右子樹。如此重復，直到?？栈蛑羔槥榭罩?。11/22/2022562．非遞歸遍歷同樣利用一個一維數(shù)組作棧，來存貯二叉鏈表中算法如下:voidinorder1(bitree*root){bitree*p,*s[100];//s為一個棧，top為棧頂指針inttop=0;p=root;while((p!=NULL)||(top>0)){while(p!=NULL){s[++top]=p;p=p->lchild;}{p=s[top--];cout<<p->data<<"";p=p->rchild;}}}11/22/202257算法如下:cout<<p->data<<"";10/116.3.3后根遍歷所謂后根遍歷，就是根在最后，即先左子樹，然后右子樹，最后根結點。1．遞歸遍歷后根遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結束;否則（1）后根遍歷左子樹:（2）后根遍歷歷子樹;（3）訪問根結點。11/22/2022586.3.3后根遍歷1．遞歸遍歷后根遍歷二叉樹的遞歸遍歷算法如下:voidpostorder(bitree*root){bitree*p;p=root;if(p!=NULL){postorder(p->lchild);postorder(p->rchild);cout<<p->data<<“”;}}11/22/202259算法如下:10/11/2022592.非遞歸遍歷利用棧來實現(xiàn)二叉樹的后序遍歷要比前序和中序遍歷復雜得多，在后序遍歷中，當搜索指針指向某一個結點時，不能馬上進行訪問，而先要遍歷左子樹，所以此結點應先進棧保存，當遍歷完它的左子樹后，再次回到該結點，還不能訪問它，還需先遍歷其右子樹,所以該結點還必須再次進棧，只有等它的右子樹遍歷完后，再次退棧時，才能訪問該結點。為了區(qū)分同一結點的兩次進棧，引入一個棧次數(shù)的標志，一個元素第一次進棧標志為0，第二次進標志為1，并將標志存入另一個棧中，當從標志棧中退出的元素為1時，訪問結點。11/22/2022602.非遞歸遍歷利用棧來實現(xiàn)二叉樹的后序遍歷要比前序和中序后序遍歷二叉樹的非遞歸算法如下：voidpostorder1(bitree*root){bitree*p,*s1[100];//s1棧存放樹中結點ints2[100],top=0,b;//s2棧存放進棧標志p=root;do{while(p!=NULL){s1[top]=p;s2[top++]=0;//第一次進棧標志為0p=p->lchild;}if(top>0) {b=s2[--top]; p=s1[top];11/22/202261后序遍歷二叉樹的非遞歸算法如下：{s1[top]=p;s2if(b==0) {s1[top]=p;s2[top++]=1;//第二次進棧標志為0

p=p->rchild;} else {cout<<p->data<<""; p=NULL; } }}while(top>0);}11/22/202262if(b==0)10/11/2022626.3.4遍歷算法應用舉例例6-5由二叉樹的前序序列和中序序列建立該二叉樹分析：若二叉樹的任意兩個結點的值都不相同，則二叉樹的前序序列和中序序列能唯一確定一棵二叉樹。另外，由前序序列和中序序列的定義可知，前序序列中第一個結點必為根結點，而在中序序列中，根結點剛好是左、右子樹的分界點，因此，可按如下方法建立二叉樹：11/22/2022636.3.4遍歷算法應用舉例例6-5由二叉樹的前序序1.用前序序列的第一個結點作為根結點;2.在中序序列中查找根結點的位置，并以此為界將中序序列劃分為左、右兩個序列(左、右子樹);3.根據(jù)左、右子樹的中序序列中的結點個數(shù)，將前序序列去掉根結點后的序列劃分為左、右兩個序列，它們分別是左、右子樹的前序序列;4.對左、右子樹的前序序列和中序序列遞歸地實施同樣方法，直到所得左、右子樹為空。假設前序序列為ABDGHCEFI，中序序列為GDHBAECIF，則得到的二叉樹如下頁所示11/22/2022641.用前序序列的第一個結點作為根結點;2.在中序序列1.A為根結點ABDGHCEFIGDHBAECIFBDGHCEFIA2.B為左子樹的根結點BDGHGDHBCEFIDHGBA3.D為左子樹的左子樹的根結點11/22/2022651.A為根結點ABDGHCEFIGDHBA4.C為右子樹的根結點5.F為右子樹的右子樹的根結點CEFIECIF11/22/2022664.C為右子樹的根結點5.F為右子樹的右子樹的根結點C例6-6按層次遍歷一棵二叉樹對于一棵二叉樹，若規(guī)定遍歷順序為從上到下(上層遍歷完才進入下層)，從左到右(同一層從左到右進行，這樣的遍歷稱為按層次遍歷：例6-5的樹的層次遍歷序列為：ABCDEFGHI。下面用一個一維數(shù)組來模擬隊列，實現(xiàn)二叉樹的層次遍歷。11/22/202267例6-6按層次遍歷一棵二叉樹對于一棵二叉樹，若規(guī)定遍歷Voidlorder(bitree*t){bitree*q[maxsize],*p;//maxsize為最大容量intf,r;//f,r類似于頭尾指針q[1]=t;f=r=1;while(f<=r){p=q[f];f++;//出隊cout<<p->data;if(p->lchild!=NULL){r++;q[r]=p->1child;}//入隊if(p->rchild!=NULL){r++;q[r]=p->rchild;}//入隊}}11/22/202268Voidlorder(bitree*t)10/116.4線索二叉樹6.4.1線索的概念通過前面介紹的二叉樹可知，遍歷二叉樹實際上就是將樹中所有結點排成一個線性序列(即非線性結構線性化)，在這樣的線性序列中，很容易求得某個結點在某種遍歷下的直接前驅和后繼。然而，有時我們希望不進行遍歷就能快速找到某個結點在某種遍歷下的直接前驅和后繼，這樣，就應該把每個結點的直接前驅和直接后繼記錄下來。為了做到這一點，可以在原來的二叉鏈表結點中，再增加兩個指針域，一個指向前驅，一個指向后繼，但這樣做將會浪費大量存貯單元，存貯空間的利用率相當?shù)?一個結點中有4個指針，1個指左孩子，1個指右孩子，1個指前驅，1個指后繼)，而原來的左、右孩子域有許多空指針又沒有利用起來。為了不浪費存存貯空間，我們利用原有的孩子指針為空時來存放直接前驅和后繼，這樣的指針稱為“線索”，加線索的過程稱為線索化，加了線索的二叉樹，稱為線索二叉樹，對應的二叉鏈表稱為線索二叉鏈表。11/22/2022696.4線索二叉樹6.4.1線索的概念通過前面介紹的在線索二叉樹中，由于有了線索，無需遍歷二叉樹就可以得到任一結點在某種遍歷下的直接前驅和后繼。但是，我們怎樣來區(qū)分孩子指針域中存放的是左、右孩子信息還是直接前驅或直接后繼信息呢?為此，在二叉鏈表結點中，還必須增加兩個標志域ltag、rtag。ltag和rtag定義如下：0lchild域指向結點的左孩子ltag=1lchild域指向結點在某種遍歷下的直接前驅0rchild域指向結點的右孩子rtag=1rchild域指向結點在某種遍歷下的直接后繼11/22/202270在線索二叉樹中，由于有了線索，無需遍歷二叉樹就可以得到任這樣，二叉鏈表中每個結點還是有5個域，但其中只有2個指針，較原來的4個指針要方便。增加線索后的二叉鏈表結點結構可描述如下：2．線索的分類另外，根據(jù)遍歷的不同要求，線索二叉樹可以分為：（1）前序前驅線索二叉樹(只需畫出前驅)（2）前序后繼線索二叉樹(只需畫出后繼)11/22/202271這樣，二叉鏈表中每個結點還是有5個域，但其中只有2個指針（3）前序線索二叉樹(前驅和后繼都要標出)（4）中序前驅線索二叉樹(只需畫出前驅)（5）中序后繼線索二叉樹(只需畫出中序后繼)（6）中序線索二叉樹(中序前驅和后繼都要標出)（7）后序前驅線索二叉樹(只需畫出后序前驅)（8）后序后繼線索二叉樹(中需畫出后序后驅)（9）后序線索二叉樹(后前驅和后繼都要標出)

11/22/202272（3）前序線索二叉樹(前驅和后繼都要標出)10/11/2026.4.2線索的描述1．結點數(shù)據(jù)類型描述structHbitree{elemtypedata;intltag,rtag;//左、右標志域Hbitree*lchild,*rchild;};2．線索的畫法在二叉樹或二叉鏈表中，若左孩子為空，則畫出它的直接前驅，右孩子為空時，則畫出它的直接后繼，左右孩子不為空時，不需畫前驅和后繼。這樣就得到了線索二叉樹或線索二叉鏈表。11/22/2022736.4.2線索的描述1．結點數(shù)據(jù)類型描述structHb前序序列為：ABCD11/22/202274前序序列為：ABCD10/11/202274中序序列為：BADC11/22/202275中序序列為：BADC10/11/202275后序序列為：BDCA11/22/202276后序序列為：BDCA10/11/2022766.4.3線索的算法實現(xiàn)在此，僅介紹中序線索二叉樹的算法實現(xiàn)，設為P為當前結點，pre為p的前驅結點，算法描述如下：voidinth(Hbitree*p)//將P所指二叉樹中序線索化，調用該函數(shù)之前，pre為Null，而樹中所有結點的ltag和rtag都為0。{if(p!=NULL){inth(p->lchild);左子樹線索化11/22/2022776.4.3線索的算法實現(xiàn)在此，僅介紹中序線索二叉樹的算if(p->lchild==NULLl)p->ltag=1;if(p->rchild==NULL)p->rtag;if(pre!=NULL){if(pre->rtag==1)pre->rchild=p;if(p->ltag=1)p->lchild=pre;}pre=p;inth(p->rchild);//右子樹線索化}}11/22/202278if(p->lchild==NULLl)10/11/206.4.4線索二叉樹上的運算1．線索二叉樹上的查找

（1）查找指定結點在中序線索二叉樹中的的直接后繼若所找結點右標志rtag=1，則右孩子域指向中序后繼，否則，中序后繼應為遍歷右子樹時的第一個訪問結點,即右子樹中最左下的結點（參見圖6-19）。從圖6-19中可知，x的后繼為xk。11/22/2022796.4.4線索二叉樹上的運算（1）查找指定結點在中序線索（2）查找指定結點在中序線索二叉樹中的的直接前驅若所找結點左標志ltag=1，則左孩子域指向中序前驅，否則，中序前驅應為遍歷左子樹時的最后一個訪問結點，即左子樹中最右下的結點（參見圖6-20）。從圖6-20中可知，x的前驅為xk。11/22/202280（2）查找指定結點在中序線索二叉樹中的的直接前驅若所找結(3)查找指定點在前序線索二叉樹中的直接后繼前序后繼的查找比較方便，若Ｐ無左孩子，右鏈為后繼，否則左孩子為后繼。(4)查找指定結點在后序線索二叉樹中的直接前驅后序前驅的查找也比較方便，若左孩子為空，左鏈指前驅，否則，若右子樹為空，左孩子指前驅，否則右孩子為前驅。求后序后繼和前序前驅都比較麻煩，在此不再作進一步介紹。11/22/202281(3)查找指定點在前序線索二叉樹中的直接后繼(4)2．線索二叉樹上的遍歷遍歷某種次序的線索二叉樹，只要從該次序下的開始結點出發(fā)，反復找到結點在該次序下的后繼，直到后繼為空。這對于中序線索和前序線索二叉樹很方便，但對于后序線索二叉樹較麻煩(因求后序后繼較麻煩)。故后序線索對于遍歷沒有什么意義。(1)前序遍歷線索二叉樹算法voidpreorder2(Hbitree*t)Hbitree*p;{p=t;//找到開始結點while(p!=NULL){cout<<p->data;p=preordernext(p);//調查函數(shù)找前序后繼}}11/22/2022822．線索二叉樹上的遍歷遍歷某種次序的線索二叉樹，只要從(2)中序遍歷線索二叉樹算法voidinorder2(Hbitree*t){Hbitree*p;p=t;if(p!=NULL){while(p->ltag==0)p=p->lchild;//找開始結點while(p!=NULL){cout<<p->data;p=inordernext(p);//調用函數(shù)找中序后繼}}}11/22/202283(2)中序遍歷線索二叉樹算法10/11/202283從上面算法可知，線索二叉樹上的遍歷較一般二叉樹要方便得多。但是這種方便是以增加線索為代價的，增加線索本身要花費大量時間。所以二叉樹是以二鏈表表示，還是以線索二叉鏈表示，可根據(jù)具體問題而定。3．線索二叉樹的扦入和刪除線索二樹上的查找、遍歷都較一般二叉樹方便，但線索二叉樹也存在其缺點，就扦入和刪除運算而言，線索二叉樹比一般二叉樹的時間花費大，因為除修改指針外，還要修改相應線索。線索二叉樹的扦入和刪除較麻煩，因此本書不再介紹算法11/22/202284從上面算法可知，線索二叉樹上的遍歷較一般二叉樹要方便得多樹、森林和二叉樹的轉換1．樹轉換成二叉樹可以分為三步：（1）

連線指相鄰兄弟之間連線。（2）

抹線指抹掉雙親與除左孩子外其它孩子之間的連線。（3）

旋轉只需將樹作適當?shù)男D。具體實現(xiàn)過程見圖6-25。11/22/202285樹、森林和二叉樹的轉換可以分為三步：（2）

抹11/22/20228610/11/2022862．森林轉換成二叉樹

（1）將森林中每一棵樹分別轉換成二叉樹這在剛才的樹轉換成二叉樹中已經(jīng)介紹過。（2）合并使第n棵樹接入到第n-1棵的右邊并成為它的右子樹，第n-1棵二叉樹接入到第n-2棵的右邊并成為它的右子樹，…，第2棵二叉樹接入到第1棵的右邊并成為它的右子樹，直到最后剩下一棵二叉樹為止。11/22/2022872．森林轉換成二叉樹（1）將森林中每一棵樹分別轉換成二叉11/22/20228810/11/2022883．二叉樹還原成樹或森林

（1）右鏈斷開將二叉樹的根結點的右鏈及右鏈的右鏈等全部斷開，得到若干棵無右子樹的二叉樹。具體操作見圖6-27(b)。

（2）二叉樹還原成樹將（1）中得到的每一棵二叉樹都還原成樹（與樹轉換成二叉樹的步驟剛好相反）。具體操作步驟見圖6-27(c)。11/22/2022893．二叉樹還原成樹或森林（1）右鏈斷開（2）二叉樹還11/22/20229010/