第六章樹狀結(jié)構(gòu)

第六章樹狀結(jié)構(gòu)第一頁，共一百三十九頁，編輯于2023年，星期五26.1樹的類型定義6.2二叉樹的類型定義6.3

二叉樹的存儲結(jié)構(gòu)6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼第二頁，共一百三十九頁，編輯于2023年，星期五36.1樹的類型定義第三頁，共一百三十九頁，編輯于2023年，星期五4數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；

(2)當(dāng)n>1時，其余結(jié)點(diǎn)可分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一個子集本身又是一棵符合本定義的樹，稱為根root的子樹。

數(shù)據(jù)關(guān)系R：第四頁，共一百三十九頁，編輯于2023年，星期五5

基本操作：查找類

插入類刪除類第五頁，共一百三十九頁，編輯于2023年，星期五6

Root(T)//求樹的根結(jié)點(diǎn)

查找類：Value(T,cur_e)//求cur_e結(jié)點(diǎn)的元素值

Parent(T,cur_e)//求cur_e結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T,cur_e)//求cur_e結(jié)點(diǎn)的最左孩子RightSibling(T,cur_e)//求cur_e結(jié)點(diǎn)的右兄弟TreeEmpty(T)//判定樹是否為空樹TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷第六頁，共一百三十九頁，編輯于2023年，星期五7InitTree(&T)//初始化置空樹

插入類：CreateTree(&T,definition)//按定義構(gòu)造樹Assign(T,&cur_e,value)//給cur_e結(jié)點(diǎn)賦值InsertChild(&T,&p,i,c)//插入c為T中P所指結(jié)點(diǎn)的第i棵子樹第七頁，共一百三十九頁，編輯于2023年，星期五8

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點(diǎn)p的第i棵子樹第八頁，共一百三十九頁，編輯于2023年，星期五9ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:樹的圖示表示法樹的廣義表表示法第九頁，共一百三十九頁，編輯于2023年，星期五10ABDCJIHMEFGKL樹的嵌套集合表示法第十頁，共一百三十九頁，編輯于2023年，星期五11(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：子樹之間不存在確定的次序關(guān)系。第十一頁，共一百三十九頁，編輯于2023年，星期五12基本術(shù)語第十二頁，共一百三十九頁，編輯于2023年，星期五13結(jié)點(diǎn):結(jié)點(diǎn)的度:樹的度:葉子結(jié)點(diǎn):分支結(jié)點(diǎn):數(shù)據(jù)元素+若干指向子樹的分支分支的個數(shù)（子樹的個數(shù)）樹中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)包含根結(jié)點(diǎn)和中間結(jié)點(diǎn)DHIJM第十三頁，共一百三十九頁，編輯于2023年，星期五14(從根到結(jié)點(diǎn)的)路徑：孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)兄弟結(jié)點(diǎn)、堂兄弟祖先結(jié)點(diǎn)、子孫結(jié)點(diǎn)結(jié)點(diǎn)的層次:樹的深度：

由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1，根的孩子為第2層，如果某結(jié)點(diǎn)在第L層,則其子樹的根在L+1層。樹中葉子結(jié)點(diǎn)所在的最大層次第十四頁，共一百三十九頁，編輯于2023年，星期五15任何一棵非空樹是一個二元組

Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點(diǎn)

F被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF第十五頁，共一百三十九頁，編輯于2023年，星期五16對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)第十六頁，共一百三十九頁，編輯于2023年，星期五17~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)

樹型結(jié)構(gòu)

（非線性結(jié)構(gòu)）第一個數(shù)據(jù)元素

(無前驅(qū))

根結(jié)點(diǎn)

(無前驅(qū))最后一個數(shù)據(jù)元素

(無后繼)多個葉子結(jié)點(diǎn)

(無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)其它數(shù)據(jù)元素(一個前驅(qū)、

多個后繼)第十七頁，共一百三十九頁，編輯于2023年，星期五18趙老根趙躍進(jìn)趙小康趙改革趙開放趙抗美趙援朝趙衛(wèi)兵趙永紅第十八頁，共一百三十九頁，編輯于2023年，星期五196.2

二叉樹的類型定義第十九頁，共一百三十九頁，編輯于2023年，星期五20

二叉樹或為空樹，或是由一個根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。(二叉樹的度最大為2)ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹第二十頁，共一百三十九頁，編輯于2023年，星期五21二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點(diǎn)NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹第二十一頁，共一百三十九頁，編輯于2023年，星期五22

二叉樹的主要基本操作：查找類插入類刪除類第二十二頁，共一百三十九頁，編輯于2023年，星期五23

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());第二十三頁，共一百三十九頁，編輯于2023年，星期五24

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);第二十四頁，共一百三十九頁，編輯于2023年，星期五25ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);第二十五頁，共一百三十九頁，編輯于2023年，星期五26二叉樹

的重要特性第二十六頁，共一百三十九頁，編輯于2023年，星期五27性質(zhì)1：二叉樹第i層上至多有2i-1個結(jié)點(diǎn)。(i≥1)用歸納法證明：

歸納基：歸納假設(shè)：歸納證明：i=1層時，只有一個根結(jié)點(diǎn)：

2i-1=20=1；假設(shè)當(dāng)j=i-1時,命題成立；即j層最多有2j-1（2i-2）個節(jié)點(diǎn)二叉樹上每個結(jié)點(diǎn)至多有兩棵子樹，則第i層的結(jié)點(diǎn)數(shù)=2i-22=2i-1。第二十七頁，共一百三十九頁，編輯于2023年，星期五28性質(zhì)2：

深度為k的二叉樹上至多含2k-1個結(jié)點(diǎn)（k≥1）。證明：

基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點(diǎn)數(shù)至多為

20+21+

+2k-1=2k-1

。（等比數(shù)列求和）第二十八頁，共一百三十九頁，編輯于2023年，星期五29

性質(zhì)3：

對任何一棵二叉樹，若它含有n0個葉子結(jié)點(diǎn)（0度節(jié)點(diǎn)）、n2個度為2的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1。證明：二叉樹上結(jié)點(diǎn)總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。第二十九頁，共一百三十九頁，編輯于2023年，星期五30兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的n個結(jié)點(diǎn)和滿二叉樹中編號為1至n的結(jié)點(diǎn)一一對應(yīng)。（編號的規(guī)則為，由上到下，從左到右。）123456789101112131415abcdefghij特點(diǎn)

1.葉子結(jié)點(diǎn)出現(xiàn)在最后2層

2.對于任意結(jié)點(diǎn)，若其右分支下的子孫的最大層次為L,

則左分支下的子孫的最大層次為L或L+1第三十頁，共一百三十九頁，編輯于2023年，星期五31

性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹的深度為

log2n+1(k≥1）證明：設(shè)完全二叉樹的深度為k則根據(jù)第二條性質(zhì)得2k-1-1<

n≤2k-1

即k-1≤

log2n<

k

k是整數(shù)，因此，k=log2n+1第三十一頁，共一百三十九頁，編輯于2023年，星期五32性質(zhì)5：若對含n個結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行1

至n

的編號，則對完全二叉樹中任意一個編號為i

的結(jié)點(diǎn)：

(1)若i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親，否則，編號為i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)；

(2)若2i＞n，則序號為i的結(jié)點(diǎn)無左孩子；

否則，編號為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；

(3)若2i+1＞n，則該序號為i的結(jié)點(diǎn)無右孩子；

否則，編號為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。第三十二頁，共一百三十九頁，編輯于2023年，星期五深度為k的完全二叉樹至少有

個結(jié)點(diǎn)，至多有

個結(jié)點(diǎn)，k和n之間關(guān)系為

。設(shè)高度為h的二叉樹只有度為偶數(shù)的結(jié)點(diǎn)，則至少有

個結(jié)點(diǎn)，至多有

個結(jié)點(diǎn)。一棵有124個葉子結(jié)點(diǎn)的完全二叉樹，最多有

個結(jié)點(diǎn)。完全二叉樹的某結(jié)點(diǎn)若無左孩子，則必為葉子結(jié)點(diǎn)？具有n個結(jié)點(diǎn)的滿二叉樹葉子結(jié)點(diǎn)有

。2k-12k-1log2n+1

2h-12h-1248(n+1)/2第三十三頁，共一百三十九頁，編輯于2023年，星期五346.3二叉樹的存儲結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯Ρ硎疽?、二叉樹的順序存儲表示第三十四頁，共一百三十九頁，編輯?023年，星期五35#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點(diǎn)數(shù)typedefunsignedcharTElemType;typedefTElemTypeSqBiTree[MAX_TREE_SIZE+1];SqBiTreebt;一、二叉樹的順序存儲表示第三十五頁，共一百三十九頁，編輯于2023年，星期五36例如:ABCDEF

ABD0C0E000000F12345678910111213142511437一般樹按完全二叉的方式存儲非常浪費(fèi)空間！深度為K的單支樹，需要2k個空間

第三十六頁，共一百三十九頁，編輯于2023年，星期五37二、二叉樹的鏈?zhǔn)酱鎯Ρ硎?.二叉鏈表2．三叉鏈表第三十七頁，共一百三十九頁，編輯于2023年，星期五38ADEBCFrootlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):1.二叉鏈表第三十八頁，共一百三十九頁，編輯于2023年，星期五39typedefcharTElemType;typedefstructNode{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;structNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述如下:第三十九頁，共一百三十九頁，編輯于2023年，星期五40ADEBCFroot2．三叉鏈表parent

lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):第四十頁，共一百三十九頁，編輯于2023年，星期五41

typedefstructNode{//結(jié)點(diǎn)結(jié)構(gòu)

structNode*parent;//雙親指針

TElemTypedata;structNode*lchild,*rchild;//左右孩子指針

}TriTreeNode,*TriTree;parentlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述如下:第四十一頁，共一百三十九頁，編輯于2023年，星期五426.4二叉樹的遍歷第四十二頁，共一百三十九頁，編輯于2023年，星期五43一、問題的提出二、先左后右的遍歷算法三、算法的遞歸描述四、遍歷算法的非遞歸描述第四十三頁，共一百三十九頁，編輯于2023年，星期五44

順著某一條搜索路徑尋訪二叉樹中的結(jié)點(diǎn)，使得每個結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。（將樹線性化）一、問題的提出（尋找某個結(jié)點(diǎn)）“訪問”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息或判定結(jié)點(diǎn)滿足某些條件等。第四十四頁，共一百三十九頁，編輯于2023年，星期五45

“遍歷”是任何數(shù)據(jù)結(jié)構(gòu)均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因為每個結(jié)點(diǎn)均只有一個后繼)故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，

每個結(jié)點(diǎn)有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。第四十五頁，共一百三十九頁，編輯于2023年，星期五46對“二叉樹”而言，可以有三條搜索方法：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；3．先右（子樹）后左（子樹）的遍歷。第四十六頁，共一百三十九頁，編輯于2023年，星期五47二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法第四十七頁，共一百三十九頁，編輯于2023年，星期五48例：將如下表達(dá)式

a+b*(c-d)-e/f存入一個樹結(jié)構(gòu)。葉子結(jié)點(diǎn)為操作數(shù)中間結(jié)點(diǎn)為運(yùn)算符f/e-dc-ab*+第四十八頁，共一百三十九頁，編輯于2023年，星期五49

若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：順序：-+a*b-cd/ef正好是前綴表達(dá)式第四十九頁，共一百三十九頁，編輯于2023年，星期五50

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。中（根）序的遍歷算法：順序：a+b*c-d-e/f正好是中綴表達(dá)式第五十頁，共一百三十九頁，編輯于2023年，星期五51

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。后（根）序的遍歷算法：順序：abcd-*+ef/-正好是后綴表達(dá)式第五十一頁，共一百三十九頁，編輯于2023年，星期五52三、算法的遞歸描述voidPreOrder(BiTreeT,void(*Visit)(TElemType)){if(T){

visit(T->data);//訪問根結(jié)點(diǎn)

PreOrder(T->lchild,visit);//遍歷左子樹

PreOrder(T->rchild,visit);//遍歷右子樹

}}ADBT第五十二頁，共一百三十九頁，編輯于2023年，星期五53voidInOrder(BiTreeT,void(*Visit)(TElemType)){//中序遍歷二叉樹

if(T){

InOrder(T->lchild,visit);//遍歷左子樹

visit(T->data);//訪問根結(jié)點(diǎn)

InOrder(T->rchild,visit);//遍歷右子樹

}}第五十三頁，共一百三十九頁，編輯于2023年，星期五54voidPostOrder(BiTreeT,void(*Visit)(TElemType)){//后序遍歷二叉樹

if(T){

PostOrder(T->lchild,visit);//遍歷左子樹

PostOrder(T->rchild,visit);//遍歷右子樹

visit(T->data);//訪問根結(jié)點(diǎn)

}}第五十四頁，共一百三十九頁，編輯于2023年，星期五55

可以這樣理解：無論先序、中序、后序遍歷二叉樹，遍歷時的搜索路線是相同的：從根結(jié)點(diǎn)出發(fā)，逆時針沿二叉樹外緣移動對每個結(jié)點(diǎn)均途經(jīng)三次。先序遍歷：第一次經(jīng)過結(jié)點(diǎn)時訪問。中序遍歷：第二次經(jīng)過結(jié)點(diǎn)時訪問。后序遍歷：第三次經(jīng)過結(jié)點(diǎn)時訪問。ABΦΦΦ123第五十五頁，共一百三十九頁，編輯于2023年，星期五56四、先序遍歷算法的非遞歸描述1.初始化設(shè)置一個棧；

2.根結(jié)點(diǎn)指針入棧；

3.堆棧非空時：（1）出棧取得結(jié)點(diǎn)指針，visit該結(jié)點(diǎn)（2）若該結(jié)點(diǎn)右子樹不空，右子樹指針進(jìn)棧；（3）若該結(jié)點(diǎn)左子樹不空，左子樹指針進(jìn)棧；第五十六頁，共一百三十九頁，編輯于2023年，星期五57voidpre_s(BiTreet){SqStacks;BiTreep;Init_Sq(s);if(t){push(s,t);while(!StackEmpty(s)){pop(s,p);printf("%d",p->data);if(p->rchild)push(s,p->rchild);if(p->lchild)push(s,p->lchild);}}}第五十七頁，共一百三十九頁，編輯于2023年，星期五58五、中序遍歷算法的非遞歸描述voidGoFarLeft(BiTreebt,BiTree&p){if(bt){p=bt;while(p->lchild){push(s,p);p=p->lchild;}}//得到樹T最左結(jié)點(diǎn)的指針}第五十八頁，共一百三十九頁，編輯于2023年，星期五59voidin_s(BiTreet){BiTreep=t;Init_Sq(s);GoFarLeft(t,p);//找到最左的結(jié)點(diǎn)

while(p){printf("%d",p->data);if(p->rchild)GoFarLeft(p->rchild,p);elseif(!StackEmpty(s))//棧不空時退棧

pop(s,p);else p=NULL;//?？毡砻鞅闅v結(jié)束

}//while}第五十九頁，共一百三十九頁，編輯于2023年，星期五60遍歷算法的應(yīng)用舉例1、建立二叉樹的存儲結(jié)構(gòu)3、求二叉樹的深度(后序遍歷)2、統(tǒng)計二叉樹中葉子結(jié)點(diǎn)的個數(shù)

第六十頁，共一百三十九頁，編輯于2023年，星期五611、建立二叉樹的存儲結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法第六十一頁，共一百三十九頁，編輯于2023年，星期五62

以字符串的形式根左子樹右子樹定義一棵二叉樹例如:ABCD以字符“#”表示A(B(#,C(#,#)),D(#,#))空樹只含一個根結(jié)點(diǎn)的二叉樹A以字符串“A##”表示以下列字符串表示第六十二頁，共一百三十九頁，編輯于2023年，星期五63voidCreateBiTree(BiTree&bt){/*以擴(kuò)展的先序序列輸入數(shù)據(jù)*/charch;scanf("%c",&ch);if(ch=='#')bt=NULL;else{bt=(BiTree)malloc(sizeof(BiTNode));if(!bt)exit(1);bt->data=ch;CreateBiTree(bt->lchild);CreateBiTree(bt->rchild);}}第六十三頁，共一百三十九頁，編輯于2023年，星期五64AB

C

D

ABCD上頁算法執(zhí)行過程舉例如下：ATBCD^^^^^第六十四頁，共一百三十九頁，編輯于2023年，星期五652、統(tǒng)計二叉樹中葉子結(jié)點(diǎn)的個數(shù)算法基本思想:遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計數(shù)。由此，需在遍歷算法中增添一個“計數(shù)”的參數(shù)，并將算法中“訪問結(jié)點(diǎn)”的操作改為：若是葉子，則計數(shù)器增1。第六十五頁，共一百三十九頁，編輯于2023年，星期五663、求二叉樹的深度(后序遍歷)算法基本思想:

從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點(diǎn)”的操作為：求得左、右子樹深度的最大值，然后加1。

首先分析二叉樹的深度和它的左、右子樹深度之間的關(guān)系。第六十六頁，共一百三十九頁，編輯于2023年，星期五67intdepthval,depthLeft,depthRight;intDepth(BiTreeT){//返回二叉樹的深度,T為樹根的指針

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}returndepthval;}第六十七頁，共一百三十九頁，編輯于2023年，星期五68例1.已知樹的先序次序為abdcegf

中序次序為bdaegcf則樹為？abdcfeg例2.已知樹的后序次序為dbgefca

中序次序為bdaegcf則樹為？我們可以利用先序次序和中序次序、后序次序和中序次序來確定一棵二叉樹。第六十八頁，共一百三十九頁，編輯于2023年，星期五696.5

線索二叉樹何謂線索二叉樹？線索鏈表的遍歷算法如何建立線索鏈表？第六十九頁，共一百三十九頁，編輯于2023年，星期五70一、何謂線索二叉樹？遍歷二叉樹的結(jié)果是，求得結(jié)點(diǎn)的一個線性序列。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA第七十頁，共一百三十九頁，編輯于2023年，星期五71指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”與其相應(yīng)的二叉樹，稱作“線索二叉樹”包含“線索”的存儲結(jié)構(gòu)，稱作“線索鏈表”ABCDEFGHK^D^

C^^B

E^第七十一頁，共一百三十九頁，編輯于2023年，星期五72例求如下二叉樹的先序線索樹、中序線索樹和后序線索樹。ABCDABCDABCDABCD先序線索樹中序線索樹后序線索樹abcdbcadcbdaNULLNULLNULLNULLNULL第七十二頁，共一百三十九頁，編輯于2023年，星期五73如何保存這種在遍歷過程中得到的信息？最簡單的方法是在每個結(jié)點(diǎn)上增加二個指針域：fwd和bkwd用來指示此結(jié)點(diǎn)在遍歷中的前驅(qū)和后繼結(jié)點(diǎn)。這樣，使結(jié)點(diǎn)的存儲密度大大降低。我們知道在n個結(jié)點(diǎn)的二叉樹中，有n+1個空鏈域。（空鏈域的個數(shù)=結(jié)點(diǎn)數(shù)*2–分支個數(shù)）

n結(jié)點(diǎn)二叉樹的空鏈域=2*n-(n-1)=n+1我們可以利用這n+1個空鏈域來存儲線索。第七十三頁，共一百三十九頁，編輯于2023年，星期五74對線索鏈表中結(jié)點(diǎn)的約定：

在二叉鏈表的結(jié)點(diǎn)中增加兩個標(biāo)志域，并作如下規(guī)定：若該結(jié)點(diǎn)的左子樹不空，則Lchild域的指針指向其左子樹，且左標(biāo)志域的值為“Link（指針）”；否則，Lchild域的指針指向其“前驅(qū)”，且左標(biāo)志的值為“Thread（線索）”

。第七十四頁，共一百三十九頁，編輯于2023年，星期五75若該結(jié)點(diǎn)的右子樹不空，則rchild域的指針指向其右子樹，且右標(biāo)志域的值為“Link（指針）”；否則，rchild域的指針指向其“后繼”，且右標(biāo)志的值為“Thread（線索）”。

如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表”。第七十五頁，共一百三十九頁，編輯于2023年，星期五76typedefstruct

BiThrNod{

TElemTypedata;

structBiThrNode*lchild,*rchild;//左右指針

PointerThrLTag,RTag;//左右標(biāo)志}BiThrNode,*BiThrTree;線索鏈表的類型描述：

#defineLink0//指針

#defineThread

1//線索

typedef

enum{

Link,Thread

}PointerThr;

第七十六頁，共一百三十九頁，編輯于2023年，星期五77要求：已知一個二叉樹，我們要會畫出它的各種線索樹。ABCDEFGHK畫出它的先序線索樹、中序線索樹、后序線索樹？第七十七頁，共一百三十九頁，編輯于2023年，星期五78ABCDEFGHK先序線索樹ABCDEFGHKNULL第七十八頁，共一百三十九頁，編輯于2023年，星期五79ABCDEFGHK后序線索樹DCBHKGFEANULL第七十九頁，共一百三十九頁，編輯于2023年，星期五80ABCDEFGHK中序線索樹BDCAHGKFENULLNULL第八十頁，共一百三十九頁，編輯于2023年，星期五81二、線索鏈表的遍歷算法:對于增加二個指針域的結(jié)構(gòu)：for(p=

firstNode(T);p;p=Succ(p))Visit(p);由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。第八十一頁，共一百三十九頁，編輯于2023年，星期五82例如：（對于利用空指針域的結(jié)構(gòu)）

//中序線索化鏈表的遍歷算法

※中序遍歷的第一個結(jié)點(diǎn)？

※在中序線索化鏈表中結(jié)點(diǎn)的后繼？左子樹上處于“最左”（沒有左子樹）的結(jié)點(diǎn)。若無右子樹，則為后繼線索所指結(jié)點(diǎn)；否則為對其右子樹進(jìn)行中序遍歷時訪問的第一個結(jié)點(diǎn)。第八十二頁，共一百三十九頁，編輯于2023年，星期五83voidInOrderTraverse_Thr(BiThrTreeT,

Status(*Visit)(TElemType)){

p=T->lchild;//p指向根結(jié)點(diǎn),T指向二叉線索樹的頭結(jié)點(diǎn)

while(p!=T){//空樹或遍歷結(jié)束時，p==Twhile(p->LTag==Link)p=p->lchild;//第一個結(jié)點(diǎn)

if(!visit(p->data))returnERROR;while(p->RTag==Thread&&p->rchild!=T)

{//訪問后繼結(jié)點(diǎn)

p=p->rchild;Visit(p->data)；

}p=p->rchild;//p進(jìn)至其右子樹根

}}//InOrderTraverse_Thr第八十三頁，共一百三十九頁，編輯于2023年，星期五84

在中序遍歷過程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問結(jié)點(diǎn)的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre,并始終保持指針p所指結(jié)點(diǎn)是當(dāng)前訪問的結(jié)點(diǎn)，pre指向p結(jié)點(diǎn)的前驅(qū)。三、如何建立線索鏈表？第八十四頁，共一百三十九頁，編輯于2023年，星期五85//已知一棵二叉樹，將其中序線索化//pre指向p的前驅(qū),第一次值為NULLvoid

InThreading(BiThrTreep)

{

if(p){//對以p為根的非空二叉樹進(jìn)行線索化

InThreading(p->lchild);

//左子樹線索化

if(!p->lchild)//建前驅(qū)線索

{p->LTag=Thread;p->lchild=pre;}

if(!pre->rchild)//建后繼線索

{pre->RTag=Thread;pre->rchild=p;}

pre=p;//保持pre指向p的前驅(qū)

InThreading(p->rchild);//右子樹線索化

}//if}//InThreading第八十五頁，共一百三十九頁，編輯于2023年，星期五86ABCDif(A){//InThreading(A),pre=NULL

InThreading(A->lchild);

//左子樹線索化

if(!A->lchild)//建前驅(qū)線索,pre=C

{A->LTag=Thread;A->lchild=pre;}

if(!pre->rchild)//建后繼線索

{pre->RTag=Thread;pre->rchild=A;}

pre=A;//保持pre指向p的前驅(qū)

InThreading(A->rchild);}if(B){//InThreading(B),pre=NULL

InThreading(B->lchild);

//左子樹線索化

if(!B->lchild)//建前驅(qū)線索

{B->LTag=Thread;B->lchild=pre;}

if(!pre->rchild)//建后繼線索

{pre->RTag=Thread;pre->rchild=B;}

pre=B;//保持pre指向p的前驅(qū)

InThreading(B->rchild);}ABCDNULL第八十六頁，共一百三十九頁，編輯于2023年，星期五87if(C){//InThreading(C),pre=B

InThreading(C->lchild);

//左子樹線索化

if(!C->lchild)//建前驅(qū)線索

{C->LTag=Thread;C->lchild=B;}

if(!B->rchild)//建后繼線索

{B->RTag=Thread;B->rchild=C;}

pre=C;//保持pre指向p的前驅(qū)

InThreading(C->rchild);}//pre=Cif(D){//InThreading(D),pre=A

InThreading(D->lchild);

//左子樹線索化

if(!D->lchild)//建前驅(qū)線索

{D->LTag=Thread;D->lchild=A;}

if(!A->rchild)//建后繼線索

{A->RTag=Thread;A->rchild=D;}

pre=D;//保持pre指向p的前驅(qū)

InThreading(D->rchild);}ABCDABCD第八十七頁，共一百三十九頁，編輯于2023年，星期五88StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//構(gòu)建中序線索鏈表

if(!(Thrt=(BiThrTree)malloc(

sizeof(BiThrNode))))

exit(OVERFLOW);

Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;

//添加頭結(jié)點(diǎn)

returnOK;`}//InOrderThreading

……第八十八頁，共一百三十九頁，編輯于2023年，星期五89if(!T)

Thrt->lchild=Thrt;

else{Thrt->lchild=T;

pre=Thrt;InThreading(T);

pre->rchild=Thrt;//處理最后一個結(jié)點(diǎn)

pre->RTag=Thread;

Thrt->rchild=pre;}第八十九頁，共一百三十九頁，編輯于2023年，星期五90

6.6樹和森林的表示方法第九十頁，共一百三十九頁，編輯于2023年，星期五91樹的三種存儲結(jié)構(gòu)一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟）存儲表示法第九十一頁，共一百三十九頁，編輯于2023年，星期五92ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7dataparent一、雙親表示法:第九十二頁，共一百三十九頁，編輯于2023年，星期五93

typedefstructPTNode{TElemTypedata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述:第九十三頁，共一百三十九頁，編輯于2023年，星期五94typedefstruct{PTNodenodes[MAX_TREE_SIZE];

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

}PTree;樹結(jié)構(gòu):第九十四頁，共一百三十九頁，編輯于2023年，星期五95ABCDEFG0

A1

B

2

C

3

D

4

E

5

F

6

G

r=0n=7datafirstchild123456二、孩子鏈表表示法:-1000224第九十五頁，共一百三十九頁，編輯于2023年，星期五96typedefstructCTNode{

intchild;//不是TElemType

structCTNode*next;

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

childnextC語言的類型描述:第九十六頁，共一百三十九頁，編輯于2023年，星期五97

typedefstruct{TElemTypedata;intparent;ChildPtrfirstchild;//孩子鏈表的頭指針

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

datafirstchildparent第九十七頁，共一百三十九頁，編輯于2023年，星期五98typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

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

}CTree;樹結(jié)構(gòu):第九十八頁，共一百三十九頁，編輯于2023年，星期五99ABCDEFGABCEDFGrootABCEDFG

三、樹的二叉鏈表(孩子-兄弟）存儲表示法第九十九頁，共一百三十九頁，編輯于2023年，星期五100要求

將一棵樹轉(zhuǎn)化為二叉樹

ABCDEFGHIJKLABCDEFKLGHIJ第一百頁，共一百三十九頁，編輯于2023年，星期五101typedefstructCSNode{TElemTypedata;

structCSNode

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

firstchilddatanextsibling第一百零一頁，共一百三十九頁，編輯于2023年，星期五102

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

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

B=(LBT,Node(root),RBT);第一百零二頁，共一百三十九頁，編輯于2023年，星期五103。。。T1T2T3T4TnT1T11T12T1m。。。T1T11T12T1m。。。T2T3Tn。。。第一百零三頁，共一百三十九頁，編輯于2023年，星期五104由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若F=Φ，則B=Φ；否則，由ROOT(T1)

對應(yīng)得到Node(root)；由(t11,t12,…,t1m)

對應(yīng)得到LBT；由(T2,T3,…,Tn)

對應(yīng)得到RBT。第一百零四頁，共一百三十九頁，編輯于2023年，星期五105由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為：若B=Φ，則F=Φ；否則，由Node(root)

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

)；由LBT

對應(yīng)得到(t11,t12,…，t1m)；由RBT

對應(yīng)得到(T2,T3,…,Tn)。第一百零五頁，共一百三十九頁，編輯于2023年，星期五106BCDEFGHIJKLBCDEFKLGHIJ第一百零六頁，共一百三十九頁，編輯于2023年，星期五107

由此，樹的各種操作均可對應(yīng)二叉樹的操作來完成。

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

左是孩子，右是兄弟。第一百零七頁，共一百三十九頁，編輯于2023年，星期五1086.7樹和森林的遍歷第一百零八頁，共一百三十九頁，編輯于2023年，星期五109一、樹的遍歷二、森林的遍歷第一百零九頁，共一百三十九頁，編輯于2023年，星期五110樹的遍歷可有三條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:

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

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

若樹不空，則自上而下自左至右訪問樹中每個結(jié)點(diǎn)。第一百一十頁，共一百三十九頁，編輯于2023年，星期五111ABCDEFGHIJK

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

后根遍歷時頂點(diǎn)的訪問次序：EFBCIJKHGDA

層次遍歷時頂點(diǎn)的訪問次序：ABCDEFGHIJK第一百一十一頁，共一百三十九頁，編輯于2023年，星期五112

BCDEFGHIJK1．森林中第一棵樹的根結(jié)點(diǎn)；2．森林中第一棵樹的子樹森林；3．森林中其它樹構(gòu)成的森林。森林由三部分構(gòu)成：第一百一十二頁，共一百三十九頁，編輯于2023年，星期五1131.先序遍歷森林的遍歷

若森林不空，則訪問森林中第一棵樹的根結(jié)點(diǎn)；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。即：依次從左至右對森林中的每一棵樹進(jìn)行先根遍歷。第一百一十三頁，共一百三十九頁，編輯于2023年，星期五114２．中序遍歷

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

余樹構(gòu)成的森林。即：依次從左至右對森林中的每一棵樹進(jìn)行后根遍歷。第一百一十四頁，共一百三十九頁，編輯于2023年，星期五115

樹的遍歷和二叉樹遍歷的對應(yīng)關(guān)系？先根遍歷后根遍歷樹二叉樹森林先序遍歷先序遍歷中序遍歷中序遍歷第一百一十五頁，共一百三十九頁，編輯于2023年，星期五1166.8哈夫曼樹與

哈夫曼編碼

最優(yōu)樹的定義

如何構(gòu)造最優(yōu)樹

哈夫曼編碼

第一百一十六頁，共一百三十九頁，編輯于2023年，星期五117

一、最優(yōu)樹的定義樹的路徑長度定義為：

根結(jié)點(diǎn)到每個結(jié)點(diǎn)的路徑長度之和。

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

從樹中一結(jié)點(diǎn)到另一結(jié)點(diǎn)的路徑上分支的數(shù)目。第一百一十七頁，共一百三十九頁，編輯于2023年，星期五118

樹的帶權(quán)路徑長度定義為：

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

WPL(T)=wklk(對所有葉子結(jié)點(diǎn))。

在所有含n個葉子結(jié)點(diǎn)、并帶相同權(quán)值的m叉樹中，必存在一棵其帶權(quán)路徑長度取最小值的樹，稱為“最優(yōu)樹”。例如：第一百一十八頁，共一百三十九頁，編輯于2023年，星期五11922475499WPL(T)=72+52+23+43+92=60WPL(T)=72+91+53+24+44=6257第一百一十九頁，共一百三十九頁，編輯于2023年，星期五12024579WPL(T)=92+72+52+23+43=60第一百二十頁，共一百三十九頁，編輯于2023年，星期五121

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

F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個帶權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹為空樹；二、如何構(gòu)造最優(yōu)樹(1)(哈夫曼算法)以二叉樹為例：第一百二十一頁，共一百三十九頁，編輯于2023年，星期五122

在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；(2)第一百二十二頁，共一百三十九頁，編輯于2023年，星期五123

從F中刪去這兩棵樹，同時加入剛生成的新樹；

重復(fù)

(2)

和

(3)

兩步，直至F中只含一棵樹為止。(3)(4)約定：為了保證得到的哈夫曼樹結(jié)構(gòu)盡量唯一，約定每個結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)權(quán)值小于等于右子樹根結(jié)點(diǎn)的權(quán)值。第一百二十三頁，共一百三十九頁，編輯于2023年，星期五1249例如:已知權(quán)值W={5,6,2,9,7}562752769767139527第一百二十四頁，共一百三十九頁，編輯于2023年，星期五1256713952795271667132900001111000111100101第一百二十五頁，共一百三十九頁，編輯于2023年，星期五126哈夫曼編碼假設(shè)我們發(fā)送的電文為“ABACCD”,它只有四個字符，只需要2位二進(jìn)制編碼

A---00B---01C---10D---11發(fā)送電文的序列為000100101011

在傳送電文時，要求總長度盡量短，因此出現(xiàn)次數(shù)多的字符適用短的編碼。

A---0B---00C---1D---11發(fā)送電文的序列為00001111(可以解釋為AAAACCCC,AABDD,BBCCCC…….)我們必須使用前綴編碼第一百二十六頁，共一百三十九頁，編輯于2023年，星期五127前綴編碼：任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。如：ABCD四個字符的使用率由高到低，編碼為A---0B---10C---110D---111做法：以字符概率作為葉子結(jié)點(diǎn)，構(gòu)造二叉樹，左分支標(biāo)0；右分支標(biāo)1；構(gòu)成編碼一定是前綴編碼。

利用哈夫曼樹可以構(gòu)造一種不等長的二進(jìn)制編碼，并且構(gòu)造所得的哈夫曼編碼是一