第六章樹無答案.ppt

1、第 六 章 樹 和 二 叉 樹,第六章 樹和二叉樹,6.1 樹的定義和基本術(shù)語 6.2 二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu) 6.3 遍歷二叉樹與線索二叉樹 6.4 樹和森林 6.5樹與等價問題 6.6 赫夫曼樹及其應(yīng)用,6.1 樹的定義和基本術(shù)語,1、樹的結(jié)構(gòu)特點 結(jié)構(gòu)特點:樹是一個層次結(jié)構(gòu),“有且僅有一個根結(jié)點無前驅(qū)(第一層);有一或多個葉結(jié)點無后繼;其余結(jié)點有唯一前驅(qū)和若干后繼” 。 遞歸定義:樹由根結(jié)點(唯一)及該根結(jié)點的若干(零或多個)“子樹”組成。不含任何結(jié)點也是樹，稱為空樹,樹的圖形表示,6.1 樹的定義和基本術(shù)語,1、樹的結(jié)構(gòu)特點 結(jié)構(gòu)特點:樹是一個層次結(jié)構(gòu),“有且僅有一個根結(jié)點無前驅(qū)

2、(第一層);有一或多個葉結(jié)點無后繼(最后一層);其余結(jié)點有唯一前驅(qū)和若干后繼” 。 遞歸定義:樹(非空)由根結(jié)點(唯一)及該根結(jié)點的若干(零或多個)子樹組成?？諛洳缓魏谓Y(jié)點,樹的圖形表示,樹的操作可遞歸分解成對根結(jié)點及其各子樹(由根節(jié)點的孩子即子樹的根標(biāo)識)的操作進行,直至空.如求結(jié)點數(shù)/葉結(jié)點數(shù)/深度等,int NodeCount(Tree T)/遞歸法統(tǒng)計所有結(jié)點的個數(shù) if(T為空樹)n=0; else n=1+NodeCount(子樹1)+NodeCount(子樹k); return n; int TreeDepth(Tree T)/遞歸法求樹的深度 if(T為空樹)d=0; els

3、e d1=TreeDepth(子樹1); dk=TreeDepth(子樹k); d=max(d1,dk)+1; return d; int LeafCount(Tree T)/遞歸法統(tǒng)計葉子結(jié)點的個數(shù) if(T為空樹)n=0; else if(T只含一個根結(jié)點)n=1; else n=LeafCount(子樹1)+LeafCount(子樹k); return n; ,2、ADT樹的定義-邏輯結(jié)構(gòu),右例：D=A,B,M H= 數(shù)據(jù)對象D:若干數(shù)據(jù)元素的集合 數(shù)據(jù)關(guān)系R:若|D|=0或1則R為空, 否則R=H,H具體定義如下: (1) D中有唯一元素?zé)o前驅(qū),root (2) 若D-root非空則存

4、在它的一個劃分D1Dm使得任意兩個Di與Dj不相交,且每個Dk中存在唯一元素xi使得H (3)對應(yīng)于元素集合D-root的劃分，關(guān)系集合H-, ,也存在劃分H1Hm，使得(Di,Hi)也是一個樹(root的子樹),樹的圖形表示,3、樹的相關(guān)術(shù)語,空樹 根結(jié)點(可標(biāo)識一顆樹) 葉子結(jié)點 結(jié)點的子樹 樹的子樹 結(jié)點的度 (葉子結(jié)點的度為幾) 樹的度 終端結(jié)點 非終端(分支)結(jié)點 內(nèi)部結(jié)點 結(jié)點的孩子/雙親/兄弟/祖先/子孫/堂兄弟 結(jié)點的層次(從1始) 樹的深度、寬度 無序樹 有序樹 森林:互不相交的樹的集合 Tree=(root, F)，F(xiàn)=T1,Tm Ti=ri,Fi,RF 路徑與路徑長度，如

5、A-D-J長為2 從根結(jié)點到任意結(jié)點存在唯一路徑,樹的樹形表示,InitTree(/先序遍歷 InOrderTraverse(T, Visit();/中序遍歷 PostOrderTraverse(T, Visit();/后序遍歷 LevelOrderTraverse(T, Visit();/層次遍歷,Assign(T, else if(T不空) (*visit)( T的根結(jié)點 ); /s1 PreOrderTraverse(T的左子樹,(*visit);/s2 PreOrderTraverse(T的右子樹,(*visit);/s3 return OK ,先序輸出:1 2 3 4 中序輸出:2

6、3 1 4 后序輸出:3 2 4 1 層次輸出:1 2 4 3,2.存儲結(jié)構(gòu)：二叉鏈表,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree; BiTree T;/思考樹的操作?,3.1 操作：求樹深【補】,int TreeDepth(BiTree T)/遞歸法求樹的深度 if(T=NULL)d=0; else d1=TreeDepth(T-lchild1);d2=TreeDepth(T-rchild); if(d1d2)d=d1+1; else d=d2+1; retu

7、rn d; /其余操作類似實現(xiàn)，務(wù)必掌握,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;,思路：如果樹為空樹則深度為0，否則，先遞歸計算出左子樹的深度，再計算出右子樹的深度，最后，樹的深度為兩子樹深度的最大值加1,3.2操作：遍歷二叉樹【P129】,先(根)序遍歷:樹空無操作，非空則先訪問根結(jié)點,后遞歸地先序遍歷其左子樹；再遞歸地先序遍歷其右子樹。 中(根)序遍歷:樹非空則遞歸地中序遍歷根左子樹；后訪問根結(jié)點,再遞歸地中序遍歷右子樹。s2-s1-s3 后(根)序遍

8、歷:樹非空則遞歸地后序遍歷左子樹；后遞歸地后序遍歷右子樹，再訪問根結(jié)點。 s2-s3-s1,先序:A B C D E F G H K,中序:B D C A H G K F E,后序:D C B H K G F E A,Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType) if(!T)return OK; else if(T不空) (*visit)( T的根結(jié)點 ); /s1 PreOrderTraverse(T的左子樹,(*visit);/s2 PreOrderTraverse(T的右子樹,(*visit);/s3 return

9、OK; /尚需具體實現(xiàn), visit可能失敗，如求倒數(shù),Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType) if(T) if( (*visit)(T-data) ) /s1 if( PreOrderTraverse(T-lchild,(*visit) /s2 if( PreOrderTraverse(T-rchild,(*visit) /s3 return OK; return ERROR; /只要有一次訪問失敗則必執(zhí)行此語句 return OK; /樹空時返回OK ,算法思路:定義輸出函數(shù)PrintElem，調(diào)用樹的先序遍歷函

10、數(shù),并將其傳遞給先序遍歷函數(shù)中的參數(shù)visit即可,假設(shè)元素為整型,3.3 操作:二叉鏈表的先序輸出【補】,Typedef int TElemType; Typedef BiTree Status PrintTElem(TElemType e)printf(%d ,e);return OK; Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType) if(T) if( (*visit)(T-data) ) if( PreOrderTraverse(T-lchild,(*visit) ) if( PreOrderTraverse(T-r

11、child,(*visit) ) return OK return ERROR; else return OK; void main()BiTree T; PreOrderTraverse(T,PrintTElem); ,typedef int TElemType; Status CreateBiTree(BiTree /若元素為字符型則輸入時不可隨意加空格,先序創(chuàng)建：若輸入為0則創(chuàng)建一個空樹,停止。否則創(chuàng)建根結(jié)點，遞歸創(chuàng)建左子樹，遞歸創(chuàng)建右子樹。如120300400,3.4操作：二叉鏈表的創(chuàng)建【P131】,Status DestroyBiTree(BiTree ,算法思路：樹為空什么都不作，

12、否則，先遞歸釋放左子樹，后遞歸釋放右子樹，最后釋放根結(jié)點。,3.5操作:二叉鏈表的后序遞歸銷毀【補】,遍歷應(yīng)用:由遍歷序列確定二叉樹(P154例6-5),先序序列+中序序列:先序序列中第1個元素X為根,中序序列中唯有遍歷完X的左子樹后方訪問X,故X之前的abc必構(gòu)成X的左子樹,X之后的def必構(gòu)成X的右子樹.對于子樹類似處理,第1個在先序序列中出現(xiàn)的元素Y為該左子樹的根,中序序列中Y左側(cè)的元素構(gòu)成Y的左子樹,右側(cè)構(gòu)成右子樹,依此類推,最終可定 中序序列+后序序列:后序序列中最后一個元素為根,中序序列中該結(jié)點前的元素為左子樹,后的元素為右子樹。對于左/右子樹,最后一個在后序序列中出現(xiàn)的元素為子樹

13、的根結(jié)點,再看中序序列,依此類推 先序輸出+后序輸出不能確定.如AB和BA,先序-+1*2-34/56,中序1+2*3-4-5/6,后序1234-*+56/-,思考:何時先序與中序序列相同,后中序同、先后同如何？,遍歷應(yīng)用P129:表達式的二叉樹表示,先序:-+1*2-34/56 前綴表達式/波蘭式,中序：1+2*3-4-5/6 中綴表達式,后序:1234-*+56/- 后綴表達式/逆波蘭,對于中綴表達式(e1)OP(e2)，令根結(jié)點值為OP，左子樹為e1，右子樹e2，e1與e2遞歸。如1+2*(3-4)-5/6即( (1)+( (2)*(3-4) ) )-(5)/(6),根據(jù)后綴表達式可直接

14、求值(不用考慮優(yōu)先級)，但求后綴式過程中需用優(yōu)先級。算符優(yōu)先法實際在執(zhí)行過程中隱含形成的邏輯結(jié)構(gòu)就是一顆樹。,作業(yè),補充：編寫遞歸算法，計算二叉數(shù)結(jié)點數(shù) 42、編寫遞歸算法,計算二叉樹中葉子結(jié)點的數(shù)目 說明1：假設(shè)采用二叉鏈表存儲結(jié)構(gòu) 說明2：分三部分，存儲結(jié)構(gòu)定義+思路+代碼,中序遍歷的非遞歸描述-完全模擬,遞歸:調(diào)用遞歸函數(shù)時樹空則直接返回;樹不空先遞歸訪問左子樹,中間訪問根節(jié)點，最后遞歸訪問右子樹 轉(zhuǎn)化:何時入棧？何時出棧?入棧、出棧時作什么操作？何時結(jié)束？ 【空樹 單節(jié)點樹 普通樹】 模擬:T入棧,重復(fù)如下操作至?？眨?只要棧頂元素不為則其左孩子入棧。最后棧頂必為，出棧。若下一個棧頂元

15、素不空則出棧訪問且右孩子入棧 ,1,2,3,5,Status InOrderTraverse_NonRecur(BiTree T,Status (*visit)(ElemType) SqStack S;InitStack(S); Push(S,T); );/入棧 while(!StackEmpty(S) while(GetTop(S,p) ,中序遍歷的非遞歸描述-略加總結(jié),遞歸:樹空時無操作;樹不空時先遞歸訪問左子樹,中間訪問根節(jié)點，最后遞歸訪問右子樹 轉(zhuǎn)化:何時入棧？何時出棧?入棧、出棧時作什么操作 總結(jié)：設(shè)指針p指向根結(jié)點:如果p不空,入棧,之后p指向左孩子,開始下次循環(huán);否則p空,出棧訪

16、問,令指針指向出棧元素的右孩子,開始下次循環(huán)重復(fù)至p和?？?Status InOrderTraverse_NonRecur(BiTree T,Status (*visit)(ElemType) SqStack S;InitStack(S);BiTNode* p=T; while(p|!EmptyStack(S) if(p) Push(S,p); p=p-lchild; else Pop(S,p); if(!(*vist)(p-data)return ERROR; p=p-rchild; return OK; ,時間復(fù)雜度:每個結(jié)點訪問3次,T(n)=O(n) 空間復(fù)雜度:棧空間,遍歷過程中最大

17、棧長O(n),小 結(jié),樹的結(jié)構(gòu)特點及遞歸定義(非空樹由根結(jié)點及其子樹組成), 二叉樹的定義，對二叉樹的操作可遞歸分解成對根結(jié)點、左子樹(由根節(jié)點的左孩子標(biāo)識)、右子樹(根節(jié)點右孩子標(biāo)識)的操作進行.如求結(jié)點數(shù)/葉結(jié)點數(shù)/深度/復(fù)制/左右互換,int NodeCount(Tree T)/遞歸法統(tǒng)計所有結(jié)點的個數(shù) if(T為空樹)n=0; else n=1+NodeCount(子樹1)+NodeCount(子樹k); return n; int LeafCount(Tree T)/遞歸法統(tǒng)計葉子結(jié)點的個數(shù) if(T為空樹)n=0; else if(T只含一個根結(jié)點)n=1; else n=Leaf

18、Count(子樹1)+LeafCount(子樹k); return n; ,小 結(jié),二叉樹的二叉鏈表存儲結(jié)構(gòu)、操作及先/中/后/層序遍歷,int BiTreeDepth(BiTree T)/遞歸法求樹的深度 if(T= =NULL)d=0; else d1=TreeDepth(T-lchild1);d2=TreeDepth(T-rchild); if(d1d2)d=d1+1;else d=d2+1; return d; /注意創(chuàng)建一個二叉樹的原理、測試步驟,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchil

19、d; BiTNode, *BiTree;,6.2 二叉樹,二叉樹的定義、二叉鏈表存儲(與基本操作) 二叉樹的性質(zhì) 二叉樹的其它存儲結(jié)構(gòu),6.2.2 二叉樹的性質(zhì),性質(zhì)1: 在二叉樹的第i層上最多有2i-1個結(jié)點（i1） 性質(zhì)2: 深度為K的二叉樹最多有2K-1個結(jié)點（K1） 性質(zhì)3: 對于任意一棵二叉樹BT，如果度為0的結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則n0=n2+1。,證: 二叉樹上結(jié)點總數(shù) n = n0 + n1 + n2 二叉樹上邊的總數(shù) e = n1+2n2 根結(jié)點外每個結(jié)點都有且僅有一條邊(分支)”進入”,故e = n-1 由此n-1= n0 + n1 + n2 - 1 ，進

20、而 n0 = n2 + 1 。,滿二叉樹與完全二叉樹：,滿二叉樹：設(shè)深度為k,含2k-1個結(jié)點的二叉樹。結(jié)點數(shù)達最大,完全二叉樹：設(shè)樹中含n個結(jié)點, 它們和滿二叉樹中編號為1至n的結(jié)點位置上一一對應(yīng)(編號規(guī)則為由上到下，從左到右）。相比滿二叉樹僅少“最后的”若干個，不能少中間的,完全二叉樹特點:(1)葉子結(jié)點出現(xiàn)在最后2層或多或1層 (2)對于任意結(jié)點，若其右分支下的子孫的最大層次為L,則左分支下的子孫的最大層次為L或L+1,證:設(shè)完全二叉樹的深度為 k 則據(jù)性質(zhì)2得 2k-1 -1 2k-1 n 2k -1 2k 即 k-1 log2 n k 因為 k 只能是整數(shù)， 因此， k =log2n

21、 + 1 。,性質(zhì)4:含n個結(jié)點的完全二叉樹深度為 log2n +1 。,性質(zhì)5:若對含 n 個結(jié)點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中編號為 i 的結(jié)點：(1) 若 i=1，則該結(jié)點是二叉樹的根，無雙親，否則，編號為 i/2 的結(jié)點為其雙親結(jié)點；(2) 若 2in，則該結(jié)點無左孩子，否則，編號為 2i 的結(jié)點為其左孩子結(jié)點；(3) 若 2i+1n，則該結(jié)點無右孩子，否則，編號為2i+1 的結(jié)點為其右孩子結(jié)點。,6.2.3二叉樹的存儲結(jié)構(gòu)順序存儲,順序存儲結(jié)構(gòu),:將二叉樹映射到完全二叉樹上，不存在的結(jié)點以空標(biāo)記，之后用地址連續(xù)的存儲單元(一維數(shù)組)依次自上而

22、下、自左而右存儲完全二叉樹上的各元素.(將一般二叉樹以完全二叉樹形式存儲),最壞情況下k個結(jié)點需2k-1個單元?？臻g可能浪費，但適合完全二叉樹的存儲， 操作簡單方便,6.2.3二叉樹的存儲結(jié)構(gòu)順序存儲,順序存儲結(jié)構(gòu),用地址連續(xù)的存儲單元(一維數(shù)組)依次自上而下、自左而右直接存儲二叉樹各元素？,存儲結(jié)構(gòu)與二叉樹不一一對應(yīng)，不能唯一確定原二叉樹，故如此存儲不可！,二叉樹的存儲結(jié)構(gòu)順序存儲,順序存儲結(jié)構(gòu),:將二叉樹映射到完全二叉樹上，不存在的結(jié)點以空標(biāo)記，之后用地址連續(xù)的存儲單元(一維數(shù)組)依次自上而下、自左而右存儲完全二叉樹上的各元素.(將一般二叉樹以完全二叉樹形式存儲),最壞情況下k個結(jié)點需2k

23、-1個單元。但適合完全二叉樹的存儲，操作簡單方便,/二叉樹的靜態(tài)分配順序存儲結(jié)構(gòu) #define MAX_TREE_SIZE 100 typedef TElemType SqBiTreeMAX_TREE_SIZE; /零號元素存根結(jié)點,考慮初始化及求根/左孩子/右孩子操作,二叉樹的鏈?zhǔn)酱鎯?二叉鏈表,三叉鏈表,線索鏈表,二叉鏈表,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree; BiTree T;/如何判樹空？,求雙親結(jié)點慢,三叉鏈表,typedef struct

24、TriTNode struct TriTNode *parent; TElemType data; struct TriTNode *lchild, *rchild; TriTNode, *TriTree;,求雙親結(jié)點快但空間利用率低，兩者均不易擴展到普通樹,6.3 遍歷二叉樹和線索二叉樹,二叉樹遍歷的定義、實現(xiàn)和應(yīng)用（已講） 線索二叉樹：概念、結(jié)構(gòu)、構(gòu)造、操作實現(xiàn),6.3.2 線索鏈表,含n個結(jié)點的二叉鏈表中有2n0+n1=n+1個空鏈域,用其記錄遍歷過程中當(dāng)前結(jié)點的前驅(qū)或后繼,方案1 直觀簡單，但存儲密度低,引：遍歷二叉樹時結(jié)點訪問的先后順序信息只有在遍歷的動態(tài)過程中得到。若經(jīng)常遍歷或者要

25、求取遍歷時節(jié)點的前驅(qū)、后繼信息則應(yīng)修改二叉鏈表的結(jié)構(gòu)以保存該遍歷順序信息(線索),加上線索的二叉樹稱線索二叉樹。分先序/中序/后序線索二叉樹,線索二叉樹的結(jié)構(gòu)（中序線索二叉樹）,每個節(jié)點的基礎(chǔ)上增設(shè)兩個標(biāo)記位, 標(biāo)記位為0(Link)代表指針存儲孩子信息；標(biāo)記位為1(Thread)代表指針存儲線索信息，若是左指針則指向前驅(qū)，右指針則指向后繼,中序:B D C A H G K F E,二叉樹的線索化(人工構(gòu)造),/先寫出遍歷序列,后添加頭結(jié)點,再據(jù)序列增加線索即可,中序:B D C A H G K F E,T,增設(shè)頭結(jié)點,左標(biāo)記為Link,左指針指根結(jié)點,右標(biāo)記為Thread,右指針指向最后被訪

26、問的結(jié)點,樹空則均指向頭結(jié)點.又稱雙向線索鏈表,線索二叉樹存儲結(jié)構(gòu)定義：線索鏈表,線索二叉樹的鏈?zhǔn)酱鎯ΨQ為線索鏈表,typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; / 左右指針 PointerTag LTag, RTag; / 指針性質(zhì)Link或Thread BiThrNode, *BiThrTree;,typedef enum Link, Thread PointerTag; /指針標(biāo)記類型 /Link 0 /標(biāo)記為0代表為指向孩子的指針 /Thread 1 /標(biāo)記為1代表為指向前驅(qū)后繼的

27、線索,操作:中序遍歷線索二叉鏈表,在線索二叉樹中添加了“前驅(qū)”和“后繼”的信息，可直接根據(jù)這些信息進行遍歷或逆向遍歷，從而提高遍歷效率,算法思路：令p指向原樹根, 設(shè)法讓p指向樹中第一個應(yīng)訪問的結(jié)點(只要左孩子不為空就令p指向其左孩子，即第一個左標(biāo)記不為Link的結(jié)點); 訪問p ; 只要p-RTag=Thread則令p=p-rchild并訪問p。否則令p指向其右子樹的根, 重復(fù)前述操作 直至遍歷完畢(p指向頭結(jié)點),void InOrderTraverse_Thr(BiThrTree T, Status (*visit) (TElemType e) p = T-lchild; / p指向根結(jié)

28、點 while (p != T) / 未遍歷結(jié)束 while (p-LTag=Link) p=p-lchild; /p指向第一個待訪問結(jié)點 if (!visit(p-data) return ERROR; while(p-RTag=Thread /當(dāng)前結(jié)點右指針非線索, p指向其右子樹根 /復(fù)雜度也為O(n)，但是沒有遞歸，不需要棧,操作:中序線索二叉鏈表的構(gòu)造,思路:(1) 開辟頭結(jié)點并賦初值(2)遍歷原二叉樹, 根據(jù)其有無孩子修改標(biāo)記并適時添線索信息 (3) 最后一個結(jié)點再單獨處理,Status InOrderThreading(BiThrTree ,設(shè)函數(shù)InThreading(BiTh

29、rTree p,BiThrTree p-lchild=pre; else p-LTag=Link; if(pre-rchild=NULL)pre-RTag=Thread;pre-rchild=p; else pre-RTag=Link;,函數(shù)InThreading(BiThrTree p,BiThrTree int parent;/下標(biāo) PTNode;,typedef char TElemType; #define MAX_TREE_SIZE 100,typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; /根結(jié)點下標(biāo)和結(jié)點個數(shù) PTree;,如

30、何求根、給定結(jié)點的雙親及孩子結(jié)點？ 注意靜態(tài)數(shù)組和動態(tài)數(shù)組的區(qū)別！,孩子表示法1多重鏈表,結(jié)點中為其每個孩子附設(shè)一個指針.具體定義時各結(jié)點指針的個數(shù)可取最大,也可根據(jù)各自的度不同而不同.前者同構(gòu),實現(xiàn)簡單；后者需動態(tài)開辟指針域,實現(xiàn)復(fù)雜但空間省,孩子表示法2孩子(雙親)鏈表表示法,鏈?zhǔn)酱鎯εc順序存儲結(jié)合,將各結(jié)點存儲在一個數(shù)組中,每個數(shù)組元素附加一指針域指向結(jié)點的孩子形成的鏈表。若經(jīng)常進行訪問雙親結(jié)點的操作則可向數(shù)組元素追加雙親位置域,typedef struct TElemType data; int parent; ChildPtr firstchild; CTBox;,typedef s

31、truct CTBox nodesMAX_TREE_SIZE; int n, r; CTree;,typedef struct CTNode int Child; /孩子結(jié)點的下標(biāo) struct CTNode* next;/指下一孩子 *ChildPtr;,孩子-兄弟表示法,鏈?zhǔn)酱鎯?每個結(jié)點包括數(shù)據(jù)域和兩個指針域，左指針指向第一個孩子結(jié)點，右指針指向兄弟結(jié)點.又稱二叉鏈表存儲法,typedef struct CSNode TElemType data; struct CSNode *firstchild, *nextsibling; CSNode, * CSTree;,樹采用孩子兄弟表示法在

32、內(nèi)存中實際形成一個二叉鏈表，與二叉樹的二叉鏈表存儲結(jié)構(gòu)同構(gòu),但對指針含義的解釋不同,1.2 森林的存儲結(jié)構(gòu)補充,思路:單顆樹的二叉鏈表存儲結(jié)構(gòu)中根結(jié)點的右指針必為空,若要存儲多顆樹組成的森林，可將后一顆樹的根結(jié)點看成前一顆樹根結(jié)點的兄弟，即將后一顆樹對應(yīng)的二叉鏈表拼接到前一顆樹根結(jié)點的右指針上，這稱為森林的孩子兄弟表示法或二叉鏈表存儲法。,typedef struct CSNode TElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;,森林的該種表示法也形成一個二叉鏈表, 與樹、二叉樹的二叉鏈表存儲結(jié)

33、構(gòu)同構(gòu),但指針含義注意區(qū)分,2、樹、森林與二叉樹的轉(zhuǎn)換,以二叉鏈表存儲結(jié)構(gòu)為轉(zhuǎn)換依據(jù)，將左右指針?biāo)附Y(jié)點理解為左右孩子結(jié)點則得到二叉樹；將左指針?biāo)附Y(jié)點理解為孩子,右指針?biāo)附Y(jié)點理解為當(dāng)前結(jié)點的兄弟則得樹或森林,二叉樹與森林轉(zhuǎn)換舉例,思考:怎樣編寫程序進行森林/樹 與二叉樹之間的相互轉(zhuǎn)換？,3、樹和森林的遍歷-樹的遍歷,樹采用二叉鏈表存儲，對樹進行遍歷即對二叉鏈表進行遍歷。先序遍歷二叉鏈表（先根結(jié)點后左子樹再右子樹）,對應(yīng)到樹上是“先根,后自左到右遞歸遍歷各子樹”,稱為樹的先根序遍歷,代碼與二叉樹的先序遍歷基本同,將lchild與rchild換作firstchild和nextsibling即可

34、.寫遍歷序列也可直接根據(jù)先根規(guī)則.ABHCEFGD,H,H,樹的遍歷續(xù),對二叉鏈表進行中序遍歷(先左子樹中根再右子樹)對應(yīng)到樹上是“先從左到右各子樹,后根”,稱為樹的后根序遍歷,代碼與二叉樹的“中序”遍歷基本同,惟lchild與rchild換作firstchild和nextsibling。也可直接根據(jù)后根規(guī)則寫遍歷序列。如HBEGFCDA,H,H,先序遍歷二叉鏈表 BEFKL CG DHIJ,森林的遍歷,森林采用二叉鏈表存儲(孩子兄弟表示法),先序遍歷二叉鏈表 (先根結(jié)點后左子樹再右子樹),對應(yīng)到樹上為“從左到右依次先根遍歷各顆樹”,稱為森林的先序遍歷,代碼與二叉樹的先序遍歷基本同,惟定義中l(wèi)

35、child與rchild換作firstchild和nextsibling。寫遍歷序列也可根據(jù)“先根序”規(guī)則,中序遍歷二叉鏈表 EKLFB GC HIJD,森林采用二叉鏈表存儲(孩子兄弟表示法),對二叉鏈表“先左子樹中根再右子樹”中序遍歷,對應(yīng)到森林為“從左到右依次后根遍歷各顆樹”,稱為森林的中序遍歷，代碼與二叉樹的中序遍歷基本同,惟lchild與rchild換作firstchild和nextsibling。寫遍歷序列也可根據(jù)“后根序”規(guī)則,森林的遍歷續(xù),補：由樹的先根和后根遍歷序列確定樹,方法一(間接法，借助二叉鏈表)：樹的先根序列對應(yīng)二叉鏈表的先序序列、后根序列對應(yīng)二叉鏈表的中序序列，由先序

36、序列與中序序列可確定出二叉鏈表，再根據(jù)此二叉鏈表按照孩子兄弟表示法的含義可得此二叉鏈表對應(yīng)的樹 方法二(直接法，根據(jù)先根后根)：先根序列中第1個X一定是整顆樹的根結(jié)點,而后根序列中唯有遍歷完X的所有子樹后方訪問X,故X必然出現(xiàn)在最后；先根序列中第二個頂點必然是第一個子樹的根結(jié)點，后根序列中該結(jié)點前的結(jié)點為此子樹中各結(jié)點；除去第一顆子樹中的結(jié)點后，先根序列中第一個結(jié)點必為第二顆子樹的根結(jié)點，而后根序列中此結(jié)點前的結(jié)點構(gòu)成第二顆子樹，以此類推，最終可確定,先根:A B E F C D G H I J K,后根:E F B C I J K H G D A,補:由森林的先序和中序遍歷序列確定森林,方法

37、一(間接法，借助二叉鏈表):森林的先序序列對應(yīng)二叉鏈表的先序序列、中序序列對應(yīng)二叉鏈表的中序序列，由先序序列與中序序列可確定出二叉鏈表，再根據(jù)此二叉鏈表按照孩子兄弟表示法的含義可得此二叉鏈表對應(yīng)的森林 方法二(直接法，根據(jù)先根后根)：先序序列中第1個X一定是第一顆樹的根結(jié)點,而中序序列中在遍歷完第一顆樹的最后訪問X,故中序序列中X之前的結(jié)點構(gòu)成森林的第一顆樹，這些結(jié)點在先序和中序序列中的出現(xiàn)次序即為第一顆樹的先根序列和后根序列，根據(jù)樹的確定方法可得第一顆樹；除去第一顆樹的結(jié)點后，先序序列中余下的第一個結(jié)點為第二顆樹的根結(jié)點，中序序列中該結(jié)點前結(jié)點的構(gòu)成第二顆樹,依次類推，最終可得森林,先序:

38、BEFKLCGDHIJ,中序:EKLFBGCHIJD,int TorFDepth(CSTree F) /采用二叉鏈表存儲結(jié)構(gòu) if(!F) return 0; else h1 = TreeDepth( F-firstchild )+1; h2 = TreeDepth( F-nextsibling); ,return(max(h1, h2);,補：求樹或森林的深度的算法(類似思考求葉子數(shù)),思路:樹也是森林。對于森林而言，森林或者為空，或者分為兩部分：第一顆樹、其余樹組成的子森林。求森林的深度可以遞歸，先遞歸求第一顆樹的深度(子樹森林深度加1),后遞歸求其余樹所組成的森林的深度,作業(yè):,23 給

39、出樹的先根序列GFKDAIEBCHJ和后根序列DIAEKFCJHBG求樹 24給出森林先序和中序序列求森林ABCDEFGHIJKL； CBEFDGAJIKLH 60設(shè)計算法統(tǒng)計孩子兄弟表示的樹或森林的葉子結(jié)點數(shù)(提示：用遞歸,仿照求 森林的 深度。葉子意味著firstchild為空,注意第一棵樹的葉子數(shù)如何求),6.5樹與等價問題【自學(xué)】,問題：給定元素與關(guān)系，劃分等價類 思路：初始每個元素一個集合，根據(jù)讀入的關(guān)系進行集合的合并?；静僮靼ǘㄎ辉厮鶎偌?集合并 存儲結(jié)構(gòu):用樹表示集合,將屬于同一集合的元素存儲到一顆樹中，類似雙親表示法，定位操作只需找根，集合并變?yōu)闃涞臍w并 基本操作及其實

40、現(xiàn)：略,電報對字符進行二進制編碼,要滿足解碼唯一性且盡量短 等長編碼：每個字符的編碼長度相同。假設(shè)字符集只含有4個字符A，B，C，D，可用兩位二進制數(shù)編碼為00，01，10，11。 編碼：若現(xiàn)在有一段電文為：ABACCDA，則應(yīng)發(fā)送二進制序列：00010010101100 譯碼：當(dāng)接收方接收到這段電文后，將按兩位一段進行譯碼。 特點：這種編碼的特點是譯碼簡單且具有唯一性，但編碼長度不一定是最短的，此例總長度為14位,引：電報編碼,不等長編碼 頻度高的字符分配相對較短的編碼，頻度較低的字符分配較長的編碼。 如ABACCDA，若分別為A，B，C，D分配0，00，1，01，則上述電文編碼為00001

41、1010，長度為9，但該編碼無法正確解碼，因為無法斷定前面4個0是4個A，還是2個B，即譯碼不唯一。原因在于A的編碼是B的前綴 前綴編碼:任一字符的編碼都不是另一字符編碼的前綴,前綴編碼的設(shè)計,0 00 1 01,0 100 101 11,A B C D,00 01 10 11,A,前綴編碼對應(yīng)的二叉樹中,字符只能作為葉子結(jié)點出現(xiàn) 路徑長代表字符編碼長,葉子結(jié)點權(quán)值代表字符出現(xiàn)次數(shù),則全文編碼長度為樹的帶權(quán)路徑長度,構(gòu)造最優(yōu)的前綴編碼即構(gòu)造最優(yōu)二叉樹,如赫夫曼樹,字符的二進制編碼可借助二叉樹表示,一個字符對應(yīng)一個葉結(jié)點,根到結(jié)點的路徑代表相應(yīng)字符的編碼(向左走表0，向右走表1)。如,什么是最優(yōu)

42、二叉樹與赫夫曼樹？ 如何構(gòu)造赫夫曼樹？ 赫夫曼樹有何應(yīng)用？ 赫夫曼樹的實現(xiàn)及和赫夫曼編碼求取,6.6 赫夫曼樹及其應(yīng)用,設(shè)二叉樹具有n個帶權(quán)值的葉子結(jié)點，從根結(jié)點到各個葉子結(jié)點的路徑長度與對應(yīng)葉子結(jié)點權(quán)值的乘積之和叫做二叉樹的“帶權(quán)”路徑長度，記為：,1、什么是赫夫曼(Huffman)樹,對于一組帶有確定權(quán)植的葉子結(jié)點，帶權(quán)路徑長度最小的二叉樹稱為最優(yōu)二叉樹(如Huffman樹),(1)WPL=1*2+3*2+5*2+5*2=28 (2)WPL=1*3+3*3+5*2+5*1=27 (3)WPL=5*3+5*3+3*2+1*1=37,2、如何構(gòu)造赫夫曼樹赫夫曼算法,(1)創(chuàng)建n個根結(jié)點,權(quán)值

43、w1,w2,.,wn, 得森林T1,T2,.,Tn； (2)在森林中選取根結(jié)點權(quán)值最小的兩棵二叉樹歸并為新二叉樹，新二叉樹根結(jié)點權(quán)值為兩權(quán)值之和； (3)將新二叉樹加入森林，同時忽略被歸并的兩棵二叉樹， (4)重復(fù)（2）和（3，至森林只有一棵二叉樹。該二叉樹就是哈夫曼樹。,例如: 已知權(quán)值 W= 5, 6, 2, 9, 7 ,5,2,7,6,9,7,6,7,13,9,9,16,29,赫夫曼樹不一定唯一!,WPL=2*3+3*3+4*2+5*1=28,WPL=2*2+4*2+5*2+3*2=28,Huffman樹肯定最優(yōu),不是Huffman樹也可能最優(yōu)樹,只要權(quán)值個數(shù)(葉結(jié)點數(shù))嚴(yán)格大于1，Hu

44、ffman樹中便不存在度為1的結(jié)點。 權(quán)值個數(shù)(葉節(jié)點數(shù))為n則Huffman樹含2n-1個結(jié)點,利用赫夫曼樹設(shè)計最佳判定算法，如五級分轉(zhuǎn)換 (注意此處權(quán)值與路徑及樹的帶權(quán)路徑長度的含義),3、赫夫曼樹的應(yīng)用-最佳判定算法,Huffman樹應(yīng)用-字符編碼,赫夫曼樹對應(yīng)的編碼稱為赫夫曼編碼,是一種最優(yōu)前綴編碼,例6-2 已知某系統(tǒng)在通訊聯(lián)絡(luò)中只可能出現(xiàn)八種字符A,B,C,D,E,F,G,H, 概率如下，設(shè)計Huffman編碼 0.05, 0.29, 0.07, 0.08, 0.14, 0.23,0.03,0.11,解：設(shè)權(quán)w=5,29,7,8,14,23,3,11,分別對應(yīng)A-H，下面根據(jù)Huf

45、fman算法構(gòu)造Huffman樹,赫夫曼編碼:A0110,B10,C1110,D1111,E110,F00,G0111,H010,權(quán)w=5,29,7,8,14,23,3,11,分別對應(yīng)A-H,字符采用Unicode編碼時,一個字符占16位,如包含100個字符的文本文檔占用空間為： 100161600 位 現(xiàn)已知文中僅含ABCDEFGH八個字符,八個字符在文件中出現(xiàn)的次數(shù)分別為:5,29,7,8,14,23,3,11 如上頁構(gòu)造赫夫曼編碼: A0110,B10,C1110,D1111,E110,F00,G0111,H010 則文件占用空間為： 542927484143232113259 位,補充赫夫曼樹的應(yīng)用文件壓縮,4、Huffman樹和Huffman編碼的存儲表示,存儲結(jié)構(gòu):含n個字符則赫夫曼樹有2n-1個結(jié)點,個數(shù)固定,編碼和解碼無增刪，故赫夫曼樹采用動態(tài)分配的順序存儲結(jié)構(gòu).構(gòu)造樹時從葉子結(jié)點逐步向上走,識別字符或者說解碼時從根向下走，故結(jié)點要含雙親和左右孩子下標(biāo),當(dāng)然還要有權(quán)值,typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode; typedef HTNode *HuffmanTree; /所有字符的Huffman編碼用含n