數(shù)據(jù)結(jié)構(gòu)-樹和二叉樹課件

第6章樹和二叉樹6.1樹的定義和基本術(shù)語6.2二叉樹6.3遍歷二叉樹6.4線索二叉樹6.5樹和森林6.6哈夫曼樹第6章樹和二叉樹6.1樹的定義和基本術(shù)語1教學(xué)目的、要求1．領(lǐng)會樹和二叉樹的類型定義，理解樹和二叉樹的結(jié)構(gòu)差別。2．熟記二叉樹的主要特性，并掌握它們的證明方法。3．熟練掌握二叉樹的各種遍歷算法，并能靈活運用遍歷算法實現(xiàn)二叉樹的其它操作。4．理解二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法。5．熟練掌握二叉樹和樹的各種存儲結(jié)構(gòu)及其建立的算法。6．學(xué)會編寫實現(xiàn)樹的各種操作的算法。7．了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。教學(xué)目的、要求1．領(lǐng)會樹和二叉樹的類型定義，理解樹和二叉樹的26.1樹的定義和基本術(shù)語

6.1.1樹的定義樹是由n（n≥0）個結(jié)點組成的有限集合。若n=0，稱為空樹；若n>0，則：①有一個特定的稱為根（root）的結(jié)點。它只有直接后繼，但沒有直接前驅(qū)；②除根結(jié)點以外的其它結(jié)點可以劃分為m（m≥0）個互不相交的有限集合T0，T1，…，Tm-1，每個集合Ti（i=0,1,…,m-1）又是一棵樹，稱為根的子樹，每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個直接后繼。由此可知，樹的定義是一個遞歸的定義，即樹的定義中又用到了樹的概念。6.1樹的定義和基本術(shù)語

6.1.1樹的定義樹是由n（n≥3樹的結(jié)構(gòu)參見下圖：圖6.1樹的結(jié)構(gòu)樹的結(jié)構(gòu)參見下圖：圖6.1樹的結(jié)構(gòu)4在圖6.1(c)中，樹的根結(jié)點為A，該樹還可以分為三個互不相交子集T0，T1，T2，其中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}。在圖6.1(c)中，樹的根結(jié)點為A，該樹還可以分為三個互不相5樹的抽象數(shù)據(jù)類型定義見教材P118-119樹的抽象數(shù)據(jù)類型定義見教材P118-11966.1.2基本術(shù)語1.結(jié)點 指樹中的一個數(shù)據(jù)元素，一般用一個字母表示。2.度 一個結(jié)點包含子樹的數(shù)目，稱為該結(jié)點的度。3.樹葉（葉子） 度為0的結(jié)點，稱為葉子結(jié)點或樹葉，也叫終端結(jié)點。4.孩子結(jié)點 若結(jié)點X有子樹，則子樹的根結(jié)點為X的孩子結(jié)點，也稱為孩子，兒子，子女等。如圖6.1（c）中A的孩子為B，C，D。5.雙親結(jié)點 若結(jié)點X有子女Y，則X為Y的雙親結(jié)點。6.1.2基本術(shù)語1.結(jié)點76.祖先結(jié)點 從根結(jié)點到該結(jié)點所經(jīng)過分枝上的所有結(jié)點為該結(jié)點的祖先，如圖6-1（c）中M的祖先有A，D，H。7.子孫結(jié)點 某一結(jié)點的子女及子女的子女都為該結(jié)點子孫。8.兄弟結(jié)點 具有同一個雙親的結(jié)點，稱為兄弟結(jié)點。9.分枝結(jié)點 除葉子結(jié)點外的所有結(jié)點，為分枝結(jié)點，也叫非終端結(jié)點。10.層數(shù) 根結(jié)點的層數(shù)為1，其它結(jié)點的層數(shù)為從根結(jié)點到該結(jié)點所經(jīng)過的分支數(shù)目再加1。6.祖先結(jié)點811.樹的深度（高度） 樹中結(jié)點所處的最大層數(shù)稱為樹的高度，如空樹的高度為0，只有一個根結(jié)點的樹高度為1。12.樹的度 樹中結(jié)點度的最大值稱為樹的度。13.有序樹 若一棵樹中所有子樹從左到右的排序是有順序的，不能顛倒次序。稱該樹為有序樹。14.無序樹 若一棵樹中所有子樹的次序無關(guān)緊要，則稱為無序樹。15．森林 若干棵互不相交的樹組成的集合為森林。一棵樹可以看成是一個特殊的森林。11.樹的深度（高度）96.1.3樹的表示

1.樹形結(jié)構(gòu)表示法6.1.3樹的表示

1.樹形結(jié)構(gòu)表示法102.凹入法表示法圖6.1（c）的樹的凹入法表示2.凹入法表示法圖6.1（c）的樹的凹入法表示113.嵌套集合表示法圖6.1（c）的嵌套集合表示3.嵌套集合表示法圖6.1（c）的嵌套集合表示124.廣義表表示法對圖6-1（c）的樹結(jié)構(gòu)，廣義表表示法可表示為：（A（B（E（J，K，L），F(xiàn)），C（G），D（H（M），I）））4.廣義表表示法對圖6-1（c）的樹結(jié)構(gòu)，廣義表表示法可表136.1.4樹的性質(zhì)性質(zhì)1樹中的結(jié)點數(shù)等于所有結(jié)點的度加1。證明：根據(jù)樹的定義，在一棵樹中，除根結(jié)點以外，每個結(jié)點有且僅有一個直接前驅(qū)，也就是說，每個結(jié)點與指向它的一個分支一一對應(yīng)，所以，除根結(jié)點以外的結(jié)點數(shù)等于所有結(jié)點的分支數(shù)（即度數(shù)），而根結(jié)點無直接前驅(qū)，因此，樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加1。6.1.4樹的性質(zhì)性質(zhì)1樹中的結(jié)點數(shù)等于所有結(jié)點的度加14性質(zhì)2度為k的樹中第i層上最多有ki-1個結(jié)點（i≥1）。下面用數(shù)學(xué)歸納法證明：對于i=1，顯然成立，假設(shè)對于i-1層，上述條件成立，即第i-1層最多有ki-2個結(jié)點，對于第i層，結(jié)點數(shù)最多為第i-1層結(jié)點數(shù)的k倍（因為度為k），故第i層的結(jié)點數(shù)為ki-2*k=ki-1。性質(zhì)2度為k的樹中第i層上最多有ki-1個結(jié)點（i≥1）15性質(zhì)3深度為h的k叉樹最多有個結(jié)點。 證明： 由性質(zhì)2可知，若每一層的結(jié)點數(shù)最多，則整個k叉樹結(jié)點數(shù)最多，共有

當(dāng)一棵K叉樹上的結(jié)點數(shù)達(dá)到時，稱為滿K叉樹。性質(zhì)3深度為h的k叉樹最多有個結(jié)16性質(zhì)4具有n個結(jié)點的k叉樹的最小深度為。 （表示取不小于x的最小整數(shù)）證明：設(shè)具有n個結(jié)點的k叉樹的深度為h，在該樹的前面h-1層都是滿的，即每一層的結(jié)點數(shù)等于ki-1個(1≤i≤h-1)，第h層（即最后一層）的結(jié)點數(shù)可能滿，也可能不滿，這時，該樹具有最小的深度。 由性質(zhì)3知道，結(jié)點數(shù)n應(yīng)滿足下面條件：性質(zhì)4具有n個結(jié)點的k叉樹的最小深度為17通過轉(zhuǎ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=通過轉(zhuǎn)換為：kh-1<n(k-1)+1≤kh，再取以k為底的186.2二叉樹為何要重點研究每結(jié)點最多只有兩個"叉"的樹？①二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；②可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性。6.2二叉樹為何要重點研究每結(jié)點最多只有兩個"叉"的樹196.2.1二叉樹的定義和樹結(jié)構(gòu)定義類似，二叉樹的定義也可以遞歸形式給出：二叉樹是n（n≥0）個結(jié)點的有限集，它或者是空集（n=0），或者由一個根結(jié)點及兩棵不相交的左子樹和右子樹組成。6.2.1二叉樹的定義和樹結(jié)構(gòu)定義類似，二叉樹的定義也可以20二叉樹的特點是每個結(jié)點最多有兩個孩子，或者說，在二叉樹中，不存在度大于2的結(jié)點，并且二叉樹是有序樹（樹為無序樹），其子樹的順序不能顛倒，因此，二叉樹有五種不同的形態(tài)，參見圖6.5。圖6.5二叉樹的五種不同形態(tài)二叉樹的特點是每個結(jié)點最多有兩個孩子，或者說，在二叉樹中，不21問：具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？問：具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？22有五種有五種23二叉樹的的抽象數(shù)據(jù)類型定義見教材P121。二叉樹的的抽象數(shù)據(jù)類型定義見教材P121。24性質(zhì)1二叉樹的第i層結(jié)點數(shù)，最多為2i-1個（i≥1）。性質(zhì)2深度為k的二叉樹最大結(jié)點數(shù)為2k-1（i≥1）。性質(zhì)1二叉樹的第i層結(jié)點數(shù)，最多為2i-1個（i≥1）。25性質(zhì)3對任意一棵二叉樹，如果葉子結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則有n0=n2+1。證明：設(shè)二叉樹中度為1的結(jié)點個數(shù)為n1，根據(jù)二叉樹的定義可知，該二叉樹的結(jié)點數(shù)n=n0+n1+n2。又因為在二叉樹中，度為0的結(jié)點沒有孩子，度為1的結(jié)點有1個孩子，度為2的結(jié)點有2個結(jié)孩子，故該二叉樹的孩子結(jié)點數(shù)為n0*0+n1*1+n2*2。而一棵二叉樹中，除根結(jié)點外所有的結(jié)點都為孩子結(jié)點，故該二叉樹的結(jié)點數(shù)應(yīng)為孩子結(jié)點數(shù)加1即：n=n0*0+n1*1+n2*2+1。因此，有n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。性質(zhì)3對任意一棵二叉樹，如果葉子結(jié)點個數(shù)為n0，度為2的26為繼續(xù)給出二叉樹的其它性質(zhì)，先定義兩種特殊的二叉樹。①滿二叉樹深度為k具有2k-1個結(jié)點的二叉樹，稱為滿二叉樹。從上面滿二叉樹定義可知，必須是二叉樹的每一層上的結(jié)點數(shù)都達(dá)到最大，否則就不是滿二叉樹。②完全二叉樹對滿二叉樹的結(jié)點，從根結(jié)點起，自上而下，自左至右進(jìn)行連續(xù)編號。如果一棵具有n個結(jié)點的深度為k的二叉樹，它的每一個結(jié)點都與深度為k的滿二叉樹中編號為1~n的結(jié)點一一對應(yīng)，則稱這棵二叉樹為完全二叉樹。為繼續(xù)給出二叉樹的其它性質(zhì)，先定義兩種特殊的二叉樹。27從滿二叉樹及完全二叉樹定義可以知道，滿二叉樹一定是一棵完全二叉樹，反之完全二叉樹不一定是一棵滿二叉樹。滿二叉樹的葉子結(jié)點全部在最底層，而完全二叉樹的葉子結(jié)點可以分布在最下面兩層。深度為4的滿二叉樹和完全二叉樹如圖6.6所示。圖6.6滿二叉樹和完全二叉樹從滿二叉樹及完全二叉樹定義可以知道，滿二叉樹一定是一棵完全二28性質(zhì)4具有n個結(jié)點的完全二叉樹深度為或。性質(zhì)5如果將一棵有n個結(jié)點的完全二叉樹從上到下，從左到右對結(jié)點編號1，2，…，n，并簡稱編號為i的結(jié)點為i(1≤i≤n)，則有如下結(jié)論成立： ①若i=1，則結(jié)點i為根結(jié)點，無雙親，否則i的雙親為； ②若2i>n，則結(jié)點i無左孩子，否則i的左孩子為2i。即滿足2i>n的結(jié)點為葉子結(jié)點； ③若2i+1>n，則結(jié)點i無右孩子，否則i的右孩子為2i+1； ④若結(jié)點i為奇數(shù)且不等于1，則它的左兄弟為i-1； ⑤若結(jié)點i為偶數(shù)且不等于n，它的右兄弟為i+1； ⑥結(jié)點i所在層數(shù)(層次)為；性質(zhì)4具有n個結(jié)點的完全二叉樹深度為296.2.3二叉樹的存貯結(jié)構(gòu)

1.順序存貯結(jié)構(gòu)按二叉樹的結(jié)點"自上而下、從左至右"編號，用一組連續(xù)的存儲單元存儲。若該二叉樹為非完全二叉樹，則必須將相應(yīng)位置空出來，使存放的結(jié)果符合完全二叉樹形狀。6.2.3二叉樹的存貯結(jié)構(gòu)

1.順序存貯結(jié)構(gòu)按二叉樹的結(jié)30圖6.7二叉樹的順序存儲對于一棵二叉樹，若采用順序存貯時，當(dāng)它為完全二叉樹時，比較方便,若為非完全二叉樹，將會浪費大量存貯存貯單元。最壞的非完全二叉樹是全部只有右分支，設(shè)高度為K，則需占用2K-1個存貯單元，而實際只有k個元素，實際只需k個存儲單元。因此，對于非完全二叉樹，宜采用下面的鏈?zhǔn)酱鎯Y(jié)構(gòu)。圖6.7二叉樹的順序存儲對于一棵二叉樹，若采用順序存貯時，312.二叉鏈表存貯結(jié)構(gòu)

⑴二叉鏈表表示將一個結(jié)點分成三部分，一部分存放結(jié)點本身信息，另外兩部分為指針，分別存放左、右孩子的地址。注：如果需要倒查某結(jié)點的雙親，可以再增加一個雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。lchilddatarchild2.二叉鏈表存貯結(jié)構(gòu)

⑴二叉鏈表表示將一個結(jié)點分成三部分32對于圖6.7所示二叉樹，用二叉鏈表形式描述。圖6.8二叉樹的二叉鏈表表示對于圖6.7所示二叉樹，用二叉鏈表形式描述。圖6.8二叉樹33⑵二叉鏈表的數(shù)據(jù)類型

bitree.h//二叉鏈表定義#include<iostream>usingnamespacestd;typedefcharTElemType;structBiTNode{ TElemTypedata; BiTNode*lchild,*rchild;};typedefBiTNode*BiTree;⑵二叉鏈表的數(shù)據(jù)類型

bitree.h//二叉鏈表定義34voidinitBiTree(BiTree&T);voidcreateBiTree(BiTree&T);//遞歸前序遍歷voidpreOrderTraverse(BiTreeT,void(*visit)(TElemType));//非遞歸前序遍歷voidpreOrderTraverse1(BiTreeT,void(*visit)(TElemType));//遞歸中序遍歷voidinOrderTraverse(BiTreeT,void(*visit)(TElemType));//遞歸后序遍歷voidpostOrderTraverse(BiTreeT,void(*visit)(TElemType));voidinitBiTree(BiTree&T);35⑶二叉鏈表的建立為了后面遍歷二叉樹方便，先介紹建立二叉鏈表的算法（假設(shè)ElemType為char型）。⑶二叉鏈表的建立為了后面遍歷二叉樹方便，先介紹建立二叉鏈表36//按先序次序輸入二叉樹中結(jié)點的值（'#'表示空格），//構(gòu)造二叉鏈表表示的二叉樹T。voidcreateBiTree(BiTree&T){ TElemTypech; cin>>ch; if(ch=='#')//空 T=NULL; else{ T=newBiTNode; if(!T) exit(1); T->data=ch;//生成根結(jié)點 createBiTree(T->lchild);//構(gòu)造左子樹 createBiTree(T->rchild);//構(gòu)造右子樹 }}//按先序次序輸入二叉樹中結(jié)點的值（'#'表示空格），376.3遍歷二叉樹遍歷是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎(chǔ)和核心。所謂遍歷二叉樹，就是遵從某種次序，訪問二叉樹中的所有結(jié)點，使得每個結(jié)點僅被訪問一次。這里提到的"訪問"是指對結(jié)點施行某種操作，操作可以是輸出結(jié)點信息，修改結(jié)點的數(shù)據(jù)值等，但要求這種訪問不破壞它原來的數(shù)據(jù)結(jié)構(gòu)。在本書中，我們規(guī)定訪問是輸出結(jié)點信息data，且以二叉鏈表作為二叉樹的存貯結(jié)構(gòu)。6.3遍歷二叉樹遍歷是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運38由于二叉樹是一種非線性結(jié)構(gòu)，每個結(jié)點可能有一個以上的直接后繼，因此，必須規(guī)定遍歷的規(guī)則，并按此規(guī)則遍歷二叉樹，最后得到二叉樹所有結(jié)點的一個線性序列。令L、R、D分別代表二叉樹的左子樹、右子樹、根結(jié)點，則遍歷二叉樹有6種規(guī)則：DLR、DRL、LDR、LRD、RDL、RKD。若規(guī)定二叉樹中必須先左后右(左右順序不能顛倒)，則只有DLR、LDR、LRD三種遍歷規(guī)則。DLR稱為前根遍歷(或前序遍歷、先序遍歷、先根遍歷)，LDR稱為中根遍歷(或中序遍歷)，LRD稱為后根遍歷(或后序遍歷)。由于二叉樹是一種非線性結(jié)構(gòu)，每個結(jié)點可能有一個以上的直接后繼396.3.1前序遍歷所謂前序遍歷，就是根結(jié)點最先遍歷，其次左子樹，最后右子樹。6.3.1前序遍歷所謂前序遍歷，就是根結(jié)點最先遍歷，其次左401.遞歸遍歷前序遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結(jié)束；否則①輸出根結(jié)點；②前根遍歷左子樹;③前根遍歷右子樹。1.遞歸遍歷前序遍歷二叉樹的遞歸遍歷算法描述為：41//先序遞歸遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次voidpreOrderTraverse(BiTreeT,void(*visit)(TElemType)){ if(T){//T不空 visit(T->data);//先訪問根結(jié)點 preOrderTraverse(T->lchild,visit);//再先序遍歷左子樹 preOrderTraverse(T->rchild,visit);//最后先序遍歷右子樹 }}//先序遞歸遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一422.非遞歸遍歷利用一個一維數(shù)組作棧，來存貯二叉鏈表中結(jié)點，算法思想為：從二叉樹根結(jié)點開始，沿左子樹一直走到末端(左孩子為空)為止，在走的過程中，訪問所遇結(jié)點，并依次把所遇結(jié)點進(jìn)棧，當(dāng)左子樹為空時，從棧頂退出某結(jié)點，并將指針指向該結(jié)點的右孩子。如此重復(fù)，直到棧為空或指針為空止。2.非遞歸遍歷利用一個一維數(shù)組作棧，來存貯二叉鏈表中結(jié)點，43//前序遍歷二叉樹T的非遞歸算法(利用棧)，對每個數(shù)據(jù)元素調(diào)用函數(shù)VisitvoidpreOrderTraverse1(BiTreeT,void(*visit)(TElemType)){ BiTrees[100]; inttop=0;//top為棧頂指針 while((T!=NULL)||(top>0)){ while(T!=NULL){ visit(T->data); s[top++]=T; T=T->lchild; } T=s[--top]; T=T->rchild; }}//前序遍歷二叉樹T的非遞歸算法(利用棧)，對每個數(shù)據(jù)元素446.3.2中序遍歷所謂中序遍歷，就是根在中間，先左子樹，然后根結(jié)點，最后右子樹。中序遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結(jié)束；否則①中根遍歷左子樹;②輸出根結(jié)點;③中根遍歷右子樹。6.3.2中序遍歷所謂中序遍歷，就是根在中間，先左子樹，然45//中序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次voidinOrderTraverse(BiTreeT,void(*visit)(TElemType)){ if(T){ inOrderTraverse(T->lchild,visit);//先中序遍歷左子樹 visit(T->data);//再訪問根結(jié)點 inOrderTraverse(T->rchild,visit);//最后中序遍歷右子樹 }}//中序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次466.3.3后序遍歷所謂后序遍歷，就是根在最后，即先左子樹，然后右子樹，最后根結(jié)點。后序遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結(jié)束；否則①后根遍歷左子樹:②后根遍歷歷子樹;③訪問根結(jié)點。6.3.3后序遍歷所謂后序遍歷，就是根在最后，即先左子樹，47//后序遞歸遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次voidpostOrderTraverse(BiTreeT,void(*visit)(TElemType)){ if(T){ inOrderTraverse(T->lchild,visit);//后序遍歷左子樹 inOrderTraverse(T->rchild,visit);//再后序遍歷右子樹 visit(T->data);//最后訪問根結(jié)點 }}//后序遞歸遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次486.3.4按層次遍歷對于一棵二叉樹，若規(guī)定遍歷順序為從上到下(上層遍歷完才進(jìn)入下層)，從左到右(同一層從左到右進(jìn)行，這樣的遍歷稱為按層次遍歷。6.3.4按層次遍歷對于一棵二叉樹，若規(guī)定遍歷順序為從上到49下面用一個一維數(shù)組來模擬隊列，實現(xiàn)二叉樹的層次遍歷。下面用一個一維數(shù)組來模擬隊列，實現(xiàn)二叉樹的層次遍歷。50//層序遍歷T(利用隊列),對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次voidlevelOrderTraverse(BiTreeT,void(*visit)(TElemType)){ BiTreeq[100],p; intf,r;//f,r類似于頭尾指針 q[0]=T; f=0; r=1; while(f<r){ p=q[f++];//出隊 visit(p->data); if(p->lchild!=NULL) q[r++]=p->lchild;//入隊 if(p->rchild!=NULL) q[r++]=p->rchild;//入隊 }}//層序遍歷T(利用隊列),對每個結(jié)點調(diào)用函數(shù)Visit一次516.4線索二叉樹

6.4.1線索的概念通過前面介紹的二叉樹可知，遍歷二叉樹實際上就是將樹中所有結(jié)點排成一個線性序列（即非線性結(jié)構(gòu)線性化），在這樣的線性序列中，很容易求得某個結(jié)點在某種遍歷下的直接前驅(qū)和后繼。然而，有時我們希望不進(jìn)行遍歷就能快速找到某個結(jié)點在某種遍歷下的直接前驅(qū)和后繼，這樣，就應(yīng)該把每個結(jié)點的直接前驅(qū)和直接后繼記錄下來。6.4線索二叉樹

6.4.1線索的概念通過前面介紹的二叉52為了做到這一點，可以在原來的二叉鏈表結(jié)點中，再增加兩個指針域，一個指向前驅(qū)，一個指向后繼，但這樣做將會浪費大量存貯單元，存貯空間的利用率相當(dāng)?shù)?一個結(jié)點中有4個指針，1個指左孩子，1個指右孩子，1個指前驅(qū)，1個指后繼)，而原來的左、右孩子域有許多空指針又沒有利用起來（在有n個結(jié)點的二叉鏈表中必定存在n+1個空鏈域）。為了做到這一點，可以在原來的二叉鏈表結(jié)點中，再增加兩個指針域53為了不浪費存存貯空間，我們利用原有的孩子指針為空時來存放直接前驅(qū)和后繼，這樣的指針稱為"線索"，加線索的過程稱為線索化，加了線索的二叉樹，稱為線索二叉樹，對應(yīng)的二叉鏈表稱為線索二叉鏈表。為了不浪費存存貯空間，我們利用原有的孩子指針為空時來存放直接54在線索二叉樹中，由于有了線索，無需遍歷二叉樹就可以得到任一結(jié)點在某種遍歷下的直接前驅(qū)和后繼。但是，我們怎樣來區(qū)分孩子指針域中存放的是左、右孩子信息還是直接前驅(qū)或直接后繼信息呢?為此，在二叉鏈表結(jié)點中，還必須增加兩個標(biāo)志域ltag、rtag。在線索二叉樹中，由于有了線索，無需遍歷二叉樹就可以得到任一結(jié)55ltag和rtag定義如下：這樣，二叉鏈表中每個結(jié)點還是有5個域，但其中只有2個指針，較原來的4個指針要方便。增加線索后的二叉鏈表結(jié)點結(jié)構(gòu)可描述如下：lchildltagdatartagrchildltag和rtag定義如下：這樣，二叉鏈表中每個結(jié)點還是有556前序序列為：ABCD。圖前序線索前序序列為：ABCD。圖前序線索57中序序列為：BADC。圖中序線索中序序列為：BADC。圖中序線索58后序序列為：BDCA。圖后序線索后序序列為：BDCA。圖后序線索596.4.3線索的算法實現(xiàn)在此，僅介紹中序線索二叉樹的算法實現(xiàn)。為方便起見，依照線性表的存儲結(jié)構(gòu)，在二叉樹的線索鏈表上也添加一個頭結(jié)點，并令其lchild域的指針指向二叉樹的根結(jié)點，其rchild域的指針指向中序遍歷時訪問的最后一個結(jié)點，并令二叉樹中序序列中的第一個結(jié)點的lchild域指針和最后一個結(jié)點的rchild域的指針均指向頭結(jié)點。6.4.3線索的算法實現(xiàn)在此，僅介紹中序線索二叉樹的算法實60圖中序線索鏈表（中序序列為：BADC）圖中序線索鏈表（中序序列為：BADC）61由于線索化的實質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷時才能得到，因此線索化的過程即為在遍歷的過程中修改空指針的過程。為了記下遍歷過程中訪問結(jié)點的先后關(guān)系，需附設(shè)一個指針pre始終指向剛剛訪問過的結(jié)點。由于線索化的實質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線621.線索鏈表類型定義

inthreading.h#include<iostream>usingnamespacestd;typedefcharTElemType;enumPointerTag{Link,Thread};//Link==0:指針，Thread==1:線索structBiThrNode{ TElemTypedata; BiThrNode*lchild,*rchild; PointerTagltag,rtag;};typedefBiThrNode*BiThrTree;1.線索鏈表類型定義

inthreading.h#incl63voidcreateBiThrTree(BiThrTree&T);voidpreOrderTraverse(BiThrTreeT,void(*visit)(TElemType));BiThrNode*inOrderThreading(BiThrTreeT);voidinTraverseThr(BiThrTreeT,void(*visit)(TElemType));voidcreateBiThrTree(BiThrTree642.實現(xiàn)

inthreading.cpp#include"inthreading.h"http://按先序次序輸入二叉樹中結(jié)點的值（'#'表示空格），構(gòu)造二叉線索樹TvoidcreateBiThrTree(BiThrTree&T){ TElemTypech; cin>>ch; if(ch=='#')//空 T=NULL; else{ T=newBiThrNode; if(!T) exit(1); T->data=ch;//生成根結(jié)點

createBiThrTree(T->lchild);//構(gòu)造左子樹 if(T->lchild)//有左孩子 T->ltag=Link; createBiThrTree(T->rchild);//構(gòu)造右子樹 if(T->rchild)//有右孩子 T->rtag=Link; }}2.實現(xiàn)

inthreading.cpp#include65//先序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次voidpreOrderTraverse(BiThrTreeT,void(*visit)(TElemType)){ if(T){//T不空 visit(T->data);//先訪問根結(jié)點 preOrderTraverse(T->lchild,visit);//再先序遍歷左子樹 preOrderTraverse(T->rchild,visit);//最后先序遍歷右子樹 }}BiThrTreepre;//全局變量,始終指向剛剛訪問過的結(jié)點//先序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一66voidinThreading(BiThrTreep){//中序遍歷進(jìn)行中序線索化 if(p){ inThreading(p->lchild);//左子樹線索化 if(!p->lchild){//沒有左孩子 p->ltag=Thread;//前驅(qū)線索 p->lchild=pre;//左孩子指針指向前驅(qū) } if(!pre->rchild){//前驅(qū)沒有右孩子 pre->rtag=Thread;//后繼線索 pre->rchild=p;//前驅(qū)右孩子指針指向后繼(當(dāng)前結(jié)點p) } pre=p;//保持pre始終指向剛剛訪問過的結(jié)點 inThreading(p->rchild);//右子樹線索化 }}voidinThreading(BiThrTreep){67//中序遍歷二叉樹T,并將其中序線索化,BiThrNode*inOrderThreading(BiThrTreeT){ BiThrNode*Thrt=newBiThrNode;//Thrt指向頭結(jié)點Thrt->ltag=Link; Thrt->rtag=Thread; Thrt->rchild=Thrt;//右指針回指 if(!T)//若二叉樹空，則左指針回指 Thrt->lchild=Thrt; else{ Thrt->lchild=T; pre=Thrt; inThreading(T);//中序遍歷進(jìn)行中序線索化 pre->rtag=Thread;//最后一個結(jié)點線索化 pre->rchild=Thrt; Thrt->rchild=pre; } returnThrt;}//中序遍歷二叉樹T,并將其中序線索化,68//中序遍歷二叉線索樹T(頭結(jié)點)的非遞歸算法voidinTraverseThr(BiThrTreeT,void(*visit)(TElemType)){ BiThrTreep; p=T->lchild;//p指向根結(jié)點 while(p!=T){//空樹或遍歷結(jié)束時,p==T while(p->ltag==Link) p=p->lchild; visit(p->data);//訪問左子樹為空的結(jié)點 while(p->rtag==Thread&&p->rchild!=T){ p=p->rchild; visit(p->data);//訪問后繼結(jié)點 } p=p->rchild; }}//中序遍歷二叉線索樹T(頭結(jié)點)的非遞歸算法696.5樹和森林

6.5.1樹的存儲結(jié)構(gòu)

1.雙親表示法它是以一組連續(xù)的存儲單元來存放樹中的結(jié)點，每個結(jié)點有兩個域：一個是data域，存放結(jié)點信息，另一個是parent域，用來存放雙親的位置(指針)。樹的雙親表示法6.5樹和森林

6.5.1樹的存儲結(jié)構(gòu)

1.雙親表示法702.孩子表示法將一個結(jié)點所有孩子鏈接成一個單鏈表形，而樹中有若干個結(jié)點，故有若干個單鏈表，每個單鏈表有一個表頭結(jié)點，所有表頭結(jié)點用一個數(shù)組來描述。樹的孩子表示法2.孩子表示法將一個結(jié)點所有孩子鏈接成一個單鏈表形，而樹中713.雙親孩子表示法將第1、2兩種方法結(jié)合起來，則得到雙親孩子表示法。雙親孩子表示法3.雙親孩子表示法將第1、2兩種方法結(jié)合起來，則得到雙親孩724.孩子兄弟表示法類似于二叉鏈表，但第一根鏈指向第一個孩子，第二根鏈指向下一個兄弟。孩子兄弟表示法4.孩子兄弟表示法類似于二叉鏈表，但第一根鏈指向第一個孩子736.5.2樹、森林和二叉樹的轉(zhuǎn)換

1.樹轉(zhuǎn)換成二叉樹（孩子--兄弟表示法）可以分為三步：①加線 將樹中同一結(jié)點的兄弟相連;②抹線 保留結(jié)點的最左孩子連線，刪除其它孩子連線；③旋轉(zhuǎn)將同一孩子的連線繞左孩子旋轉(zhuǎn)45度角。6.5.2樹、森林和二叉樹的轉(zhuǎn)換

1.樹轉(zhuǎn)換成二叉樹（孩74討論：二叉樹怎樣還原為樹？要點：逆操作，把所有右孩子變?yōu)樾值?！樹轉(zhuǎn)換成二叉樹討論：二叉樹怎樣還原為樹？樹轉(zhuǎn)換成二叉樹752.森林轉(zhuǎn)換成二叉樹①將森林中每一棵樹分別轉(zhuǎn)換成二叉樹；②合并：使第n棵樹接入到第n-1棵的右邊并成為它的右子樹，第n-1棵二叉樹接入到第n-2棵的右邊并成為它的右子樹，…，第2棵二叉樹接入到第1棵的右邊并成為它的右子樹，直到最后剩下一棵二叉樹為止。2.森林轉(zhuǎn)換成二叉樹①將森林中每一棵樹分別轉(zhuǎn)換成二叉樹；76森林轉(zhuǎn)換成二叉樹森林轉(zhuǎn)換成二叉樹773.二叉樹還原成樹或森林①右鏈斷開 將二叉樹的根結(jié)點的右鏈及右鏈的右鏈等全部斷開，得到若干棵無右子樹的二叉樹。②二叉樹還原成樹 將①中得到的每一棵二叉樹都還原成樹（與樹轉(zhuǎn)換成二叉樹的步驟剛好相反）。3.二叉樹還原成樹或森林①右鏈斷開78二叉樹還原成森林的過程二叉樹還原成森林的過程796.5.3樹和森林的遍歷在樹和森林中，一個結(jié)點可能有兩棵以上的子樹，所以不宜討論它們的中序遍歷，即樹和森林只有先序遍歷和后序遍歷。6.5.3樹和森林的遍歷在樹和森林中，一個結(jié)點可能有兩棵以801.先序遍歷⑴樹的先序遍歷 若樹非空，則先訪問根結(jié)點，然后依次先序遍歷各子樹。⑵森林的先序遍歷 若森林非空，則先訪問森林中第一棵樹的根結(jié)點，再先序遍歷第一棵樹各子樹，接著先序遍歷第二棵樹、第三棵樹、…、直到最后一棵樹。1.先序遍歷⑴樹的先序遍歷812.后序遍歷⑴樹的后序遍歷 若樹非空，則依次后序遍歷各子樹，最后訪問根結(jié)點。⑵森林的后序遍歷 按順序后序遍歷森林中的每一棵樹。另外，請注意，樹和森林的先序遍歷等價于它轉(zhuǎn)換成的二叉樹的先序遍歷，樹和森林的后序遍歷等價于它轉(zhuǎn)換成的二叉樹的中序遍歷。2.后序遍歷⑴樹的后序遍歷826.6哈夫曼樹

6.6.1基本術(shù)語1.路徑和路徑長度 在一棵樹中，從一個結(jié)點往下可以達(dá)到的孩子或子孫結(jié)點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。 若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。2.結(jié)點的權(quán)及帶權(quán)路徑長度 若將樹中結(jié)點賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結(jié)點的權(quán)。 結(jié)點的帶權(quán)路徑長度為：從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。6.6哈夫曼樹

6.6.1基本術(shù)語1.路徑和路徑長度833.樹的帶權(quán)路徑長度 樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點的帶權(quán)路徑長度之和，記為其中n為葉子結(jié)點數(shù)目，wk為第k個葉子結(jié)點的權(quán)值，lk為第k個葉子結(jié)點的路徑長度。3.樹的帶權(quán)路徑長度844.哈夫曼樹 在一棵二叉樹中，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffmantree)。 例如，給定葉子結(jié)點的權(quán)分別為1,3,5,7，則可以得到如下圖所示的不同二叉樹。具有不同帶權(quán)路徑長度的二叉樹在哈夫曼樹中，權(quán)值大的結(jié)點離根最近。4.哈夫曼樹具有不同帶權(quán)路徑長度的二叉樹在哈夫曼樹中，權(quán)值856.6.2哈夫曼樹構(gòu)造假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點。n個權(quán)值分別設(shè)為w1,w2,…,wn，則哈夫曼樹的構(gòu)造規(guī)則為：①將w1,w2,…,wn看成是有n棵樹的森林(每棵樹僅有一個結(jié)點)；②在森林中選出兩個根結(jié)點的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；③從森林中刪除選取的兩棵樹，并將新樹加入森林；④重復(fù)①、②步，直到森林中只剩一棵樹為止，該樹即為我們所求得的哈夫曼樹。6.6.2哈夫曼樹構(gòu)造假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有86下面給出哈夫曼樹的構(gòu)造過程，假設(shè)給定的葉子結(jié)點的權(quán)分別為1,5,7,3，則構(gòu)造哈夫曼樹過程如圖所示。哈夫曼樹構(gòu)造的過程從上圖可知，n個權(quán)值構(gòu)造哈夫曼樹需n-1次合并，每次合并，森林中的樹數(shù)目減1，最后森林中只剩下一棵樹，即為我們求得的哈夫曼樹。下面給出哈夫曼樹的構(gòu)造過程，假設(shè)給定的葉子結(jié)點的權(quán)分別為1,876.6.3哈夫曼樹的應(yīng)用

1.哈夫曼編碼通信中，可以采用0、1的不同排列來表示不同的字符，稱為二進(jìn)制編碼。而哈夫曼樹在數(shù)據(jù)編碼中的應(yīng)用，是數(shù)據(jù)的最小冗余編碼問題，它是數(shù)據(jù)壓縮學(xué)的基礎(chǔ)。若每個字符出現(xiàn)的頻率相同，則可以采用等長的二進(jìn)制編碼，若頻率不同，則可以采用不等長的二進(jìn)編碼，頻率較大的采用位數(shù)較少的編碼，頻率較小的字符采用位數(shù)較多的編碼，這樣可以使字符的整體編碼長度最小，這就是最小冗余編碼的問題。6.6.3哈夫曼樹的應(yīng)用

1.哈夫曼編碼通信中，可以采用88而哈夫曼編碼就是一種不等長的二進(jìn)制編碼，且哈夫曼樹是一種最優(yōu)二叉樹，它的編碼也是一種最優(yōu)編碼，在哈夫曼樹中，規(guī)定往左編碼為0，往右編碼為1，則得到葉子結(jié)點編碼為從根結(jié)點到葉子結(jié)點中所有路徑中0和1的順序排列。而哈夫曼編碼就是一種不等長的二進(jìn)制編碼，且哈夫曼樹是一種最優(yōu)89例如，給定權(quán){1,5,7,3}，得到的哈夫曼樹及編碼見下圖(假定權(quán)值就代表該字符名字)。哈夫曼編碼例如，給定權(quán){1,5,7,3}，得到的哈夫曼樹及編碼見下圖902.哈夫曼譯碼在通信中，若將字符用哈夫曼編碼形式發(fā)送出去，對方接收到編碼后，將編碼還原成字符的過程，稱為哈夫曼譯碼。2.哈夫曼譯碼在通信中，若將字符用哈夫曼編碼形式發(fā)送出去，91第6章樹和二叉樹6.1樹的定義和基本術(shù)語6.2二叉樹6.3遍歷二叉樹6.4線索二叉樹6.5樹和森林6.6哈夫曼樹第6章樹和二叉樹6.1樹的定義和基本術(shù)語92教學(xué)目的、要求1．領(lǐng)會樹和二叉樹的類型定義，理解樹和二叉樹的結(jié)構(gòu)差別。2．熟記二叉樹的主要特性，并掌握它們的證明方法。3．熟練掌握二叉樹的各種遍歷算法，并能靈活運用遍歷算法實現(xiàn)二叉樹的其它操作。4．理解二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法。5．熟練掌握二叉樹和樹的各種存儲結(jié)構(gòu)及其建立的算法。6．學(xué)會編寫實現(xiàn)樹的各種操作的算法。7．了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。教學(xué)目的、要求1．領(lǐng)會樹和二叉樹的類型定義，理解樹和二叉樹的936.1樹的定義和基本術(shù)語

6.1.1樹的定義樹是由n（n≥0）個結(jié)點組成的有限集合。若n=0，稱為空樹；若n>0，則：①有一個特定的稱為根（root）的結(jié)點。它只有直接后繼，但沒有直接前驅(qū)；②除根結(jié)點以外的其它結(jié)點可以劃分為m（m≥0）個互不相交的有限集合T0，T1，…，Tm-1，每個集合Ti（i=0,1,…,m-1）又是一棵樹，稱為根的子樹，每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個直接后繼。由此可知，樹的定義是一個遞歸的定義，即樹的定義中又用到了樹的概念。6.1樹的定義和基本術(shù)語

6.1.1樹的定義樹是由n（n≥94樹的結(jié)構(gòu)參見下圖：圖6.1樹的結(jié)構(gòu)樹的結(jié)構(gòu)參見下圖：圖6.1樹的結(jié)構(gòu)95在圖6.1(c)中，樹的根結(jié)點為A，該樹還可以分為三個互不相交子集T0，T1，T2，其中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}。在圖6.1(c)中，樹的根結(jié)點為A，該樹還可以分為三個互不相96樹的抽象數(shù)據(jù)類型定義見教材P118-119樹的抽象數(shù)據(jù)類型定義見教材P118-119976.1.2基本術(shù)語1.結(jié)點 指樹中的一個數(shù)據(jù)元素，一般用一個字母表示。2.度 一個結(jié)點包含子樹的數(shù)目，稱為該結(jié)點的度。3.樹葉（葉子） 度為0的結(jié)點，稱為葉子結(jié)點或樹葉，也叫終端結(jié)點。4.孩子結(jié)點 若結(jié)點X有子樹，則子樹的根結(jié)點為X的孩子結(jié)點，也稱為孩子，兒子，子女等。如圖6.1（c）中A的孩子為B，C，D。5.雙親結(jié)點 若結(jié)點X有子女Y，則X為Y的雙親結(jié)點。6.1.2基本術(shù)語1.結(jié)點986.祖先結(jié)點 從根結(jié)點到該結(jié)點所經(jīng)過分枝上的所有結(jié)點為該結(jié)點的祖先，如圖6-1（c）中M的祖先有A，D，H。7.子孫結(jié)點 某一結(jié)點的子女及子女的子女都為該結(jié)點子孫。8.兄弟結(jié)點 具有同一個雙親的結(jié)點，稱為兄弟結(jié)點。9.分枝結(jié)點 除葉子結(jié)點外的所有結(jié)點，為分枝結(jié)點，也叫非終端結(jié)點。10.層數(shù) 根結(jié)點的層數(shù)為1，其它結(jié)點的層數(shù)為從根結(jié)點到該結(jié)點所經(jīng)過的分支數(shù)目再加1。6.祖先結(jié)點9911.樹的深度（高度） 樹中結(jié)點所處的最大層數(shù)稱為樹的高度，如空樹的高度為0，只有一個根結(jié)點的樹高度為1。12.樹的度 樹中結(jié)點度的最大值稱為樹的度。13.有序樹 若一棵樹中所有子樹從左到右的排序是有順序的，不能顛倒次序。稱該樹為有序樹。14.無序樹 若一棵樹中所有子樹的次序無關(guān)緊要，則稱為無序樹。15．森林 若干棵互不相交的樹組成的集合為森林。一棵樹可以看成是一個特殊的森林。11.樹的深度（高度）1006.1.3樹的表示

1.樹形結(jié)構(gòu)表示法6.1.3樹的表示

1.樹形結(jié)構(gòu)表示法1012.凹入法表示法圖6.1（c）的樹的凹入法表示2.凹入法表示法圖6.1（c）的樹的凹入法表示1023.嵌套集合表示法圖6.1（c）的嵌套集合表示3.嵌套集合表示法圖6.1（c）的嵌套集合表示1034.廣義表表示法對圖6-1（c）的樹結(jié)構(gòu)，廣義表表示法可表示為：（A（B（E（J，K，L），F(xiàn)），C（G），D（H（M），I）））4.廣義表表示法對圖6-1（c）的樹結(jié)構(gòu)，廣義表表示法可表1046.1.4樹的性質(zhì)性質(zhì)1樹中的結(jié)點數(shù)等于所有結(jié)點的度加1。證明：根據(jù)樹的定義，在一棵樹中，除根結(jié)點以外，每個結(jié)點有且僅有一個直接前驅(qū)，也就是說，每個結(jié)點與指向它的一個分支一一對應(yīng)，所以，除根結(jié)點以外的結(jié)點數(shù)等于所有結(jié)點的分支數(shù)（即度數(shù)），而根結(jié)點無直接前驅(qū)，因此，樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加1。6.1.4樹的性質(zhì)性質(zhì)1樹中的結(jié)點數(shù)等于所有結(jié)點的度加105性質(zhì)2度為k的樹中第i層上最多有ki-1個結(jié)點（i≥1）。下面用數(shù)學(xué)歸納法證明：對于i=1，顯然成立，假設(shè)對于i-1層，上述條件成立，即第i-1層最多有ki-2個結(jié)點，對于第i層，結(jié)點數(shù)最多為第i-1層結(jié)點數(shù)的k倍（因為度為k），故第i層的結(jié)點數(shù)為ki-2*k=ki-1。性質(zhì)2度為k的樹中第i層上最多有ki-1個結(jié)點（i≥1）106性質(zhì)3深度為h的k叉樹最多有個結(jié)點。 證明： 由性質(zhì)2可知，若每一層的結(jié)點數(shù)最多，則整個k叉樹結(jié)點數(shù)最多，共有

當(dāng)一棵K叉樹上的結(jié)點數(shù)達(dá)到時，稱為滿K叉樹。性質(zhì)3深度為h的k叉樹最多有個結(jié)107性質(zhì)4具有n個結(jié)點的k叉樹的最小深度為。 （表示取不小于x的最小整數(shù)）證明：設(shè)具有n個結(jié)點的k叉樹的深度為h，在該樹的前面h-1層都是滿的，即每一層的結(jié)點數(shù)等于ki-1個(1≤i≤h-1)，第h層（即最后一層）的結(jié)點數(shù)可能滿，也可能不滿，這時，該樹具有最小的深度。 由性質(zhì)3知道，結(jié)點數(shù)n應(yīng)滿足下面條件：性質(zhì)4具有n個結(jié)點的k叉樹的最小深度為108通過轉(zhuǎ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=通過轉(zhuǎn)換為：kh-1<n(k-1)+1≤kh，再取以k為底的1096.2二叉樹為何要重點研究每結(jié)點最多只有兩個"叉"的樹？①二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；②可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性。6.2二叉樹為何要重點研究每結(jié)點最多只有兩個"叉"的樹1106.2.1二叉樹的定義和樹結(jié)構(gòu)定義類似，二叉樹的定義也可以遞歸形式給出：二叉樹是n（n≥0）個結(jié)點的有限集，它或者是空集（n=0），或者由一個根結(jié)點及兩棵不相交的左子樹和右子樹組成。6.2.1二叉樹的定義和樹結(jié)構(gòu)定義類似，二叉樹的定義也可以111二叉樹的特點是每個結(jié)點最多有兩個孩子，或者說，在二叉樹中，不存在度大于2的結(jié)點，并且二叉樹是有序樹（樹為無序樹），其子樹的順序不能顛倒，因此，二叉樹有五種不同的形態(tài)，參見圖6.5。圖6.5二叉樹的五種不同形態(tài)二叉樹的特點是每個結(jié)點最多有兩個孩子，或者說，在二叉樹中，不112問：具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？問：具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？113有五種有五種114二叉樹的的抽象數(shù)據(jù)類型定義見教材P121。二叉樹的的抽象數(shù)據(jù)類型定義見教材P121。115性質(zhì)1二叉樹的第i層結(jié)點數(shù)，最多為2i-1個（i≥1）。性質(zhì)2深度為k的二叉樹最大結(jié)點數(shù)為2k-1（i≥1）。性質(zhì)1二叉樹的第i層結(jié)點數(shù)，最多為2i-1個（i≥1）。116性質(zhì)3對任意一棵二叉樹，如果葉子結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則有n0=n2+1。證明：設(shè)二叉樹中度為1的結(jié)點個數(shù)為n1，根據(jù)二叉樹的定義可知，該二叉樹的結(jié)點數(shù)n=n0+n1+n2。又因為在二叉樹中，度為0的結(jié)點沒有孩子，度為1的結(jié)點有1個孩子，度為2的結(jié)點有2個結(jié)孩子，故該二叉樹的孩子結(jié)點數(shù)為n0*0+n1*1+n2*2。而一棵二叉樹中，除根結(jié)點外所有的結(jié)點都為孩子結(jié)點，故該二叉樹的結(jié)點數(shù)應(yīng)為孩子結(jié)點數(shù)加1即：n=n0*0+n1*1+n2*2+1。因此，有n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。性質(zhì)3對任意一棵二叉樹，如果葉子結(jié)點個數(shù)為n0，度為2的117為繼續(xù)給出二叉樹的其它性質(zhì)，先定義兩種特殊的二叉樹。①滿二叉樹深度為k具有2k-1個結(jié)點的二叉樹，稱為滿二叉樹。從上面滿二叉樹定義可知，必須是二叉樹的每一層上的結(jié)點數(shù)都達(dá)到最大，否則就不是滿二叉樹。②完全二叉樹對滿二叉樹的結(jié)點，從根結(jié)點起，自上而下，自左至右進(jìn)行連續(xù)編號。如果一棵具有n個結(jié)點的深度為k的二叉樹，它的每一個結(jié)點都與深度為k的滿二叉樹中編號為1~n的結(jié)點一一對應(yīng)，則稱這棵二叉樹為完全二叉樹。為繼續(xù)給出二叉樹的其它性質(zhì)，先定義兩種特殊的二叉樹。118從滿二叉樹及完全二叉樹定義可以知道，滿二叉樹一定是一棵完全二叉樹，反之完全二叉樹不一定是一棵滿二叉樹。滿二叉樹的葉子結(jié)點全部在最底層，而完全二叉樹的葉子結(jié)點可以分布在最下面兩層。深度為4的滿二叉樹和完全二叉樹如圖6.6所示。圖6.6滿二叉樹和完全二叉樹從滿二叉樹及完全二叉樹定義可以知道，滿二叉樹一定是一棵完全二119性質(zhì)4具有n個結(jié)點的完全二叉樹深度為或。性質(zhì)5如果將一棵有n個結(jié)點的完全二叉樹從上到下，從左到右對結(jié)點編號1，2，…，n，并簡稱編號為i的結(jié)點為i(1≤i≤n)，則有如下結(jié)論成立： ①若i=1，則結(jié)點i為根結(jié)點，無雙親，否則i的雙親為； ②若2i>n，則結(jié)點i無左孩子，否則i的左孩子為2i。即滿足2i>n的結(jié)點為葉子結(jié)點； ③若2i+1>n，則結(jié)點i無右孩子，否則i的右孩子為2i+1； ④若結(jié)點i為奇數(shù)且不等于1，則它的左兄弟為i-1； ⑤若結(jié)點i為偶數(shù)且不等于n，它的右兄弟為i+1； ⑥結(jié)點i所在層數(shù)(層次)為；性質(zhì)4具有n個結(jié)點的完全二叉樹深度為1206.2.3二叉樹的存貯結(jié)構(gòu)

1.順序存貯結(jié)構(gòu)按二叉樹的結(jié)點"自上而下、從左至右"編號，用一組連續(xù)的存儲單元存儲。若該二叉樹為非完全二叉樹，則必須將相應(yīng)位置空出來，使存放的結(jié)果符合完全二叉樹形狀。6.2.3二叉樹的存貯結(jié)構(gòu)

1.順序存貯結(jié)構(gòu)按二叉樹的結(jié)121圖6.7二叉樹的順序存儲對于一棵二叉樹，若采用順序存貯時，當(dāng)它為完全二叉樹時，比較方便,若為非完全二叉樹，將會浪費大量存貯存貯單元。最壞的非完全二叉樹是全部只有右分支，設(shè)高度為K，則需占用2K-1個存貯單元，而實際只有k個元素，實際只需k個存儲單元。因此，對于非完全二叉樹，宜采用下面的鏈?zhǔn)酱鎯Y(jié)構(gòu)。圖6.7二叉樹的順序存儲對于一棵二叉樹，若采用順序存貯時，1222.二叉鏈表存貯結(jié)構(gòu)

⑴二叉鏈表表示將一個結(jié)點分成三部分，一部分存放結(jié)點本身信息，另外兩部分為指針，分別存放左、右孩子的地址。注：如果需要倒查某結(jié)點的雙親，可以再增加一個雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。lchilddatarchild2.二叉鏈表存貯結(jié)構(gòu)

⑴二叉鏈表表示將一個結(jié)點分成三部分123對于圖6.7所示二叉樹，用二叉鏈表形式描述。圖6.8二叉樹的二叉鏈表表示對于圖6.7所示二叉樹，用二叉鏈表形式描述。圖6.8二叉樹124⑵二叉鏈表的數(shù)據(jù)類型

bitree.h//二叉鏈表定義#include<iostream>usingnamespacestd;typedefcharTElemType;structBiTNode{ TElemTypedata; BiTNode*lchild,*rchild;};typedefBiTNode*BiTree;⑵二叉鏈表的數(shù)據(jù)類型

bitree.h//二叉鏈表定義125voidinitBiTree(BiTree&T);voidcreateBiTree(BiTree&T);//遞歸前序遍歷voidpreOrderTraverse(BiTreeT,void(*visit)(TElemType));//非遞歸前序遍歷voidpreOrderTraverse1(BiTreeT,void(*visit)(TElemType));//遞歸中序遍歷voidinOrderTraverse(BiTreeT,void(*visit)(TElemType));//遞歸后序遍歷voidpostOrderTraverse(BiTreeT,void(*visit)(TElemType));voidinitBiTree(BiTree&T);126⑶二叉鏈表的建立為了后面遍歷二叉樹方便，先介紹建立二叉鏈表的算法（假設(shè)ElemType為char型）。⑶二叉鏈表的建立為了后面遍歷二叉樹方便，先介紹建立二叉鏈表127//按先序次序輸入二叉樹中結(jié)點的值（'#'表示空格），//構(gòu)造二叉鏈表表示的二叉樹T。voidcreateBiTree(BiTree&T){ TElemTypech; cin>>ch; if(ch=='#')//空 T=NULL; else{ T=newBiTNode; if(!T) exit(1); T->data=ch;//生成根結(jié)點 createBiTree(T->lchild);//構(gòu)造左子樹 createBiTree(T->rchild);//構(gòu)造右子樹 }}//按先序次序輸入二叉樹中結(jié)點的值（'#'表示空格），1286.3遍歷二叉樹遍歷是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎(chǔ)和核心。所謂遍歷二叉樹，就是遵從某種次序，訪問二叉樹中的所有結(jié)點，使得每個結(jié)點僅被訪問一次。這里提到的"訪問"是指對結(jié)點施行某種操作，操作可以是輸出結(jié)點信息，修改結(jié)點的數(shù)據(jù)值等，但要求這種訪問不破壞它原來的數(shù)據(jù)結(jié)構(gòu)。在本書中，我們規(guī)定訪問是輸出結(jié)點信息data，且以二叉鏈表作為二叉樹的存貯結(jié)構(gòu)。6.3遍歷二叉樹遍歷是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運129由于二叉樹是一種非線性結(jié)構(gòu)，每個結(jié)點可能有一個以上的直接后繼，因此，必須規(guī)定遍歷的規(guī)則，并按此規(guī)則遍歷二叉樹，最后得到二叉樹所有結(jié)點的一個線性序列。令L、R、D分別代表二叉樹的左子樹、右子樹、根結(jié)點，則遍歷二叉樹有6種規(guī)則：DLR、DRL、LDR、LRD、RDL、RKD。若規(guī)定二叉樹中必須先左后右(左右順序不能顛倒)，則只有DLR、LDR、LRD三種遍歷規(guī)則。DLR稱為前根遍歷(或前序遍歷、先序遍歷、先根遍歷)，LDR稱為中根遍歷(或中序遍歷)，LRD稱為后根遍歷(或后序遍歷)。由于二叉樹是一種非線性結(jié)構(gòu)，每個結(jié)點可能有一個以上的直接后繼1306.3.1前序遍歷所謂前序遍歷，就是根結(jié)點最先遍歷，其次左子樹，最后右子樹。6.3.1前序遍歷所謂前序遍歷，就是根結(jié)點最先遍歷，其次左1311.遞歸遍歷前序遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結(jié)束；否則①輸出根結(jié)點；②前根遍歷左子樹;③前根遍歷右子樹。1.遞歸遍歷前序遍歷二叉樹的遞歸遍歷算法描述為：132//先序遞歸遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次voidpreOrderTraverse(BiTreeT,void(*visit)(TElemType)){ if(T){//T不空 visit(T->data);//先訪問根結(jié)點 preOrderTraverse(T->lchild,visit);//再先序遍歷左子樹 preOrderTraverse(T->rchild,visit);//最后先序遍歷右子樹 }}//先序遞歸遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一1332.非遞歸遍歷利用一個一維數(shù)組作棧，來存貯二叉鏈表中結(jié)點，算法思想為：從二叉樹根結(jié)點開始，沿左子樹一直走到末端(左孩子為空)為止，在走的過程中，訪問所遇結(jié)點，并依次把所遇結(jié)點進(jìn)棧，當(dāng)左子樹為空時，從棧頂退出某結(jié)點，并將指針指向該結(jié)點的右孩子。如此重復(fù)，直到棧為空或指針為空止。2.非遞歸遍歷利用一個一維數(shù)組作棧，來存貯二叉鏈表中結(jié)點，134//前序遍歷二叉樹T的非遞歸算法(利用棧)，對每個數(shù)據(jù)元素調(diào)用函數(shù)VisitvoidpreOrderTraverse1(BiTreeT,void(*visit)(TElemType)){ BiTrees[100]; inttop=0;//top為棧頂指針 while((T!=NULL)||(top>0)){ while(T!=NULL){ visit(T->data); s[top++]=T; T=T->lchild; } T=s[--top]; T=T->rchild; }}//前序遍歷二叉樹T的非遞歸算法(利用棧)，對每個數(shù)據(jù)元素1356.3.2中序遍歷所謂中序遍歷，就是根在中間，先左子樹，然后根結(jié)點，最后右子樹。中序遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結(jié)束；否則①中根遍歷左子樹;②輸出根結(jié)點;③中根遍歷右子樹。6.3.2中序遍歷所謂中序遍歷，就是根在中間，先左子樹，然136//中序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次voidinOrderTraverse(BiTreeT,void(*visit)(TElemType)){ if(T){ inOrderTraverse(T->lchild,visit);//先中序遍歷左子樹 visit(T->data);//再訪問根結(jié)點 inOrderTraverse(T->rchild,visit);//最后中序遍歷右子樹 }}//中序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次1376.3.3后序遍歷所謂后序遍歷，就是根在最后，即先左子樹，然后右子樹，最后根結(jié)點。后序遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結(jié)束；否則①后根遍歷左子樹:②后根遍歷歷子樹;③訪問根結(jié)點。6.3.3后序遍歷所謂后序遍歷，就是根在最后，即先左子樹，138//后序遞歸遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次voidpostOrderTraverse(BiTreeT,void(*visit)(TElemType)){ if(T){ inOrderTraverse(T->lchild,visit);//后序遍歷左子樹 inOrderTraverse(T->rchild,visit);//再后序遍歷右子樹 visit(T->data);//最后訪問根結(jié)點 }}//后序遞歸遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次1396.3.4按層次遍歷對于一棵二叉樹，若規(guī)定遍歷順序為從上到下(上層遍歷完才進(jìn)入下層)，從左到右(同一層從左到右進(jìn)行，這樣的遍歷稱為按層次遍歷。6.3.4按層次遍歷對于一棵二叉樹，若規(guī)定遍歷順序為從上到140下面用一個一維數(shù)組來模擬隊列，實現(xiàn)二叉樹的層次遍歷。下面用一個一維數(shù)組來模擬隊列，實現(xiàn)二叉樹的層次遍歷。141//層序遍歷T(利用隊列),對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次voidlevelOrderTraverse(BiTreeT,void(*visit)(TElemType)){ BiTreeq[100],p; intf,r;//f,r類似于頭尾指針 q[0]=T; f=0; r=1; while(f<r){ p=q[f++];//出隊 visit(p->data); if(p->lchild!=NULL) q[r++]=p->lchild;//入隊 if(p->rchild!=NULL) q[r++]=p->rchild;//入隊 }}//層序遍歷T(利用隊列),對每個結(jié)點調(diào)用函數(shù)Visit一次1426.4線索二叉樹

6.4.1線索的概念通過前面介紹的二叉樹可知，遍歷二叉樹實際上就是將樹中所有結(jié)點排成一個線性序列（即非線性結(jié)構(gòu)線性化），在這樣的線性序列中，很容易求得某個結(jié)點在某種遍歷下的直接前驅(qū)和后繼。然而，有時我們希望不進(jìn)行遍歷就能快速找到某個結(jié)點在某種遍歷下的直接前驅(qū)和后繼，這樣，就應(yīng)該把每個結(jié)點的直接前驅(qū)和直接后繼記錄下來。6.4線索二叉樹

6.4.1線索的概念通過前面介紹的二叉143為了做到這一點，可以在原來的二叉鏈表結(jié)點中，再增加兩個指針域，一個指向前驅(qū)，一個指向后繼，但這樣做將會浪費大量存貯單元，存貯空間的利用率相當(dāng)?shù)?一個結(jié)點中有4個指針，1個指左孩子，1個指右孩子，1個指前驅(qū)，1個指后繼)，而原來的左、右孩子域有許多空指針又沒有利用起來（在有n個結(jié)點的二叉鏈表中必定存在n+1個空鏈域）。為了做到這一點，可以在原來的二叉鏈表結(jié)點中，再增加兩個指針域144為了不浪費存存貯空間，我們利用原有的孩子指針為空時來存放直接前驅(qū)和后繼，這樣的指針稱為"線索"，加線索的過程稱為線索化，加了線索的二叉樹，稱為線索二叉樹，對應(yīng)的二叉鏈表稱為線索二叉鏈表。為了不浪費存存貯空間，我們利用原有的孩子指針為空時來存放直接145在線索二叉樹中，由于有了線索，無需遍歷二叉樹就可以得到任一結(jié)點在某種遍歷下的直接前驅(qū)和后繼。但是，我們怎樣來區(qū)分孩子指針域中存放的是左、右孩子信息還是直接前驅(qū)或直接后繼信息呢?為此，在二叉鏈表結(jié)點中，還必須增加兩個標(biāo)志域ltag、rtag。在線索二叉樹中，由于有了線索，無需遍歷二叉樹就可以得到任一結(jié)146ltag和rtag定義如下：這樣，二叉鏈表中每個結(jié)點還是有5個域，但其中只有2個指針，較原來的4個指針要方便。增加線索后的二叉鏈表結(jié)點結(jié)構(gòu)可描述如下：lchildltagdatartagrchildltag和rtag定義如下：這樣，二叉鏈表中每個結(jié)點還是有5147前序序列為：ABCD。圖前序線索前序序列為：ABCD。圖前序線索148中序序列為：BADC。圖中序線索中序序列為：BADC。圖中序線索149后序序列為：BDCA。圖后序線索后序序列為：BDCA。圖后序線索1506.4.3線索的算法實現(xiàn)在此，僅介紹中序線索二叉樹的算法實現(xiàn)。為方便起見，依照線性表的存儲結(jié)構(gòu)，在二叉樹的線索鏈表上也添加一個頭結(jié)點，并令其lchild域的指針指向二叉樹的根結(jié)點，其rchild域的指針指向中序遍歷時訪問的最后一個結(jié)點，并令二叉樹中序序列中的第一個結(jié)點的lchild域指針和最后一個結(jié)點的rchild域的指針均指向頭結(jié)點。6.4.3線索的算法實現(xiàn)在此，僅介紹中序線索二叉樹的算法實151圖中序線索鏈表（中序序列為：BADC）圖中序線索鏈表（中序序列為：BADC）152由于線索化的實質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷時才能得到，因此線索化的過程即為在遍歷的過程中修改空指針的過程。為了記下遍歷過程中訪問結(jié)點的先后關(guān)系，需附設(shè)一個指針pre始終指向剛剛訪問過的結(jié)點。由于線索化的實質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線1531.線索鏈表類型定義

inthreading.h#include<iostream>usingnamespacestd;typedefcharTElemType;enumPointerTag{Link,Thread};//Link==0:指針，Thread==1:線索structBiThrNode{ TElemTypedata; BiThrNode*lchild,*rchild; PointerTagltag,rtag;};typedefBiThrNode*BiThrTree;1.線索鏈表類型定義

inthreading.h#incl154voidcreateBiThrTree(BiThrTree&T);voidpreOrderTraverse(BiThrTreeT,void(*visit)(TElemType));BiThrNode*inOrderThreading(BiThrTreeT);voidinTraverseThr(BiThrTreeT,void(*visit)(TElemType));voidcreateBiThrTree(BiThrTree1552.實現(xiàn)

inthreading.cpp#include"inthreading.h"http://按先序次序輸入二叉樹中結(jié)點的值（'#'表示空格），構(gòu)造二叉線索樹TvoidcreateBiThrTree(BiThrTree&T){ TElemTypech; cin>>ch; if(ch=='#')//空 T=NULL; else{ T=newBiThrNode; if(!T) exit(1); T->data=ch;//生成根結(jié)點

createBiThrTree(T->lchild);//構(gòu)造左子樹 if(T->lchild)//有左孩子 T->ltag=Link; createBiThrTree(T->rchild);//構(gòu)造右子樹 if(T->rchild)//有右孩子 T->rtag=Link; }}