工程09級(jí)使用數(shù)據(jù)結(jié)構(gòu)第6章

返回主目錄

本章說(shuō)明6.1樹(shù)的基本定義6.2二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)6.4樹(shù)和森林6.6赫夫曼樹(shù)及其應(yīng)用

本章小結(jié)

學(xué)習(xí)目標(biāo)領(lǐng)會(huì)樹(shù)和二叉樹(shù)的類型定義，理解樹(shù)和二叉樹(shù)的結(jié)構(gòu)差別熟記二叉樹(shù)的主要特性，并掌握它們的證明方法熟練掌握二叉樹(shù)的各種遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其它操作理解二叉樹(shù)的線索化過(guò)程以及在中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法熟練掌握二叉樹(shù)和樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法了解最優(yōu)樹(shù)的特性，掌握建立最優(yōu)樹(shù)和赫夫曼編碼的方法。本章說(shuō)明本章說(shuō)明

重點(diǎn)和難點(diǎn)二叉樹(shù)和樹(shù)的遍歷及其應(yīng)用是本章的學(xué)習(xí)重點(diǎn)，而編寫(xiě)實(shí)現(xiàn)二叉樹(shù)和樹(shù)的各種操作的遞歸算法也恰是本章的難點(diǎn)所在。知識(shí)點(diǎn)樹(shù)的類型定義、二叉樹(shù)的類型定義、二叉樹(shù)的存儲(chǔ)表示、二叉樹(shù)的遍歷以及其它操作的實(shí)現(xiàn)、線索二叉樹(shù)、樹(shù)和森林的存儲(chǔ)表示、樹(shù)和森林的遍歷以及其它操作的實(shí)現(xiàn)、最優(yōu)樹(shù)和赫夫曼編碼學(xué)習(xí)指南本章是整個(gè)課程的第二個(gè)學(xué)習(xí)重點(diǎn)，也是整個(gè)課程中的一大難點(diǎn)。在本章的學(xué)習(xí)過(guò)程中主要應(yīng)該學(xué)會(huì)如何根據(jù)二叉樹(shù)和樹(shù)的結(jié)構(gòu)及其操作的遞歸定義編寫(xiě)遞歸算法。6.1樹(shù)的定義和基本術(shù)語(yǔ)

樹(shù)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)1、樹(shù)的定義定義：樹(shù)(tree)是n(n>0)個(gè)結(jié)點(diǎn)的有限集T，其中：有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹(shù)的根(root)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,……Tm，其中每一個(gè)集合本身又是一棵樹(shù)，稱為根的子樹(shù)(subtree)特點(diǎn)：樹(shù)中至少有一個(gè)結(jié)點(diǎn)——根樹(shù)中各子樹(shù)是互不相交的集合6.1樹(shù)的定義和基本術(shù)語(yǔ)A只有根結(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM有子樹(shù)的樹(shù)根子樹(shù)ADTTree

數(shù)據(jù)對(duì)象D：數(shù)據(jù)關(guān)系R：基本操作P：InitTree(&T);DestroyTree(&T);CreateTree(&T,definition);ClearTree(&T);……2、樹(shù)的抽象數(shù)據(jù)類型的定義P1186.1樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)形表示法：自然界倒長(zhǎng)的樹(shù)(Knuth開(kāi)初用正長(zhǎng)的樹(shù)表示)文氏表示法：用嵌套集合表示(a)嵌套括號(hào)表示法：廣義表表示法凹入表示法：類似書(shū)目3、樹(shù)的表示方法6.1樹(shù)的定義和基本術(shù)語(yǔ)KLEADJIMHGCBF(a)ACDBEKLFGHMIJ(c)(b)(A(B(E(K,L),F),C(G),D(H(M),I,J)))4、樹(shù)的術(shù)語(yǔ)6.1樹(shù)的定義和基本術(shù)語(yǔ)結(jié)點(diǎn)(node)——表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支結(jié)點(diǎn)的度(degree)——結(jié)點(diǎn)擁有的子樹(shù)數(shù)葉子(leaf)——度為0的結(jié)點(diǎn)孩子(child)——結(jié)點(diǎn)子樹(shù)的根稱為該結(jié)點(diǎn)的孩子雙親(parents)——孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的~兄弟(sibling)——同一雙親的孩子樹(shù)的度——一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù)結(jié)點(diǎn)的層次(level)——從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……堂兄——其父母為兄弟的結(jié)點(diǎn)互稱堂兄祖先——結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)子孫——以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫有序樹(shù)——結(jié)點(diǎn)的子樹(shù)從左到右有順序，否則，稱為無(wú)序樹(shù)深度(depth)——樹(shù)中結(jié)點(diǎn)的最大層次數(shù)森林(forest)——m(m

0)棵互不相交的樹(shù)的集合6.1樹(shù)的定義和基本術(shù)語(yǔ)6.1樹(shù)的定義和基本術(shù)語(yǔ)ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹(shù)的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹(shù)的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先6.2二叉樹(shù)1、二叉樹(shù)定義定義：二叉樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)(n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)構(gòu)成特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)(即不存在度大于2的結(jié)點(diǎn))二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能任意顛倒基本形態(tài)A只有根結(jié)點(diǎn)的二叉樹(shù)

空二叉樹(shù)AB右子樹(shù)為空AB左子樹(shù)為空ABC左、右子樹(shù)均非空證明：用歸納法證明之

i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，顯然，2i-1=20=1

是對(duì)的假設(shè)對(duì)所有j,(1j<i)命題成立，即第j層上

至多有2j-1個(gè)結(jié)點(diǎn)，可證明j=i命題成立

③那么，第i-1層至多有2i-2個(gè)結(jié)點(diǎn)

又二叉樹(shù)每個(gè)結(jié)點(diǎn)的度至多為2

第i層上最大結(jié)點(diǎn)數(shù)是第i-1層的2倍，即

2×2i-2=2i-1

故命題得證2、二叉樹(shù)的性質(zhì)6.2二叉樹(shù)性質(zhì)1：性質(zhì)2：深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)(k1)6.2二叉樹(shù)證明：由性質(zhì)1，可得深度為k的二叉樹(shù)最大結(jié)點(diǎn)數(shù)是性質(zhì)3：對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1證明：設(shè)n1為二叉樹(shù)T中度為1的結(jié)點(diǎn)數(shù)

因?yàn)椋憾鏄?shù)中所有結(jié)點(diǎn)的度均小于或等于2

所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2

又二叉樹(shù)中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一

個(gè)分支進(jìn)入，設(shè)B為分支總數(shù)，則n=B+1

又：分支由度為1和度為2的結(jié)點(diǎn)射出，

B=n1+2n2

于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(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í)，稱為~特點(diǎn)葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l或l+16.2二叉樹(shù)幾種特殊形式的二叉樹(shù)滿二叉樹(shù)定義：6.2二叉樹(shù)1231145891213671014151231145891267101234567123456思考：滿二叉樹(shù)與完全二叉樹(shù)的關(guān)系？性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為

log2n+1

證明：設(shè)深度為k，則由性質(zhì)2和完全二叉樹(shù)定義

(k-1層)2k-1-1<n≤2k-1(k層）或2k-1≤n<2k

于是k-1≤log2n<k

又k是整數(shù)

k=log2n+1性質(zhì)5：對(duì)于一棵完全二叉樹(shù)，從上到下從左至右對(duì)結(jié)點(diǎn)進(jìn)行編號(hào),根結(jié)點(diǎn)為1,則對(duì)任一結(jié)點(diǎn)i(1<=i<=n)，有：若i=1,則結(jié)點(diǎn)是二叉樹(shù)的根，無(wú)雙親，否則其雙親是

i/2如果2i>n，則結(jié)點(diǎn)i無(wú)左子女，否則，其左子女為2i如果2i+1>n，則結(jié)點(diǎn)i無(wú)右子女，否則，其右子女為2i+16.2二叉樹(shù)3、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：按滿二叉樹(shù)的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹(shù)中的數(shù)據(jù)元素特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中浪費(fèi)空間，適于存滿二叉樹(shù)和完全二叉樹(shù)abcdefgabcde0000fg12345678910116.2二叉樹(shù)浪費(fèi)空間二叉樹(shù)的順序存儲(chǔ)表示

#defineMAX_TREE_SIZE100TypedefTElemTypeSqBiTree[MAX_TREE_SIZE];//

0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)

SqBiTreebt;缺點(diǎn)：按完全二叉樹(shù)形式存儲(chǔ)，浪費(fèi)空間。例如，在最壞情況下，n個(gè)結(jié)點(diǎn)的單枝樹(shù)，要占用2n-1個(gè)元素的存儲(chǔ)空間。6.2二叉樹(shù)順序存儲(chǔ)結(jié)構(gòu)適用于滿二叉樹(shù)和完全二叉樹(shù)的存儲(chǔ)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表表示typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;lchilddatarchildABCDEFG在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域ABCDEFG^^^^^^^^6.2二叉樹(shù)三叉鏈表表示typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild,*parent;}BiTNode,*Bitree;lchilddataparentrchildABCDEFGABCDEFG^^^^^^^^^6.2二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)

問(wèn)題的提出

先左后右的遍歷算法

算法的遞歸描述

遍歷算法的應(yīng)用舉例1、遍歷二叉樹(shù)

算法的非遞歸描述

順著某一條搜索路徑巡訪二叉樹(shù)中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。

問(wèn)題的提出“訪問(wèn)”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。6.3遍歷二叉樹(shù)和線索二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)

“遍歷”是任何類型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹(shù)是非線性結(jié)構(gòu)，

每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑進(jìn)行遍歷的問(wèn)題。6.3遍歷二叉樹(shù)和線索二叉樹(shù)

對(duì)“二叉樹(shù)”而言，可以有三條搜索路徑：（1）先上后下的按層次遍歷；（2）先左（子樹(shù)）后右（子樹(shù)）的遍歷；（3）先右（子樹(shù)）后左（子樹(shù)）的遍歷。6.3遍歷二叉樹(shù)和線索二叉樹(shù)

先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法根左子樹(shù)右子樹(shù)根根根根根訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹(shù)、遍歷右子樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)

若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）訪問(wèn)根結(jié)點(diǎn)；（2）先序遍歷左子樹(shù)；（3）先序遍歷右子樹(shù)。先（根）序的遍歷算法：6.3遍歷二叉樹(shù)和線索二叉樹(shù)

若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）中序遍歷左子樹(shù)；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷右子樹(shù)。中（根）序的遍歷算法：6.3遍歷二叉樹(shù)和線索二叉樹(shù)

若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）后序遍歷左子樹(shù)；（2）后序遍歷右子樹(shù)；（3）訪問(wèn)根結(jié)點(diǎn)。后（根）序的遍歷算法：6.3遍歷二叉樹(shù)和線索二叉樹(shù)ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A6.3遍歷二叉樹(shù)和線索二叉樹(shù)

算法的遞歸描述（6.1）6.3遍歷二叉樹(shù)和線索二叉樹(shù)voidpreorder(BiTree*T){if(T){printf("%d\t",T->data);preorder(T->lchild);preorder(T->rchild);}}主程序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);先序序列：ABDC6.3遍歷二叉樹(shù)和線索二叉樹(shù)

算法的非遞歸描述

二叉樹(shù)表示表達(dá)式

基本思想

若表達(dá)式為數(shù)或簡(jiǎn)單變量，則相應(yīng)二叉樹(shù)只有根結(jié)點(diǎn)，其數(shù)據(jù)域存放表達(dá)式信息；否則，表達(dá)式均可寫(xiě)成<第一操作數(shù)>（運(yùn)算符）<第二操作數(shù)>形式，其中，“運(yùn)算符”可用二叉樹(shù)的根結(jié)點(diǎn)表示，“第一操作數(shù)”用二叉樹(shù)的左子樹(shù)表示，“第二操作數(shù)”用二叉樹(shù)的右子樹(shù)表示。操作數(shù)本身可以是表達(dá)式。6.3遍歷二叉樹(shù)和線索二叉樹(shù)表達(dá)式=(操作數(shù)1)(運(yùn)算符)(操作數(shù)2)運(yùn)算符操作數(shù)1操作數(shù)26.3遍歷二叉樹(shù)和線索二叉樹(shù)例如：a+b*(c-d)-e/f的二叉樹(shù)表示。abcef-+*/d-先序（前綴表達(dá)式）中序（中綴表達(dá)式）后序（后綴表達(dá)式）-+a*b-cd/efa+b*c-d-e/fabcd-*+ef/-6.3遍歷二叉樹(shù)和線索二叉樹(shù)abc-*-*cab-*abc先序遍歷：-*abc6.3遍歷二叉樹(shù)和線索二叉樹(shù)abc-*-*cab中序遍歷：

a*b-ca*bc-6.3遍歷二叉樹(shù)和線索二叉樹(shù)abc-*-*cab后序遍歷：

ab*c-ab*c-6.3遍歷二叉樹(shù)和線索二叉樹(shù)

二叉樹(shù)遍歷的非遞歸算法6.2ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問(wèn)：C(4)6.3遍歷二叉樹(shù)和線索二叉樹(shù)pABCDEFGiP->A訪問(wèn)：CB(5)ABCDEFGiP->AP->D訪問(wèn)：CBp(6)ABCDEFGiP->AP->DP->E訪問(wèn)：CBp(7)ABCDEFGiP->AP->D訪問(wèn)：CBEp(8)6.3遍歷二叉樹(shù)和線索二叉樹(shù)ABCDEFGiP->AP->DP->G訪問(wèn)：CBEP=NULL(9)ABCDEFGiP->A訪問(wèn)：CBEGDp(11)ABCDEFGiP->AP->F訪問(wèn)：CBEGDp(12)ABCDEFGiP->AP->D訪問(wèn)：CBEGp(10)6.3遍歷二叉樹(shù)和線索二叉樹(shù)ABCDEFGiP->A訪問(wèn)：CBEGDFp=NULL(13)ABCDEFGi訪問(wèn)：CBEGDFAp(14)ABCDEFGi訪問(wèn)：CBEGDFAp=NULL(15)6.3遍歷二叉樹(shù)和線索二叉樹(shù)

建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

遍歷算法的應(yīng)用舉例

統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)

求二叉樹(shù)的深度

二叉樹(shù)表示表達(dá)式6.3遍歷二叉樹(shù)和線索二叉樹(shù)

統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)

算法基本思想:

先序(或中序或后序)遍歷二叉樹(shù)，在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問(wèn)結(jié)點(diǎn)”的操作改為:若是葉子，則計(jì)數(shù)器增1。算法實(shí)現(xiàn)6.3遍歷二叉樹(shù)和線索二叉樹(shù)否則，整個(gè)二叉樹(shù)中的葉子結(jié)點(diǎn)個(gè)數(shù)等于其左子樹(shù)中的葉子結(jié)點(diǎn)個(gè)數(shù)和其右子樹(shù)中的葉子結(jié)點(diǎn)個(gè)數(shù)之和。

另一種算法思想分析方法:若二叉樹(shù)為空，則葉子結(jié)點(diǎn)的個(gè)數(shù)為零;若二叉樹(shù)中只有一個(gè)(根)結(jié)點(diǎn)，則葉子結(jié)點(diǎn)的個(gè)數(shù)為1;(后序遍歷)算法實(shí)現(xiàn)6.3遍歷二叉樹(shù)和線索二叉樹(shù)

求二叉樹(shù)的深度算法基本思想:若二叉樹(shù)為空樹(shù)，則深度為0;否則，二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深度的最大值加1。由此，需先分別求得左、右子樹(shù)的深度。

首先分析二叉樹(shù)的深度和它的左、右子樹(shù)深度之間的關(guān)系(后序遍歷)6.3遍歷二叉樹(shù)和線索二叉樹(shù)intDepth(BiTreeT){//返回二叉樹(shù)的深度

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}returndepthval;}6.3遍歷二叉樹(shù)和線索二叉樹(shù)也可以從另一角度去分析:

從二叉樹(shù)深度的定義還可知，二叉樹(shù)的深度即為其葉子結(jié)點(diǎn)所在層次的最大值。由此，可通過(guò)遍歷求得二叉樹(shù)中所有結(jié)點(diǎn)的“層次”，從中取其最大值。算法中需引入一個(gè)計(jì)結(jié)點(diǎn)層次的參數(shù)。

首先分析二叉樹(shù)的深度和結(jié)點(diǎn)的“層次”間的關(guān)系。6.3遍歷二叉樹(shù)和線索二叉樹(shù)voidDepth(BiTreeT,intlevel,int&dval){if(T){if(level>dval)dval=level;

Depth(T->lchild,level+1,dval);

Depth(T->rchild,level+1,dval);}}//調(diào)用之前l(fā)evel的初值為1。

//dval的初值為0.6.3遍歷二叉樹(shù)和線索二叉樹(shù)

建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法6.3遍歷二叉樹(shù)和線索二叉樹(shù)

以字符串的形式“根左子樹(shù)右子樹(shù)”定義一棵二叉樹(shù)（算法6.4）例如:A(B(,C(,)),D(,))以字符串“A”表示ABCD以空白字符“”表示空樹(shù)只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù)A以下列字符串表示6.3遍歷二叉樹(shù)和線索二叉樹(shù)void

CreateBiTree(BiTree&T)

{

scanf(&ch);if(ch=='')T=NULL;else{

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

CreateBiTree(T->lchild);//構(gòu)造左子樹(shù)

CreateBiTree(T->rchild);//構(gòu)造右子樹(shù)

}}//CreateBiTree6.3遍歷二叉樹(shù)和線索二叉樹(shù)AB

C

D

ABCD上頁(yè)算法執(zhí)行過(guò)程舉例如下:ATBCD^^^^^scanf(&ch);if(ch=='')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));T->data=ch;CreateBiTree(T->lchild);

CreateBiTree(T->rchild);}6.3遍歷二叉樹(shù)和線索二叉樹(shù)

二叉樹(shù)的遍歷有許多重要性質(zhì)，現(xiàn)以例子加以說(shuō)明。例如：僅知二叉樹(shù)的先序序列“abcdefg”不能唯一確定一棵二叉樹(shù)，如果同時(shí)已知二叉樹(shù)的中序序列“cbdaegf”，則會(huì)如何？二叉樹(shù)的先序序列二叉樹(shù)的中序序列左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列6.3遍歷二叉樹(shù)和線索二叉樹(shù)此例推論可知，二叉樹(shù)遍歷的重要性質(zhì)：若已知二叉樹(shù)的先序序列和中序序列，可唯一確定一棵二叉樹(shù)；若已知二叉樹(shù)的后序序列和中序序列，也可唯一確定一棵二叉樹(shù)。6.3遍歷二叉樹(shù)和線索二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)2、線索二叉樹(shù)

線索二叉樹(shù)定義

線索二叉樹(shù)的遍歷

中序遍歷二叉線索樹(shù)的算法6.3遍歷二叉樹(shù)和線索二叉樹(shù)

二叉樹(shù)的遍歷本質(zhì)上是將一個(gè)復(fù)雜的非線性結(jié)構(gòu)轉(zhuǎn)換為線性結(jié)構(gòu)，使每個(gè)結(jié)點(diǎn)都有了唯一前驅(qū)和后繼（第一個(gè)結(jié)點(diǎn)無(wú)前驅(qū)，最后一個(gè)結(jié)點(diǎn)無(wú)后繼）。對(duì)于二叉樹(shù)的一個(gè)結(jié)點(diǎn)，查找其左、右孩子是方便的，其前驅(qū)后繼只有在遍歷中得到。為了容易找到前驅(qū)和后繼，有兩種方法：在結(jié)點(diǎn)結(jié)構(gòu)中增加向前和向后的指針fwd和bkd，這種方法增加了存儲(chǔ)開(kāi)銷

利用二叉樹(shù)的空鏈指針。

線索二叉樹(shù)定義n個(gè)結(jié)點(diǎn)的二叉鏈表有n+1個(gè)空鏈域證明：因除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一指針射入。

n個(gè)結(jié)點(diǎn)便有n-1個(gè)指針，即有n-1個(gè)非空鏈域。因有2n個(gè)鏈域

空鏈域個(gè)數(shù)為：2n-(n-1)=n+16.3遍歷二叉樹(shù)和線索二叉樹(shù)

為了節(jié)省存貯空間，我們可以利用這些空鏈域來(lái)存放結(jié)點(diǎn)的前趨和后繼的信息。為避免混淆，需在結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域：lchildltagdatartagrchild(特征位)0lchild域指示結(jié)點(diǎn)的左孩子ltag=1lchild域指示結(jié)點(diǎn)的前趨

rtag=0rchild域指示結(jié)點(diǎn)的右孩子

1rchild域指示結(jié)點(diǎn)的后繼6.3遍歷二叉樹(shù)和線索二叉樹(shù)

線索鏈表：以上述結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表其中指向結(jié)點(diǎn)前趨和后繼的指針，叫做線索

線索二叉樹(shù)：加上線索的二叉樹(shù)對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程叫做線索化。例如：中序線索二叉樹(shù)作業(yè)：畫(huà)先序，后序線索樹(shù)！6.3遍歷二叉樹(shù)和線索二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)abcef-+*/d-NILNIL中序線索二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)010-00+00/01a10*01e11b10-01c11d11f1thrtbt中序線索鏈表頭結(jié)點(diǎn)：lt=0,lc指向根結(jié)點(diǎn)rt=1,rc指向遍歷序列中最后一個(gè)結(jié)點(diǎn)遍歷序列中第一個(gè)結(jié)點(diǎn)的lc域和最后一個(gè)結(jié)點(diǎn)的rc域都指向頭結(jié)點(diǎn)

只要先找到序列中的第一個(gè)結(jié)點(diǎn)，依次找結(jié)點(diǎn)的后繼直到其后繼為空為止。6.3遍歷二叉樹(shù)和線索二叉樹(shù)

線索二叉樹(shù)的遍歷

在中序線索樹(shù)中找結(jié)點(diǎn)的后繼：

(1)若結(jié)點(diǎn)的rtag為1（葉子），則其后繼為線索rchild所指結(jié)點(diǎn)（2）（否則）若結(jié)點(diǎn)的rtag為0（非葉子），則其后繼為“從其右孩子沿著左鏈找到ltag為1的那個(gè)結(jié)點(diǎn)”

(即右子樹(shù)最左下的結(jié)點(diǎn)）6.3遍歷二叉樹(shù)和線索二叉樹(shù)

在中序線索樹(shù)中找結(jié)點(diǎn)的前驅(qū)：

(1)若結(jié)點(diǎn)的ltag為1（葉子），則其前驅(qū)為線索lchild所指結(jié)點(diǎn)（2）（否則）若結(jié)點(diǎn)的ltag為0（非葉子），則其前驅(qū)為“從其左孩子沿著右鏈找到rtag為1的那個(gè)結(jié)點(diǎn)”(即左子樹(shù)最右下的結(jié)點(diǎn)）

在后序線索二叉樹(shù)中查找結(jié)點(diǎn)的前驅(qū)和后繼要知道其雙親的信息，要使用棧，所以說(shuō)后序線索二叉樹(shù)是不完善的。6.3遍歷二叉樹(shù)和線索二叉樹(shù)

二叉樹(shù)的二叉線索存儲(chǔ)表示Typedefenum{Link,Thread}pointerTag;//Link==0:指針，Thread==1：線索TypedefstructBiThrNode{TElemTypedata;structBiThrNode*lchild,*rchild;PointerTagLtag,Rtag;}BiThrNode,*BiThrTree;二叉樹(shù)的線索化：是在遍歷的過(guò)程中，將二叉鏈表中的空指針改為線索中序遍歷的線索化算法在二叉樹(shù)的線索鏈表上加一個(gè)頭結(jié)點(diǎn)，令其lchild指向二叉樹(shù)的根結(jié)點(diǎn)，rchild指向中序遍歷時(shí)訪問(wèn)的最后一個(gè)結(jié)點(diǎn)令二叉樹(shù)中序序列中的第一個(gè)結(jié)點(diǎn)的lchild和最后一個(gè)結(jié)點(diǎn)的rchild均指向頭結(jié)點(diǎn)（象雙向鏈表，可雙向遍歷）設(shè)指針p指向當(dāng)前訪問(wèn)結(jié)點(diǎn)，pre指向其前驅(qū)結(jié)點(diǎn)6.3遍歷二叉樹(shù)和線索二叉樹(shù)

中序遍歷二叉線索樹(shù)的算法

中序遍歷二叉線索樹(shù)T的非遞歸算法思想：找左子樹(shù)的最左葉子結(jié)點(diǎn)，訪問(wèn)訪問(wèn)后繼結(jié)點(diǎn)6.3遍歷二叉樹(shù)和線索二叉樹(shù)

學(xué)習(xí)線索化時(shí)，有三點(diǎn)必須注意：

何種序的線索化，是先序、中序還是后序要前驅(qū)線索化、后繼線索化還是全線索化（前驅(qū)后繼都要）只有空指針處才能加線索;6.4

樹(shù)和森林1、樹(shù)的三種存儲(chǔ)結(jié)構(gòu)

雙親表示法

孩子鏈表表示法

樹(shù)的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法6.4

樹(shù)和森林ABCDEFGr=0n=60

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent

雙親表示法雙親位置缺點(diǎn)：只反映了雙親位置6.4

樹(shù)和森林

typedefstructPTNode{ElemTypedata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類型描述:6.4

樹(shù)和森林typedefstruct{

PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}PTree;樹(shù)結(jié)構(gòu):6.4

樹(shù)和森林r=0n=6

datafirstchildABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4645

123

孩子鏈表表示法-1000224parent6.4

樹(shù)和森林typedefstructCTNode{

intchild;

structCTNode*next;}*ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu):

childnextchildC語(yǔ)言的類型描述:6.4

樹(shù)和森林

typedefstruct{ElemTypedata;ChildPtrfirstchild;//孩子鏈的頭指針

}CTBox;雙親結(jié)點(diǎn)結(jié)構(gòu)

datafirstchild6.4

樹(shù)和森林typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置

}CTree;樹(shù)結(jié)構(gòu):6.4

樹(shù)和森林ABCDEFGrootABCEDFGABCEDFG

樹(shù)的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法root6.4

樹(shù)和森林typedefstructCSNode{ElemTypedata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C語(yǔ)言的類型描述:結(jié)點(diǎn)結(jié)構(gòu):

firstchilddatanextsibling6.4

樹(shù)和森林2、森林與二叉樹(shù)的轉(zhuǎn)換

森林和二叉樹(shù)的對(duì)應(yīng)關(guān)系

森林轉(zhuǎn)換成二叉樹(shù)

二叉樹(shù)轉(zhuǎn)換成森林6.4

樹(shù)和森林

森林和二叉樹(shù)的對(duì)應(yīng)關(guān)系設(shè)森林

F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉樹(shù)

B=(LBT,Node(root),RBT);6.4

樹(shù)和森林T1T11,T12,…,T1mT2,…,TnLBTRBTroot6.4

樹(shù)和森林BCADEBACDE二叉鏈表作為中間媒介6.4

樹(shù)和森林BCADBACDFEGHIJACDBGHIJEFFEHIJG樹(shù)與二叉樹(shù)對(duì)應(yīng)樹(shù)根相連森林與二叉樹(shù)對(duì)應(yīng)6.4

樹(shù)和森林由森林轉(zhuǎn)換成二叉樹(shù)的轉(zhuǎn)換規(guī)則為:若F=Φ，即m=0，則B=Φ;

由ROOT(T1)

對(duì)應(yīng)得到Node(root);否則，即m

0由(T2,T3,…,Tn)

對(duì)應(yīng)得到RBT。RBT是由(T2,T3,…,Tn)

轉(zhuǎn)換的二叉樹(shù)若F={T1,T2,T3,…,Tn},則按如下規(guī)則轉(zhuǎn)換二叉樹(shù)B=(root,LBT,RBT)：6.4

樹(shù)和森林由二叉樹(shù)轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為:由LBT

對(duì)應(yīng)得到(t11,t12,…，t1m);若B=Φ,則F=Φ;否則，由Node(root)

對(duì)應(yīng)得到ROOT(T1

);由RBT

對(duì)應(yīng)得到(T2,T3,…,Tn)。6.4

樹(shù)和森林

由此，樹(shù)和森林的各種操作均可與二叉樹(shù)的各種操作相對(duì)應(yīng)。

應(yīng)當(dāng)注意的是，和樹(shù)對(duì)應(yīng)的二叉樹(shù)，其左、右子樹(shù)的概念已改變?yōu)椋?/p>

左是孩子，右是兄弟6.4

樹(shù)和森林

樹(shù)的遍歷

森林的遍歷3、樹(shù)和森林的遍歷6.4

樹(shù)和森林樹(shù)的遍歷可有2條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:

若樹(shù)不空，則先訪問(wèn)根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹(shù)。

若樹(shù)不空，則先依次后根遍歷各棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。

若樹(shù)不空，則自上而下自左至右訪問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)。6.4

樹(shù)和森林ABCDEFGHIJK層次遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：

先根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：ABEFCDGHIJK后根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：EFBCIJKHGDAABCDEFGHIJK6.4

樹(shù)和森林

層次遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：ABCDEFGHIJK

先根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：ABEFCDGHIJK

后根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：EFBCIJKHGDAABCDEFGHIJK6.4

樹(shù)和森林

BCDEFGHIJK（1）森林中第一棵樹(shù)的根結(jié)點(diǎn)；（2）森林中第一棵樹(shù)的子樹(shù)森林；（3）森林中其它樹(shù)構(gòu)成的森林?？梢苑纸獬扇糠郑荷?.4

樹(shù)和森林

若森林不空，則訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn);先序遍歷森林中第一棵樹(shù)的子樹(shù)森林;先序遍歷森林中(除第一棵樹(shù)之外)其余樹(shù)構(gòu)成的森林。先序遍歷

森林的遍歷即：依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)行先根遍歷。6.4

樹(shù)和森林

中序遍歷

若森林不空，則中序遍歷森林中第一棵樹(shù)的子樹(shù)森林;訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn);中序遍歷森林中(除第一棵樹(shù)之外)其

余樹(shù)構(gòu)成的森林。即：依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)行后根遍歷。6.4

樹(shù)和森林

樹(shù)的遍歷和二叉樹(shù)遍歷的對(duì)應(yīng)關(guān)系？先根遍歷后根遍歷樹(shù)二叉樹(shù)森林先序遍歷先序遍歷中序遍歷中序遍歷6.6

赫夫曼樹(shù)及其應(yīng)用

最優(yōu)二叉樹(shù)（赫夫曼樹(shù)）

如何構(gòu)造最優(yōu)二叉樹(shù)

赫夫曼樹(shù)應(yīng)用

最優(yōu)二叉樹(shù)的定義樹(shù)的路徑長(zhǎng)度定義為：

樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。

結(jié)點(diǎn)的路徑長(zhǎng)度定義為：

從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。6.6

赫夫曼樹(shù)及其應(yīng)用

樹(shù)的帶權(quán)路徑長(zhǎng)度定義為：

樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和

WPL(T)=

wklk(對(duì)所有葉子結(jié)點(diǎn))

其中：wk——權(quán)值

lk——結(jié)點(diǎn)到根的路徑長(zhǎng)度

在所有含n個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán)值的m叉樹(shù)中，必存在一棵其帶權(quán)路徑長(zhǎng)度取最小值的樹(shù)，稱為“最優(yōu)二叉樹(shù)”。例如：6.6

赫夫曼樹(shù)及其應(yīng)用WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=896.6赫夫曼樹(shù)及其應(yīng)用2475979542

根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹(shù)的集合

F={T1,T2,…,Tn}

其中每棵二叉樹(shù)中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹(shù)為空樹(shù);

如何構(gòu)造最優(yōu)二叉樹(shù)(1)(赫夫曼算法)以二叉樹(shù)為例:6.6赫夫曼樹(shù)及其應(yīng)用

在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹(shù)，分別作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，并置這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值

為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和;(2)6.6赫夫曼樹(shù)及其應(yīng)用

從F中刪去這兩棵樹(shù)，同時(shí)加入剛生成的新樹(shù);

重復(fù)(2)和(3)兩步，直至F中只含一棵樹(shù)為止。(3)(4)6.6赫夫曼樹(shù)及其應(yīng)用9例如:已知權(quán)值W={5,6,2,9,7}5627527697671395276.6赫夫曼樹(shù)及其應(yīng)用67139527952716671329000011110001111001016.6赫夫曼樹(shù)及其應(yīng)用

利用赫夫曼樹(shù)解決判別問(wèn)題分?jǐn)?shù)0-5960-6970-7980-8990-100比例樹(shù)0.050.150.400.300.10A<60A<70A<80A<90不及格及格中等良好優(yōu)秀NNNNYYYY6.6赫夫曼樹(shù)及其應(yīng)用(a)10000個(gè)輸入比較31500次利用赫夫曼樹(shù)構(gòu)造最佳判定樹(shù)6.6赫夫曼樹(shù)及其應(yīng)用70A<80不及格及格中等良好優(yōu)秀NNYNYYY80A<90A<6060A<70N(b)僅比較22000次A<80不及格及格中等良好優(yōu)秀NNYNYYYNA<70A<90A<60(c)拆分條件515403010

Huffman編碼構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長(zhǎng)度最短。6.6赫夫曼樹(shù)及其應(yīng)用

數(shù)據(jù)通信用的二進(jìn)制編碼思想：根據(jù)字符出現(xiàn)頻率編碼，利