第六章樹(shù)無(wú)答案.ppt

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

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

3、e d1=TreeDepth(子樹(shù)1); dk=TreeDepth(子樹(shù)k); d=max(d1,dk)+1; return d; int LeafCount(Tree T)/遞歸法統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù) if(T為空樹(shù))n=0; else if(T只含一個(gè)根結(jié)點(diǎn))n=1; else n=LeafCount(子樹(shù)1)+LeafCount(子樹(shù)k); return n; ,2、ADT樹(shù)的定義-邏輯結(jié)構(gòu),右例：D=A,B,M H= 數(shù)據(jù)對(duì)象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、在它的一個(gè)劃分D1Dm使得任意兩個(gè)Di與Dj不相交,且每個(gè)Dk中存在唯一元素xi使得H (3)對(duì)應(yīng)于元素集合D-root的劃分，關(guān)系集合H-, ,也存在劃分H1Hm，使得(Di,Hi)也是一個(gè)樹(shù)(root的子樹(shù)),樹(shù)的圖形表示,3、樹(shù)的相關(guān)術(shù)語(yǔ),空樹(shù) 根結(jié)點(diǎn)(可標(biāo)識(shí)一顆樹(shù)) 葉子結(jié)點(diǎn) 結(jié)點(diǎn)的子樹(shù) 樹(shù)的子樹(shù) 結(jié)點(diǎn)的度 (葉子結(jié)點(diǎn)的度為幾) 樹(shù)的度 終端結(jié)點(diǎn) 非終端(分支)結(jié)點(diǎn) 內(nèi)部結(jié)點(diǎn) 結(jié)點(diǎn)的孩子/雙親/兄弟/祖先/子孫/堂兄弟 結(jié)點(diǎn)的層次(從1始) 樹(shù)的深度、寬度 無(wú)序樹(shù) 有序樹(shù) 森林:互不相交的樹(shù)的集合 Tree=(root, F)，F(xiàn)=T1,Tm Ti=ri,Fi,RF 路徑與路徑長(zhǎng)度，如

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

6、3 1 4 后序輸出:3 2 4 1 層次輸出:1 2 4 3,2.存儲(chǔ)結(jié)構(gòu)：二叉鏈表,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree; BiTree T;/思考樹(shù)的操作?,3.1 操作：求樹(shù)深【補(bǔ)】,int TreeDepth(BiTree T)/遞歸法求樹(shù)的深度 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; /其余操作類似實(shí)現(xiàn)，務(wù)必掌握,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;,思路：如果樹(shù)為空樹(shù)則深度為0，否則，先遞歸計(jì)算出左子樹(shù)的深度，再計(jì)算出右子樹(shù)的深度，最后，樹(shù)的深度為兩子樹(shù)深度的最大值加1,3.2操作：遍歷二叉樹(shù)【P129】,先(根)序遍歷:樹(shù)空無(wú)操作，非空則先訪問(wèn)根結(jié)點(diǎn),后遞歸地先序遍歷其左子樹(shù)；再遞歸地先序遍歷其右子樹(shù)。 中(根)序遍歷:樹(shù)非空則遞歸地中序遍歷根左子樹(shù)；后訪問(wèn)根結(jié)點(diǎn),再遞歸地中序遍歷右子樹(shù)。s2-s1-s3 后(根)序遍

8、歷:樹(shù)非空則遞歸地后序遍歷左子樹(shù)；后遞歸地后序遍歷右子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)。 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é)點(diǎn) ); /s1 PreOrderTraverse(T的左子樹(shù),(*visit);/s2 PreOrderTraverse(T的右子樹(shù),(*visit);/s3 return

9、OK; /尚需具體實(shí)現(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; /只要有一次訪問(wèn)失敗則必執(zhí)行此語(yǔ)句 return OK; /樹(shù)空時(shí)返回OK ,算法思路:定義輸出函數(shù)PrintElem，調(diào)用樹(shù)的先序遍歷函

10、數(shù),并將其傳遞給先序遍歷函數(shù)中的參數(shù)visit即可,假設(shè)元素為整型,3.3 操作:二叉鏈表的先序輸出【補(bǔ)】,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 /若元素為字符型則輸入時(shí)不可隨意加空格,先序創(chuàng)建：若輸入為0則創(chuàng)建一個(gè)空樹(shù),停止。否則創(chuàng)建根結(jié)點(diǎn)，遞歸創(chuàng)建左子樹(shù)，遞歸創(chuàng)建右子樹(shù)。如120300400,3.4操作：二叉鏈表的創(chuàng)建【P131】,Status DestroyBiTree(BiTree ,算法思路：樹(shù)為空什么都不作，

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

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

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

15、素不空則出棧訪問(wèn)且右孩子入棧 ,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é),遞歸:樹(shù)空時(shí)無(wú)操作;樹(shù)不空時(shí)先遞歸訪問(wèn)左子樹(shù),中間訪問(wèn)根節(jié)點(diǎn)，最后遞歸訪問(wèn)右子樹(shù) 轉(zhuǎn)化:何時(shí)入棧？何時(shí)出棧?入棧、出棧時(shí)作什么操作 總結(jié)：設(shè)指針p指向根結(jié)點(diǎn):如果p不空,入棧,之后p指向左孩子,開(kāi)始下次循環(huán);否則p空,出棧訪

16、問(wèn),令指針指向出棧元素的右孩子,開(kāi)始下次循環(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; ,時(shí)間復(fù)雜度:每個(gè)結(jié)點(diǎn)訪問(wèn)3次,T(n)=O(n) 空間復(fù)雜度:棧空間,遍歷過(guò)程中最大

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

18、Count(子樹(shù)1)+LeafCount(子樹(shù)k); return n; ,小 結(jié),二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)、操作及先/中/后/層序遍歷,int BiTreeDepth(BiTree T)/遞歸法求樹(shù)的深度 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)建一個(gè)二叉樹(shù)的原理、測(cè)試步驟,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchil

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

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

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

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

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

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

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

26、問(wèn)的結(jié)點(diǎn),樹(shù)空則均指向頭結(jié)點(diǎn).又稱雙向線索鏈表,線索二叉樹(shù)存儲(chǔ)結(jié)構(gòu)定義：線索鏈表,線索二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)稱為線索鏈表,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、線索,操作:中序遍歷線索二叉鏈表,在線索二叉樹(shù)中添加了“前驅(qū)”和“后繼”的信息，可直接根據(jù)這些信息進(jìn)行遍歷或逆向遍歷，從而提高遍歷效率,算法思路：令p指向原樹(shù)根, 設(shè)法讓p指向樹(shù)中第一個(gè)應(yīng)訪問(wèn)的結(jié)點(diǎn)(只要左孩子不為空就令p指向其左孩子，即第一個(gè)左標(biāo)記不為L(zhǎng)ink的結(jié)點(diǎn)); 訪問(wèn)p ; 只要p-RTag=Thread則令p=p-rchild并訪問(wèn)p。否則令p指向其右子樹(shù)的根, 重復(fù)前述操作 直至遍歷完畢(p指向頭結(jié)點(diǎn)),void InOrderTraverse_Thr(BiThrTree T, Status (*visit) (TElemType e) p = T-lchild; / p指向根結(jié)

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

30、何求根、給定結(jié)點(diǎn)的雙親及孩子結(jié)點(diǎn)？ 注意靜態(tài)數(shù)組和動(dòng)態(tài)數(shù)組的區(qū)別！,孩子表示法1多重鏈表,結(jié)點(diǎn)中為其每個(gè)孩子附設(shè)一個(gè)指針.具體定義時(shí)各結(jié)點(diǎn)指針的個(gè)數(shù)可取最大,也可根據(jù)各自的度不同而不同.前者同構(gòu),實(shí)現(xiàn)簡(jiǎn)單；后者需動(dòng)態(tài)開(kāi)辟指針域,實(shí)現(xiàn)復(fù)雜但空間省,孩子表示法2孩子(雙親)鏈表表示法,鏈?zhǔn)酱鎯?chǔ)與順序存儲(chǔ)結(jié)合,將各結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)組中,每個(gè)數(shù)組元素附加一指針域指向結(jié)點(diǎn)的孩子形成的鏈表。若經(jīng)常進(jìn)行訪問(wèn)雙親結(jié)點(diǎn)的操作則可向數(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é)點(diǎn)的下標(biāo) struct CTNode* next;/指下一孩子 *ChildPtr;,孩子-兄弟表示法,鏈?zhǔn)酱鎯?chǔ),每個(gè)結(jié)點(diǎn)包括數(shù)據(jù)域和兩個(gè)指針域，左指針指向第一個(gè)孩子結(jié)點(diǎn)，右指針指向兄弟結(jié)點(diǎn).又稱二叉鏈表存儲(chǔ)法,typedef struct CSNode TElemType data; struct CSNode *firstchild, *nextsibling; CSNode, * CSTree;,樹(shù)采用孩子兄弟表示法在

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

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

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

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

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

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

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

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

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

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

42、二叉樹(shù)與赫夫曼樹(shù)？ 如何構(gòu)造赫夫曼樹(shù)？ 赫夫曼樹(shù)有何應(yīng)用？ 赫夫曼樹(shù)的實(shí)現(xiàn)及和赫夫曼編碼求取,6.6 赫夫曼樹(shù)及其應(yīng)用,設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與對(duì)應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹(shù)的“帶權(quán)”路徑長(zhǎng)度，記為：,1、什么是赫夫曼(Huffman)樹(shù),對(duì)于一組帶有確定權(quán)植的葉子結(jié)點(diǎn)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)稱為最優(yōu)二叉樹(shù)(如Huffman樹(shù)),(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)造赫夫曼樹(shù)赫夫曼算法,(1)創(chuàng)建n個(gè)根結(jié)點(diǎn),權(quán)值

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

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

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