第6章樹(shù)

陳守孔孟佳娜陳卓2024/12/212024/12/2第6章樹(shù)6.1樹(shù)的概念及操作6.2二叉樹(shù)

6.2.1二叉樹(shù)的概念及操作

6.2.2二叉樹(shù)的性質(zhì)6.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.3二叉樹(shù)的遍歷6.4線索二叉樹(shù)6.5樹(shù)和森林6.5.1樹(shù)的存儲(chǔ)結(jié)構(gòu)

6.5.2森林、樹(shù)、二叉樹(shù)的相互轉(zhuǎn)換

6.5.3樹(shù)和森林的遍歷6.6哈夫曼樹(shù)及其應(yīng)用

6.6.1最優(yōu)二叉樹(shù)(哈夫曼樹(shù))6.6.2哈夫曼編碼6.7算法設(shè)計(jì)舉例22024/12/2主要內(nèi)容知識(shí)點(diǎn)樹(shù)和二叉樹(shù)定義二叉樹(shù)的性質(zhì)，存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷及遍歷算法的應(yīng)用**線索二叉樹(shù)二叉樹(shù)和樹(shù)及森林的關(guān)系Huffman樹(shù)與Huffman編碼重點(diǎn)難點(diǎn)二叉樹(shù)的性質(zhì)及應(yīng)用二叉樹(shù)的遍歷算法及應(yīng)用**線索二叉樹(shù)的算法Huffman樹(shù)的構(gòu)造方法樹(shù)的算法32024/12/2樹(shù)例與特征社會(huì)的組織結(jié)構(gòu)家族的族譜計(jì)算機(jī)中的目錄組織描述層次結(jié)構(gòu)，是一種一對(duì)多的邏輯關(guān)系42024/12/2樹(shù)的定義樹(shù)(Tree)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集。n=0時(shí)稱為空樹(shù)。（注：有人定義樹(shù)不能為空）有且僅有一個(gè)稱為根的結(jié)點(diǎn)（Root）；n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm,其中每個(gè)集合又是一棵樹(shù)，稱為子樹(shù)(SubTree)FGIJABCEDH52024/12/2樹(shù)的定義樹(shù)的遞歸定義的各子樹(shù)T1,T2,…,Tm的相對(duì)次序是重要的，即樹(shù)是有序的。62024/12/2樹(shù)定義T1T2T372024/12/2樹(shù)的抽象數(shù)據(jù)類型ADTTree{數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹(shù)；若D僅含有一個(gè)數(shù)據(jù)元素，則R為空集，否則R={H}，H是如下定義的二元關(guān)系： （1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)； （2）若D-{root}

,則存在D-{root}的一個(gè)劃分D1，D2,…,Dm（m>0）,對(duì)任意j

k(1

j,k

m)有Dj

Dk=

,且對(duì)任意的i(1

i

m),存在唯一數(shù)據(jù)元素xi

Di,<root,xi>

H;

（3）對(duì)應(yīng)于D-{root}的劃分，H-{<root,x1>,…<root,xm>}有唯一的一個(gè)劃分H1,H2,…,Hm(m>0),對(duì)任意j

k(1

j,k

m)有Hj

Hk=

,且對(duì)任意i(1

i

m)，Hi是Di上的二元關(guān)系，（Di，{Hi}）是一棵符合本定義的樹(shù)，稱為根root的子樹(shù)。

（轉(zhuǎn)下頁(yè)）

82024/12/2TreeInit(T);TreeChild(T,x,i);Treebuild(T,F);TreeClear(T);Traverse(T);TreeRoot(T);TreeParent(T,x);TreeRightBrother(T,x);TreeLeftBrother(T,x);TreeInsert(T,y,i,x);}ADTTree樹(shù)的抽象數(shù)據(jù)類型92024/12/2樹(shù)的其它表示方式凹入表示嵌套集合廣義表A(B(E,F),C,D(G(J),H,I))AEFBIJGHCDABEFCDGJHIFGIJABCEDH102024/12/2結(jié)點(diǎn)：一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支；結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)的數(shù)目。樹(shù)的度：樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值；葉子（終端結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)；分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn)；除根結(jié)點(diǎn)外，也稱內(nèi)部結(jié)點(diǎn)；孩子，雙親，兄弟，堂兄：結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子；該結(jié)點(diǎn)稱為孩子的雙親；同一個(gè)雙親的孩子之間互稱兄弟；其父結(jié)點(diǎn)是兄弟的結(jié)點(diǎn)互稱堂兄。樹(shù)的概念112024/12/2概念祖先：從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。子孫：以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。層次：結(jié)點(diǎn)在樹(shù)結(jié)構(gòu)中的層（一般定義根為1層）。深度：樹(shù)中結(jié)點(diǎn)的最大層次稱為樹(shù)的深度。有序樹(shù)：結(jié)點(diǎn)的子樹(shù)在樹(shù)中的位置固定，不能互換，稱有序樹(shù)。無(wú)序樹(shù)：子樹(shù)在樹(shù)中的位置可以互換。森林：m(m≥0)棵互不相交的樹(shù)的集合。122024/12/2概念示例結(jié)點(diǎn)結(jié)點(diǎn)的度(Degree)葉子（Leaf)或終端結(jié)點(diǎn)分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)樹(shù)的度層次(Level)樹(shù)的深度(Depth)孩子（child)雙親（Parent)兄弟(Sibling)祖先子孫樹(shù)的示例132024/12/2二叉樹(shù)的概念二叉樹(shù)(BinaryTree)：或者是一棵空樹(shù)，或者是一棵由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左子樹(shù)和右子樹(shù)所組成的非空樹(shù)，左子樹(shù)和右子樹(shù)又同樣都是二叉樹(shù)

特征：每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)子樹(shù)有左右之分，其次序不能任意顛倒，只有一棵子樹(shù)時(shí)也必須分清左右子樹(shù)。142024/12/2二叉樹(shù)的抽象數(shù)據(jù)類型ADTBinTree{

數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D=

，則R=

，稱二叉樹(shù)為空二叉樹(shù)；若D

，則R={H}，H是如下二元關(guān)系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；（2）若D-{root}

,則存在D-{root}={D1,Dr},且

D1

Dr

；（3）若D1

，則D1中存在唯一的元素x1,<root,x1>

H,且存在D1上的關(guān)系H1

H；若Dr

,則Dr中存在唯一的元素xr,<root,xr>

H,且存在Dr上的關(guān)系Hr

H；H={<root,x1>,<root,xr>,H1,Hr};

（4）（D1，{H1}）是一棵符合本定義的二叉樹(shù)，稱為根的左子樹(shù)，（Dr，{Hr}）是一棵符合本定義的二叉樹(shù)，稱為根的右子樹(shù)。基本操作如下：152024/12/2二叉樹(shù)的抽象數(shù)據(jù)類型BiTreeInit(BT);BiTreeRoot(BT);BiTreeParent(BT,x);BiTreeLeftChild(BT,x);BiTreeRightChild(BT,x);BiTreeBuild(BT,LBT,RBT);BiTreeInsertLeft(BT,y,x);BiTreeInsertRight(BT,y,x);BiTreeDeleteLeft(BT,x);BiTreeDeleteRight(BT,x);BiTreeClear(BT);BiTraverse(BT);}ADTBinTree

162024/12/2二叉樹(shù)的五種形態(tài)(a)(b)(c)(d)(e)172024/12/2二叉樹(shù)的性質(zhì)1.一個(gè)非空二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i

1）

證明：i=1,只有根結(jié)點(diǎn)，顯然成立

設(shè)i=k時(shí)成立，最多有2k-1

當(dāng)i=k+1時(shí)，最多的結(jié)點(diǎn)個(gè)數(shù)：

2k-1*2=2k-1+1=2k=2(

k+1)-1182024/12/22.深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)(k

1)

二叉樹(shù)的性質(zhì)證明：二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為：

1+2+…+2k-1=2k-1192024/12/2二叉樹(shù)的性質(zhì)3.對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。證明：設(shè)n1為T中度為1的結(jié)點(diǎn)數(shù)，則總結(jié)點(diǎn)數(shù)：

n=n0+n1+n2(1)

另：除根結(jié)點(diǎn)外，所有結(jié)點(diǎn)都有且僅有一個(gè)雙親結(jié)點(diǎn)，也就是僅有一個(gè)分支進(jìn)入，若B為分支數(shù)，則

n=B+1=n1+2*n2+1(2)

由(1)和(2)有：

n1+2*n2＋1=n0+n1+n2

故 n0=n2+1;202024/12/2滿二叉樹(shù)滿二叉樹(shù)：深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)滿二叉樹(shù)考慮到有序性，任一結(jié)點(diǎn)在樹(shù)中都有確切的位置，因此可以對(duì)滿二叉樹(shù)進(jìn)行編號(hào)。編號(hào)方式為：從上到下，從左到右。212024/12/2完全二叉樹(shù)完全二叉樹(shù)：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹(shù)。完全二叉樹(shù)222024/12/2完全二叉樹(shù)特征：葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)。任一結(jié)點(diǎn)，若其左分支下的子孫的最大層次為l，則其右分支下的最大層次為l或l-1，即若結(jié)點(diǎn)無(wú)左子女，決不應(yīng)有右子女。232024/12/2完全二叉樹(shù)的特性（1）1.具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度:k=證明：假設(shè)n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為k，則n的值應(yīng)大于深度為k-1的滿二叉樹(shù)的結(jié)點(diǎn)數(shù)2k-1-1，小于等于深度為k的滿二叉樹(shù)的結(jié)點(diǎn)數(shù)2k-1，即2k-1-1<n≤2k-1

進(jìn)一步可推導(dǎo)出

2k-1<n+1≤2k兩邊取對(duì)數(shù)后，有

k-1<log2(n+1)≤k因?yàn)閗是整數(shù)，所以有k＝

242024/12/2完全二叉樹(shù)的特性（2）2.如果將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)1、2、3、…、n,則對(duì)任一結(jié)點(diǎn)i（1

i

n）有

（a）如果i=1,此結(jié)點(diǎn)為根結(jié)點(diǎn)，無(wú)雙親；若i>1,則其雙親結(jié)點(diǎn)是

i/2

。（b）如果2i>n,則結(jié)點(diǎn)i無(wú)左孩子，i為葉子結(jié)點(diǎn),否則其左孩子是結(jié)點(diǎn)2i。（c）如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子，否則其右孩子是結(jié)點(diǎn)2i+1。252024/12/2示意圖2i2i+1i2i+22i+3i+1

i/2

j層j+1層262024/12/2示意圖2i2i+1i2i+22i+3i+1LCHILD(i)LCHILD(i+1)RCHILD(i)RCHILD(i+1)

i/2

272024/12/2完全二叉樹(shù)性質(zhì)的推論n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中：度為1的結(jié)點(diǎn)數(shù)為(n+1)%2;

度為0的結(jié)點(diǎn)數(shù)為

(n+1)/2；度為2的結(jié)點(diǎn)數(shù)為

(n+1)/2-1；編號(hào)最大的分支結(jié)點(diǎn)是

n/2；編號(hào)最小的葉子結(jié)點(diǎn)是n/2+1。n個(gè)結(jié)點(diǎn)的二叉樹(shù)：高最多為n；最低為（完全二叉樹(shù)）。282024/12/2樹(shù)的葉子與其它結(jié)點(diǎn)的關(guān)系設(shè)度為m的樹(shù)中度為0,1,2,…,m的結(jié)點(diǎn)數(shù)分別為n0,n1,n2,…,nm，結(jié)點(diǎn)總數(shù)為n，分枝數(shù)為B，則下面二式成立n=n0+n1+n2+…+nm(1)n=B+1=n1+2n2+…+mnm(2)由(1)和(2)得葉子結(jié)點(diǎn)數(shù)n0=1+

292024/12/2二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)302024/12/2二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)整個(gè)二叉樹(shù)可以按照從上到下，從左到右的順序編號(hào)；對(duì)于滿/完全二叉樹(shù)，可以從根結(jié)點(diǎn)開(kāi)始按序號(hào)存放；對(duì)于一般的二叉樹(shù)，可以參照滿二叉樹(shù)的編號(hào)方法進(jìn)行編號(hào)，位置空的結(jié)點(diǎn)為“虛結(jié)點(diǎn)”。312024/12/2順序存儲(chǔ)結(jié)構(gòu)舉例1234567891018910452673完全二叉樹(shù)322024/12/2順序存儲(chǔ)結(jié)構(gòu)舉例123457810181045273一般二叉樹(shù)332024/12/2順序存儲(chǔ)結(jié)構(gòu)舉例ABC非完全二叉樹(shù)XABC????A?B???C

342024/12/2二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表三叉鏈表（線索鏈表）lchilddatarchilddatalchildrchildlchilddatarchildparentdatalchildrchildparent352024/12/2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示例ACFEDBADBCEF∧∧∧∧∧∧∧A∧∧∧∧∧BCDEF∧∧∧∧∧∧∧二叉鏈表三叉鏈表362024/12/2二叉鏈表的類C表示

二叉樹(shù)的二叉鏈表存儲(chǔ)表示typedefstructBiNode{ElemTytedata;structBiNode*lchild,*rchild;

左右孩子指針

}BiNode,*BiTree；372024/12/2二叉樹(shù)的遍歷

二叉樹(shù)的遍歷的定義：按某種規(guī)律，訪問(wèn)二叉樹(shù)的結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅一次。訪問(wèn)的含義包括查詢、打印、計(jì)算、修改等對(duì)結(jié)點(diǎn)的操作。遍歷的過(guò)程，實(shí)際上是按某種規(guī)律，將一個(gè)非線性結(jié)構(gòu)的結(jié)點(diǎn)排成一個(gè)線性序列，使每個(gè)結(jié)點(diǎn)在這種遍歷中有唯一前驅(qū)和后繼關(guān)系。一棵二叉樹(shù)的遍歷序列（在某種遍歷方式下）是唯一的，但一般說(shuō)，二叉樹(shù)不能由某一遍歷序列唯一確定。382024/12/2二叉樹(shù)的遍歷

前序遍歷二叉樹(shù)中序遍歷二叉樹(shù)后序遍歷二叉樹(shù)訪問(wèn)根結(jié)點(diǎn)；前序遍歷左子樹(shù)；前序遍歷右子樹(shù)；

中序遍歷左子樹(shù)；訪問(wèn)根結(jié)點(diǎn)；中序遍歷右子樹(shù)；

后序遍歷左子樹(shù)；后序遍歷右子樹(shù)；

訪問(wèn)根結(jié)點(diǎn)；DLRLDR、LRD、DLRRDL、RLD、DRL若二叉樹(shù)為空，則空操作，否則：層次遍歷二叉樹(shù)392024/12/2ADBCDLRADLRDLR>B>>D>>CDLR前序遍歷序列：ABDC前序遍歷402024/12/2ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷412024/12/2ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷B422024/12/2遍歷圖例ACFEDB中序序列為：DBEACF

前序序列為：ABDECF

后序序列為：DEBFCA

432024/12/2中序遍歷二叉樹(shù)的遞歸算法voidInOrderTraverse(BiTreeT){if(T)二叉樹(shù)非空

{InOrderTraverse(T->lchild);

中序遍歷左子樹(shù)

visit(T->data);

訪問(wèn)根結(jié)點(diǎn)

InOrderTraverse(T->rchild);

中序遍歷右子樹(shù)

}if}InOrderTraverse

442024/12/2圖例CFEDBA452024/12/2遞歸遍歷舉例abcdgefABCDEF前序序列：abdefcg中序序列：dfebagc后序序列：fedbgca前序序列：abcdef中序序列：cbefda后序序列：cfedba462024/12/2二叉樹(shù)的中序非遞歸遍歷設(shè)S為一個(gè)棧，t為指向根結(jié)點(diǎn)的指針，其處理過(guò)程為：（1）當(dāng)t非空時(shí)，將t所指結(jié)點(diǎn)的地址進(jìn)棧，并將t指向該結(jié)點(diǎn)的左子樹(shù)；（2）當(dāng)t為空時(shí)，彈出棧頂元素，顯示結(jié)點(diǎn)元素，并將t指向該結(jié)點(diǎn)的右子樹(shù)；（3）重復(fù)（1）、（2）步驟，直到棧空且t也為空。

472024/12/2非遞歸中序遍歷棧S的變化－cba×t→”－”－－t→”×”×t→”a”－×at→”NULL”a出棧－×t→”NULL”×出棧－－bt→”b”－t→”NULL”b出棧t→”NULL”－出棧t→”c”ct→”NULL”c出棧t→”NULL”棧空結(jié)束482024/12/2voidInOrderTraverse1(BiTreeT){∥中序遍歷二叉樹(shù)的非遞歸算法，Visit是訪問(wèn)元素的函數(shù)

StackInit(S);∥建棧

p=T;while(p||!StackEmpty(S)){while(p){Push(S，p);∥二叉樹(shù)非空，根結(jié)點(diǎn)進(jìn)棧

p=p->lchild;∥遍歷左子樹(shù)

}∥ifif（！StackEmpty(S)）

{Pop(S，p);Visit(p->data);p=p->rchild;∥遍歷右子樹(shù)

}∥if}}

中序非遞歸遍歷算法492024/12/2voidpostorder(BiTreet)

{typedefstructnode{BiTreet;inttag;//tag0..1}stack;stacks[n+1];top=0;while(t!=null||top!=0){while(t!=null){s[++top].t=t;s[top].tag=0;t=t->lchild;}while(top!=0&&s[top].tag==1)printf(s[top--].t->data:3);if(top){s[top].tag:=1;t=s[top].t->rchild;}}

}

postorder后序非遞歸遍歷算法502024/12/2建立二叉樹(shù)BiTreeCreatBiTree(){

按前序構(gòu)造二叉鏈表表示的二叉樹(shù)TBiTreeT;scanf(&ch);if(ch==’*’)T=NULL;*表示空

else{T=(BiNode*)malloc(sizeof(BiNode));T->data=ch;生成根結(jié)點(diǎn)

T->lchild=CreatBiTree();生成左子樹(shù)

T->rchild=CreatBiTree();生成左子樹(shù)

}ifreturnT;}

CreatBiTree

512024/12/2二叉樹(shù)結(jié)構(gòu)的性質(zhì)

已知二叉樹(shù)的先序序列和中序序列，可以唯一確定一棵二叉樹(shù)。已知二叉樹(shù)的后序序列和中序序列，可以唯一確定一棵二叉樹(shù)；已知二叉樹(shù)的先序序列和后序序列，不能唯一確定一棵二叉樹(shù)；已知二叉樹(shù)的層次序列和中序序列，可以唯一確定一棵二叉樹(shù)。522024/12/2構(gòu)造二叉樹(shù)

已知二叉樹(shù)的

先序序列ABDFCEHG

中序序列DBFAHECG請(qǐng)構(gòu)造該二叉樹(shù)。

532024/12/2構(gòu)造二叉樹(shù)

已知二叉樹(shù)的

后序序列DMFBHELGCA

中序序列DBMEAHECGL請(qǐng)構(gòu)造該二叉樹(shù)。

542024/12/2構(gòu)造二叉樹(shù)試找出滿足下列條件的二叉樹(shù)1）先序序列與后序序列相同2）中序序列與后序序列相同3）先序序列與中序序列相同4）中序序列與層次遍歷序列相同

552024/12/2表達(dá)式的二叉樹(shù)表示用二叉樹(shù)可以表示表達(dá)式<exp1><optr><exp2>前序遍歷：*+++ab*c+def+gh中序遍歷：a+b+c*d+e+f*g+h后序遍歷：ab+cde+*+f+gh+*表達(dá)式:((a+b)+c*(d+e)+f)*(g+h)562024/12/2二叉樹(shù)遍歷算法的應(yīng)用(1)以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，試編寫(xiě)求二叉樹(shù)深度的算法。intBinTreeDetth(BiTreeT){if(T==NULL)return0;else{l=BinTreeDetth(T->lchild);r=BinTreeDetth(T->rchild);return((l>r?l+1:r+1);}}572024/12/2二叉樹(shù)遍歷算法的應(yīng)用(2)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，試編寫(xiě)求二叉樹(shù)中葉子數(shù)的算法。intLeafCount(BiTreeT){if(!T)return0;//空樹(shù)沒(méi)有葉子

elseif(!T->lchild&&!T->rchild)return1;//葉子結(jié)點(diǎn)

elsereturnLeafCount(T->lchild)+LeafCount(T->rchild);//左子樹(shù)葉子數(shù)加上右子樹(shù)葉子數(shù)}582024/12/2二叉樹(shù)遍歷算法的應(yīng)用(3)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，試編寫(xiě)求二叉樹(shù)中葉子數(shù)的算法。intnum=0;voidLeafCount(BiTreeT){if(T){LeafCount(T->lchild);//中序遍歷左子樹(shù)

if(!T->lchild&&!T->rchild)num++;//訪問(wèn)根結(jié)點(diǎn)

LeafCount(T->rchild);//中序遍歷右子樹(shù)

}}592024/12/2二叉樹(shù)遍歷算法的應(yīng)用(4)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)算法交換二叉樹(shù)中所有結(jié)點(diǎn)的左、右子樹(shù)。voidchange(BiTree*T){if(*T!=NULL){change(&(*T)->lchild);change(&(*T)->rchild); *t=(*T)->lchild; (*T)->lchild=(*T)->rchild; (*T)->rchild=*t; }}

602024/12/2二叉樹(shù)遍歷算法的應(yīng)用(5)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)算法拷貝二叉樹(shù)。BiTreecopy(BiTreeT){BiTreeT1;if(T==null)T1=null;else{T1=(BiTree)malloc(sizeof(BiNode));//申請(qǐng)結(jié)點(diǎn)

T1->data=T->data;T1->lchild=copy(T->lchild);T1->rchild=copy(T->rchild); }returnT1;}

612024/12/2二叉樹(shù)遍歷算法的應(yīng)用(6)由順序存儲(chǔ)的n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)建立二叉鏈表存儲(chǔ)的二叉樹(shù)。BiTreecreat(ElemTypeA[],inti){BiTreeT;if(i>n)T=null;else{T=(BiTree)malloc(sizeof(BiNode));//申請(qǐng)結(jié)點(diǎn)

T->data=A[i];T->lchild=creat(A,2*i);T->rchild=creat(A,2*i+1); }returnT;}

//初始調(diào)用：p=creat(A,1);622024/12/2二叉樹(shù)遍歷算法的應(yīng)用(7)設(shè)一棵二叉樹(shù)中各結(jié)點(diǎn)的值互不相同，其前序序列和中序序列分別存于兩個(gè)一維數(shù)組pre[1..n]和mid[1..n]中，試遍寫(xiě)算法建立該二叉樹(shù)的二叉鏈表。

voidPreInCreat(BiTreeroot,ElemTypepre[],in[],intl1,h1,l2,h2)//根據(jù)二叉樹(shù)前序序列pre和中序序列in建立二叉樹(shù)。l1,h1,l2,h2是序列第一和最后元素下標(biāo)。{root=(BiTree)malloc(sizeof(BiNode));//申請(qǐng)結(jié)點(diǎn)root->data=pre[l1];//pre[l1]是根for(i=l2;i<=h2;i++)if(in[i]==pre[l1])break;//在中序序列中，根結(jié)點(diǎn)將樹(shù)分成左右子樹(shù)if(i==l2)root->lchild=null;//無(wú)左子樹(shù)elsePreInCreat(root->lchild,pre,in,l1+1,l1+(i-l2),l2,i-1)；

//遞歸建立//左子樹(shù)if(i==h2)root->rchild=null;//無(wú)右子樹(shù)elsePreInCreat((*root)->rchild,pre,in,l1+(i-l2)+1,h1,i+1,h2)//遞歸建//立右子樹(shù)}//結(jié)束PreInCreat632024/12/2線索二叉樹(shù)

線索二叉樹(shù)的提出：

1、遍歷的實(shí)質(zhì)：非線性結(jié)構(gòu)線性化（前驅(qū)、后繼）;2、前驅(qū)和后繼是在遍歷中得到的;3、知道前驅(qū)和后繼，再遍歷時(shí)就不需要棧;4、可以在二叉鏈表結(jié)構(gòu)中增加前驅(qū)和后繼兩個(gè)指針域;5、n個(gè)結(jié)點(diǎn)的二叉樹(shù)有n＋1個(gè)空指針，可以利用。642024/12/2線索二叉樹(shù)

n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針域，可以利用這些空指針域來(lái)存放結(jié)點(diǎn)的前驅(qū)和后繼的信息,這樣的的指針?lè)Q為“線索”，加上了線索的二叉鏈表稱為線索鏈表，加上線索的二叉樹(shù)就是線索二叉樹(shù)（ThreadedBinaryTree）。將二叉樹(shù)變?yōu)榫€索二叉樹(shù)的過(guò)程稱為線索化。

lchildltagdatartagrchildltag=

rtag=

652024/12/2線索二叉樹(shù)

<？序><前驅(qū)/后繼/全>線索化只有空指針才能加線索662024/12/2前序前驅(qū)線索化前序前驅(qū)線索化ABECFGHIDABECFGHID672024/12/2中序（全）線索二叉樹(shù)NULLACFEDBNULLA00E11C01D11F11B00NULLA

為方便起見(jiàn)，在線索鏈表中增加一個(gè)頭結(jié)點(diǎn)，令其lchild域指向二叉樹(shù)的根結(jié)點(diǎn)，rchild域指向訪問(wèn)序列的最后一個(gè)結(jié)點(diǎn)，這樣，就建立了一個(gè)雙向線索鏈表。68

皮肌炎是一種引起皮膚、肌肉、心、肺、腎等多臟器嚴(yán)重?fù)p害的，全身性疾病，而且不少患者同時(shí)伴有惡性腫瘤。它的1癥狀表現(xiàn)如下：1、早期皮肌炎患者，還往往伴有全身不適癥狀，如-全身肌肉酸痛，軟弱無(wú)力，上樓梯時(shí)感覺(jué)兩腿費(fèi)力；舉手梳理頭發(fā)時(shí)，舉高手臂很吃力；抬頭轉(zhuǎn)頭緩慢而費(fèi)力。皮肌炎圖片——皮肌炎的癥狀表現(xiàn)2024/12/2后序（全）線索化702024/12/2類型定義typedefstructBiThrNode{ElemTytedata;structBiThrNode*lchild,*rchild;

左、右孩子指針

intltag,rtag;}BiThrNode，*BiThrTree712024/12/2前序線索化BiThrTreepre=null;//設(shè)置前驅(qū)voidPreOrderThreat(BiThrTreeT){if(T!=null){if(T->lchild==null){T->ltag=1;T->lchild=pre;}//設(shè)置左線索

if(T->rchild==null)T->rtag=1;//為建立右鏈作準(zhǔn)備

if(pre!=null&&pre->rtag==1)pre->rchild=T;//設(shè)置前驅(qū)的右線索；

pre=T;//前驅(qū)后移

if(T->ltag==0)PreOrderThreat(T->lchild);//左子樹(shù)前序線索化

PreOrderThreat(BT->rchild);//右子樹(shù)前序線索化

}}722024/12/2中序線索化二叉樹(shù)BiThrTreepre=null;//設(shè)置前驅(qū)voidInOrderThreat(BiThrTreeT){if(T)

{InOrderThreat(T->lchild);//左子樹(shù)中序線索化

if(T->lchild==null){T->ltag=1;T->lchild=pre;}//左線索為pre;if(T->rchild==null)T->rtag=1;//置右標(biāo)記，為右線索作準(zhǔn)備

if(pre!=null&&pre->rtag==1)pre->rchild=T;}//給前驅(qū)加后繼線索

pre=T;//前驅(qū)指針后移

InOrderThreat(T->rchild);//右子樹(shù)中序線索化

}

}//結(jié)束InOrderThreat

732024/12/2后序線索化二叉樹(shù)BiThrTreepre=null;//設(shè)置前驅(qū)voidPostOrderThreat(BiThrTreeT){if(T)

{PostOrderThreat(T->lchild);//左子樹(shù)后序線索化

PostOrderThreat(T->rchild);//右子樹(shù)后序線索化

if(T->lchild==null){T->ltag=1;T->lchild=pre;}//左線索為pre;if(T->rchild==null)T->rtag=1;//置右標(biāo)記，為右線索作準(zhǔn)備

if(pre!=null&&pre->rtag==1)pre->rchild=T;}//給前驅(qū)加后繼線索

pre=T;//前驅(qū)指針后移

}

}//結(jié)束PostOrderThreat

742024/12/2線索二叉樹(shù)的中序遍歷voidInorderTraverseThr(BiThrTreep){while(p)

二叉樹(shù)非空

{while(p->tag==0)

找中序序列的開(kāi)始結(jié)點(diǎn)

p=p->lchild;

printf(p->data); while(p&&p->rtag==1){p=p->rchild;printf(p->data);}//找P的中序后繼結(jié)點(diǎn)

if(p)p=p->rchild;}//while}

InorderTraverseThr752024/12/2帶頭結(jié)點(diǎn)的線索二叉樹(shù)的中序遍歷voidInorderTraverseThr(BiThrTreethrt){p=thrt->lchild;while(p!=thrt)

二叉樹(shù)非空

{while(p->ltag==0)

找中序序列的開(kāi)始結(jié)點(diǎn)

p=p->lchild;printf(p->data); while(p->rtag==1&&p->rchild!=thrt){p=p->rchild;printf(p->data);}//找P的中序后繼結(jié)點(diǎn)

p=p->rchild;}//while(p!=thrt)}

InorderTraverseThr762024/12/2前序線索樹(shù)上找前驅(qū)和后繼找前驅(qū)：困難找后繼：

若結(jié)點(diǎn)有左子女，則左子女是后繼；否則，rchild指向后繼。772024/12/2前序線索樹(shù)上找后繼BiThrTreePreorderNext(BiThrTreep){if(p->ltag==0)

結(jié)點(diǎn)有左子女

return(p->lchild);

結(jié)點(diǎn)的左子女為其前序后繼

else

return(p->rchild);}

PreorderNext782024/12/2中序線索樹(shù)上找前驅(qū)和后繼

中序的前驅(qū)和后繼都往上指向祖先找前驅(qū)：若左標(biāo)記為1，則lchild指向其前驅(qū)；否則，其前驅(qū)是其左子樹(shù)上按中序遍歷的最后一個(gè)結(jié)點(diǎn)。找后繼：若右標(biāo)記為1，則rchild指向其后繼；否則，其后繼是其右子樹(shù)上按中序遍歷的第一個(gè)結(jié)點(diǎn)。792024/12/2中序線索樹(shù)上找前驅(qū)BiThrTreeInorderPre(BiThrTreep){BiThrTreeq;if(p->ltag==1)

結(jié)點(diǎn)的左子樹(shù)為空

q=p->lchild

結(jié)點(diǎn)的左指針域?yàn)樽缶€索，指向其前驅(qū)

else{q=p->lchild;

p結(jié)點(diǎn)的中序前驅(qū)是左子樹(shù)中最右邊結(jié)點(diǎn)

while(q->rtag==0)q=q->rchild;

}

ifreturn(q);}

InorderPre802024/12/2中序線索樹(shù)上找后繼BiThrTreeInorderNext(BiThrTreep){BiThrTreeq;if(p->rtag==1)

結(jié)點(diǎn)的右子樹(shù)為空

q=p->rchild

結(jié)點(diǎn)的右指針域?yàn)橛揖€索，指向其后繼

else{q=p->rchild;

P結(jié)點(diǎn)的中序后繼是其右子樹(shù)中最左邊結(jié)點(diǎn)

while(q->ltag==0)q=q->lchild;

}

ifreturn(q);}

InorderNext812024/12/2后序線索樹(shù)上找前驅(qū)和后繼找前驅(qū)：若結(jié)點(diǎn)有右子女，則右子女是其前驅(qū)；否則，lchild指向其前驅(qū)。找后繼：困難，需要知道其雙親。822024/12/2后序線索樹(shù)上找前驅(qū)BiThrTreePostorderPre(BiThrTreep){if(p->rtag==0)

結(jié)點(diǎn)有右子女

return(p->rchild);

結(jié)點(diǎn)的右子女為其后序前驅(qū)

else

return(p->lchild);}

PreorderPre832024/12/2線索樹(shù)上結(jié)點(diǎn)的插入與刪除除修改結(jié)點(diǎn)指針外，還需要修改線索。842024/12/2樹(shù)的存儲(chǔ)結(jié)構(gòu)考慮存儲(chǔ)結(jié)構(gòu)時(shí)，主要考慮邏輯結(jié)構(gòu)：數(shù)據(jù)元素?cái)?shù)據(jù)元素之間的關(guān)系樹(shù)的存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)852024/12/2樹(shù)的存儲(chǔ)結(jié)構(gòu)ABECDF雙親表示法

孩子表示法

孩子兄弟表示法

862024/12/2雙親表示法使用靜態(tài)數(shù)組（本質(zhì)是靜態(tài)鏈表）；數(shù)組的每個(gè)數(shù)據(jù)元素，包括兩個(gè)域：一個(gè)域是數(shù)據(jù)元素；另一個(gè)域用游標(biāo)指示該結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的相對(duì)位置；根結(jié)點(diǎn)的游標(biāo)為-1。特點(diǎn)：方便找結(jié)點(diǎn)的雙親；順序存儲(chǔ)結(jié)構(gòu)；872024/12/2雙親表示法類型定義#defineMAX_NODE64typedefstructPtnode{ElemTytedata;

數(shù)據(jù)域

intparent;

雙親指示域

}Ptnode；typedefstruct

{Ptnodenodes[MAX_NODE];intn;}Ptree;

882024/12/2雙親表示示例ACGEDBHF

數(shù)組下標(biāo)

01234567dataABCDEFGHparent-10011222892024/12/2雙親表示法表示的樹(shù)的深度intDepth(Ptreet){intmaxdepth=0;for(i=1;i<=t.n;i++){temp=0;f=i;while(f>0)//求結(jié)點(diǎn)i的深度

{temp++;f=t.nodes[f].parent;}

if(temp>maxdepth)//最大深度更新

maxdepth=temp;}return(maxdepth);//返回樹(shù)的深度}//結(jié)束Depth902024/12/2孩子表示法任一數(shù)據(jù)元素，有0個(gè)或多個(gè)孩子；因此可以設(shè)計(jì)一個(gè)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其結(jié)點(diǎn)除放置數(shù)據(jù)元素外，還放置若干指針，分別用來(lái)指示該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)在存儲(chǔ)空間中的位置。912024/12/2孩子表示法方法1根據(jù)結(jié)點(diǎn)的度，設(shè)置結(jié)點(diǎn)的指針個(gè)數(shù)，比如若結(jié)點(diǎn)的度為d:datachild1child2…childd問(wèn)題：不同的數(shù)據(jù)元素，結(jié)點(diǎn)構(gòu)造不同；操作不方便922024/12/2孩子表示法方法2按照樹(shù)的度定義結(jié)點(diǎn)。若樹(shù)的度為d,定義degree，表示該結(jié)點(diǎn)的度datachild1child2…childddegree問(wèn)題：因degree為樹(shù)的度，是所有結(jié)點(diǎn)的最大的度，因此樹(shù)中有相當(dāng)部分的指針域?yàn)榭眨速M(fèi)空間。有n個(gè)結(jié)點(diǎn)的樹(shù)的度為k，空指針域有

n(k-1)+1個(gè)。932024/12/2孩子表示法有n個(gè)結(jié)點(diǎn)的樹(shù)的度為k，空指針域有n(k-1)+1個(gè)。證明：n個(gè)結(jié)點(diǎn)的樹(shù)，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有一個(gè)指針指向，也就是樹(shù)中有n-1個(gè)有效鏈域（指針）而按該結(jié)點(diǎn)定義，n個(gè)結(jié)點(diǎn)總的指針域有：nk個(gè)。因此空鏈域：

nk–(n-1)=n(k-1)+1942024/12/2一個(gè)靜態(tài)數(shù)組，存放所有的結(jié)點(diǎn)數(shù)組的每個(gè)數(shù)據(jù)元素，包括兩部分：數(shù)據(jù)元素，指針；指針指向一個(gè)鏈表，鏈表結(jié)點(diǎn)的數(shù)據(jù)域是一個(gè)整數(shù)，表示該結(jié)點(diǎn)的孩子在數(shù)組中的相對(duì)位置；特點(diǎn)：順序+鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；找孩子容易，找雙親難；孩子表示法952024/12/2孩子表示法ACGEDBHF01234567∧∧∧∧657∧ABCDEFG312∧4∧∧H962024/12/2雙親孩子鏈表在靜態(tài)數(shù)組的結(jié)點(diǎn)中增加一個(gè)域，表示該結(jié)點(diǎn)的雙親在該樹(shù)組中的相對(duì)位置。有利于尋找孩子結(jié)點(diǎn)和雙親結(jié)點(diǎn)。ACGEDBHF01234567657∧312∧∧G∧∧∧ABCDEF-1001122parent4∧H2∧972024/12/2孩子表示法類型定義#defineMAX_NODE64typedefstructCtnode孩子結(jié)點(diǎn){intchild;structCtnode*next;}*childlink; typedefstruct頭結(jié)點(diǎn){ElemTypedata;childlinkfirstchild;}CTBox;CTBoxnodes[MAX_NODE]；982024/12/2孩子兄弟表示法從向下的縱向和向右的橫向描述樹(shù)；定義結(jié)點(diǎn)，除存放數(shù)據(jù)元素外，存放兩個(gè)指針，一個(gè)指向該結(jié)點(diǎn)的第一個(gè)孩子，另一個(gè)指向該結(jié)點(diǎn)的下一個(gè)兄弟；992024/12/2孩子兄弟表示法typedefstructCSNode{ElemTytedata;

structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;

該表示方法又稱二叉樹(shù)表示法，本質(zhì)上與二叉鏈表表示法一致。datafirstchildnextsibling1002024/12/2孩子兄弟表示法A∧BC∧D∧E∧F∧G∧∧H∧∧ACGEDBHF1012024/12/2孩子-兄弟表示法算法示例intLeaves(Treet)//計(jì)算以孩子-兄弟表示法存儲(chǔ)的森林的葉子數(shù){if(t==null)return0;else{if(t->firstchild==null)//無(wú)孩子的結(jié)點(diǎn)必是葉子

return(1+Leaves(t->nextsibling));

//返回葉子結(jié)點(diǎn)和其兄弟子樹(shù)中的葉子結(jié)點(diǎn)數(shù)

elsereturn(Leaves(t->firstchild)+Leaves(t->nextsibling));//孩子子樹(shù)和兄弟子樹(shù)中葉子數(shù)之和

}}//結(jié)束Leaves1022024/12/2孩子-兄弟表示法算法示例intHeight(CSTreebt)//遞歸求以孩子兄弟鏈表表示的樹(shù)的深度{inthc,hs;if(bt==null)return(0);elseif(!bt->firstchild)returnmax(1,height(bt->nextsibling））；

//子女空，取1和兄弟的深度的大者

else{hc=height(bt->firstchild)；//第一子女樹(shù)高

hs=height(bt->nextsibling)；//兄弟樹(shù)高

if(hc+1>hs)return(hc+1);elsereturn(hs);//高度取子女高度+1和兄弟子樹(shù)高度的大者

}}//結(jié)束height1032024/12/2若樹(shù)采用孩子兄弟表示法，二叉樹(shù)采用二叉鏈表表示，則從存儲(chǔ)結(jié)構(gòu)上看，結(jié)點(diǎn)定義完全相同。因此，在使用該存儲(chǔ)結(jié)構(gòu)下，樹(shù)和二叉樹(shù)是等價(jià)的，樹(shù)可以轉(zhuǎn)化為二叉樹(shù)。樹(shù)和二叉樹(shù)的轉(zhuǎn)化步驟（1）連線：在兄弟結(jié)點(diǎn)之間加一條連線。（2）切線：對(duì)于每個(gè)結(jié)點(diǎn)，除了保留與其最左孩子的連線外，切掉該結(jié)點(diǎn)與其它孩子的連線。（3）旋轉(zhuǎn)：將按（1）、（2）的方法形成的二叉樹(shù)，沿順時(shí)針?lè)较蛐D(zhuǎn)450,就可以得到一棵形式上更為清楚的二叉樹(shù)。

1042024/12/2樹(shù)和二叉樹(shù)轉(zhuǎn)化例FGHABCEDFGHABCEDFGHABCEDFHABGCED1052024/12/2將樹(shù)轉(zhuǎn)換成二叉樹(shù)樹(shù)轉(zhuǎn)換成的二叉樹(shù)其右子樹(shù)一定為空ABCDEFGHIJKLABCDEFGHIJKL1062024/12/2森林到二叉樹(shù)的轉(zhuǎn)換若樹(shù)采用孩子兄弟表示法，二叉樹(shù)采用二叉鏈表表示，則：任一棵樹(shù)，都可以找到唯一的一棵二叉樹(shù)和它對(duì)應(yīng)，而且該二叉樹(shù)沒(méi)有右子樹(shù)。(因此一棵二叉樹(shù)，不一定保證能轉(zhuǎn)換為一棵(>=1)樹(shù))若把森林中的第二棵樹(shù)的根結(jié)點(diǎn)，看成是第一棵樹(shù)的根結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，則這兩棵樹(shù)可以轉(zhuǎn)換為一棵二叉樹(shù)（該二叉樹(shù)的根結(jié)點(diǎn)的右子女沒(méi)有右子樹(shù)）。依次類推，可以認(rèn)為森林和二叉樹(shù)是一一對(duì)應(yīng)的，從而得到二叉樹(shù)和森林的轉(zhuǎn)換規(guī)則1072024/12/2森林到二叉樹(shù)的轉(zhuǎn)換步驟：（1）連線：在兄弟（各樹(shù)的根結(jié)點(diǎn)看作兄弟）結(jié)點(diǎn)之間加一條連線。（2）切線：對(duì)于每個(gè)結(jié)點(diǎn)，除了保留與其最左孩子的連線外，切掉該結(jié)點(diǎn)與其它孩子的連線。（3）旋轉(zhuǎn)：將按（1）、（2）的方法形成的二叉樹(shù)，沿順時(shí)針?lè)较蛐D(zhuǎn)450,就可以得到一棵形式上更為清楚的二叉樹(shù)。1082024/12/2AGJBCDHIKEFLMN將森林轉(zhuǎn)換成二叉樹(shù)ABGCEHFJKILMND1092024/12/2二叉樹(shù)到森林的轉(zhuǎn)換

如果B={root,LBT,RBT}是一棵二叉樹(shù)，F(xiàn)={T1,T2,…,Tn}表示與其對(duì)應(yīng)的森林，轉(zhuǎn)換規(guī)則如下：（1）若B為空，則F為空；（2）若B非空，則F中第一棵樹(shù)T1的根即為二叉樹(shù)B的根root，T1中根結(jié)點(diǎn)的子樹(shù)森林F1是由B的左子樹(shù)LBT轉(zhuǎn)換而成的森林；F中除T1之外其余樹(shù)組成的森林F’={T2,T3…,Tn}是由B的右子樹(shù)RBT轉(zhuǎn)化而成的森林。1102024/12/2二叉樹(shù)到森林的轉(zhuǎn)換例1IABDFGHKCEJIABDJHCEFGK1112024/12/2DEFGHIJLABCKFILCABEGHJKD二叉樹(shù)到森林的轉(zhuǎn)換例21122024/12/2樹(shù)和森林的遍歷

樹(shù)的遍歷：（1）前序遍歷（2）后序遍歷森林的遍歷：（1）前序遍歷（2）中序遍歷1132024/12/2樹(shù)的遍歷前序遍歷樹(shù)的規(guī)則為：若樹(shù)非空，則：（1）訪問(wèn)樹(shù)的根結(jié)點(diǎn)；（2）依次前序遍歷樹(shù)的第一棵子樹(shù)、第二棵子樹(shù)，……后序遍歷樹(shù)的規(guī)則為：若樹(shù)非空，則：（1）依次后序遍歷樹(shù)的第一棵子樹(shù)、第二棵子樹(shù)，……（2）訪問(wèn)樹(shù)的根結(jié)點(diǎn)；

ABCED前序遍歷序列：ABCDE后序遍歷序列：BCEDA1142024/12/2樹(shù)的遍歷與二叉樹(shù)遍歷對(duì)應(yīng)

樹(shù)的前序遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的前序遍歷序列相同；

樹(shù)的后序遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的中序遍歷序列相同；1152024/12/2森林的遍歷前序遍歷森林的規(guī)則為：若森林為空，返回；否則：（1）訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；（2）前序遍歷第一棵樹(shù)的子樹(shù)森林；（3）前序遍歷其它樹(shù)組成的森林；

中序遍歷森林的規(guī)則為：若森林為空，返回；否則：（1）中序遍歷第一棵樹(shù)的子樹(shù)森林；（2）訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)；（3）中序遍歷除第一棵樹(shù)外其它樹(shù)組成的森林；

ABCFGHJIED右圖森林的前序遍歷序列為：

ABCDEFGHIJ右圖森林的后序遍歷序列為：BDCAFEHIJG1162024/12/2森林的遍歷與二叉樹(shù)的遍歷對(duì)應(yīng)

森林的先序遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先序遍歷序列相同；

森林的中序遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的中序遍歷序列相同；1172024/12/2哈夫曼樹(shù)的概念路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成兩個(gè)結(jié)點(diǎn)之間的路徑。路徑長(zhǎng)度：路徑上的分支數(shù)目稱為路徑長(zhǎng)度。樹(shù)的路徑長(zhǎng)度：樹(shù)的根結(jié)點(diǎn)到樹(shù)中每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度的和。1182024/12/2結(jié)點(diǎn)的帶權(quán)的路徑長(zhǎng)度：該結(jié)點(diǎn)到根結(jié)點(diǎn)之間的路程長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積樹(shù)的帶權(quán)的路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)的路徑長(zhǎng)度的和。通常記為：WPL(WeightedPathLength)。由n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)構(gòu)成的二叉樹(shù)中，WPL最小的二叉樹(shù)稱為最優(yōu)二叉樹(shù)，或哈夫曼（Huffman）樹(shù)。哈夫曼樹(shù)的概念（續(xù)）1192024/12/2

有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)abcd7524WPL=7*2+5*2+2*2+4*2=36WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35dcab24751202024/12/2哈夫曼樹(shù)的性質(zhì)1、哈夫曼樹(shù)只有度為0和2的結(jié)點(diǎn)，無(wú)度為1的結(jié)點(diǎn)；2、權(quán)值大的結(jié)點(diǎn)離根結(jié)點(diǎn)近；3、n個(gè)葉子的哈夫曼樹(shù)的形態(tài)一般不唯一，但WPL是相同的；4、n個(gè)葉子的哈夫曼樹(shù)共有2n-1個(gè)結(jié)點(diǎn)。1212024/12/2根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹(shù)，令其權(quán)值為wj;在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)，置新二叉樹(shù)根結(jié)點(diǎn)權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和;在森林中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入森林中;重復(fù)上述兩步，直到只含一棵樹(shù)為止，這棵樹(shù)即哈夫曼樹(shù)。構(gòu)造Huffman樹(shù)步驟1222024/12/2dcba9653ba96358a9614358962314538abcdcbd哈夫曼樹(shù)的構(gòu)造舉例1232024/12/2例w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100哈夫曼樹(shù)的形態(tài)是不唯一的1242024/12/2已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8，11，試構(gòu)造哈夫曼樹(shù)。舉例1252024/12/2哈夫曼樹(shù)的類型定義typedefstruct{intweight;intparent,lchild,rchild;}HufmTree;1262024/12/2哈夫曼樹(shù)的構(gòu)造算法viodCreatHuffman(HufmTreetree[]，intn){

構(gòu)造哈夫曼樹(shù)，n為初始森林中的結(jié)點(diǎn)數(shù)

inti,j,t1,t2；

if(n<=1)retu