數(shù)據(jù)結(jié)構(gòu)第六章.ppt

1、數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容,1,第6章 樹和二叉樹（ Tree 且前9層總結(jié)點(diǎn)數(shù)為29-1=511 (完全二叉樹的前k-1層肯定是滿的) 所以末層葉子數(shù)為1000-511=489個(gè)。,24,請(qǐng)注意葉子結(jié)點(diǎn)總數(shù)末層葉子數(shù)！ 還應(yīng)當(dāng)加上第k-1層（靠右邊）的0度結(jié)點(diǎn)個(gè)數(shù)。 分析：末層的489個(gè)葉子只占據(jù)了上層的245個(gè)結(jié)點(diǎn)（489/2 ) 上層（k=9)右邊的0度結(jié)點(diǎn)數(shù)還有29-1-245=11個(gè)！,另一法：可先求2度結(jié)點(diǎn)數(shù),再由此得到葉子總數(shù)。 首先，k-2層的28-1（255）個(gè)結(jié)點(diǎn)肯定都是2度的（完全二叉） 另外，末層葉子（剛才已求出為489）所對(duì)應(yīng)的雙親也是度2， （共有489/2244個(gè)）。 所

2、以，全部2度結(jié)點(diǎn)數(shù)為255(k-2層)244(k-1層)=499個(gè)； 總?cè)~子數(shù)2度結(jié)點(diǎn)數(shù)1=500個(gè)。,第i層上的滿結(jié)點(diǎn)數(shù)為2i-1,所以， 全部葉子數(shù)489(末層)11(k-1層)=500個(gè)。 度為2的結(jié)點(diǎn)葉子總數(shù)1=499個(gè)。,3. 二叉樹的存儲(chǔ)結(jié)構(gòu),25,一、順序存儲(chǔ)結(jié)構(gòu) 按二叉樹的結(jié)點(diǎn)“自上而下、從左至右”編號(hào)，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)。,A B C D E F G H I,問：順序存儲(chǔ)后能否復(fù)原成唯一對(duì)應(yīng)的二叉樹形狀？ 答：若是完全/滿二叉樹則可以做到唯一復(fù)原。 而且有規(guī)律：下標(biāo)值為i的雙親，其左孩子的下標(biāo)值必為2i，其右孩子的下標(biāo)值必為2i1（即性質(zhì)5） 例如，對(duì)應(yīng)2的兩個(gè)孩子必為

3、4和5,即B的左孩子必是D,右孩子必為E。,T0一般不用,討論：不是完全二叉樹怎么辦？,26,答：一律轉(zhuǎn)為完全二叉樹！ 方法很簡(jiǎn)單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。,A B C D E,缺點(diǎn)：浪費(fèi)空間；插入、刪除不便,二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用二叉鏈表即可方便表示。,27,二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義： typedef struct node *tree_pointer; typedef struct node int data; tree_pointer left_child, right_child; node;,一般從根結(jié)點(diǎn)開始存儲(chǔ)。（相應(yīng)地，訪問樹中結(jié)點(diǎn)時(shí)也只能從根開始） 注：如果需要倒

4、查某結(jié)點(diǎn)的雙親，可以再增加一個(gè)雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。,例：,28,6.3 遍歷二叉樹和線索二叉樹,29,一、遍歷二叉樹（Traversing Binary Tree）,遍歷定義指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)（又稱周游）。 遍歷用途它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。 遍歷方法牢記一種約定，對(duì)每個(gè)結(jié)點(diǎn)的查看都是“先左后右” 。,30,遍歷規(guī)則,二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、 L、R D、 L、R的組合定義了六種可能的遍歷方案： LDR, LRD, DLR, DRL, RDL, RLD 若限定先左后右，則有三種

5、實(shí)現(xiàn)方案： DLR LDR LRD 先 (根)序遍歷 中 (根)序遍歷 后(根)序遍歷 注：“先、中、后”的意思是指訪問的結(jié)點(diǎn)D是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。,例1：,31,先序遍歷的結(jié)果是： 中序遍歷的結(jié)果是： 后序遍歷的結(jié)果是：,A B D E C D B E A C D E B C A,口訣： DLR先序遍歷，即先根再左再右 LDR中序遍歷，即先左再根再右 LRD后序遍歷，即先左再右再根,例2：用二叉樹表示算術(shù)表達(dá)式,32,先序遍歷 + * * / A B C D E 前綴表達(dá)式 中序遍歷 A / B * C * D + E 中綴表達(dá)式 后序遍歷 A B / C * D * E + 后

6、綴表達(dá)式 層序遍歷 + * E * D / C A B,遍歷的算法實(shí)現(xiàn)：,33,回憶1：二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義： typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode,*BitTree;,34,1）先序遍歷二叉樹 算法思想: 若二叉樹非空，則： 1）訪問根結(jié)點(diǎn) 2）先序遍歷左子樹 3）先序遍歷右子樹,算法描述: void Preorder (BiTree bt) /bt為根結(jié)點(diǎn)指針 if( bt) /根非空 visit (bt-data)； Preorder (bt-lchild) ;

7、Preorder (bt-rchild) ; ,二叉樹的遍歷,1）中序遍歷二叉樹 算法思想: 若二叉樹非空，則： 1）中序遍歷左子樹 2）訪問根結(jié)點(diǎn) 3）中序遍歷右子樹,算法描述: void Inorder (BiTree bt) /bt為根結(jié)點(diǎn)指針 if( bt) /根非空 Inorder (bt-lchild) ; visit (bt-data)； Inorder (bt-rchild) ; ,36,2）后序遍歷二叉樹 算法思想: 若二叉樹非空，則： 1）后序遍歷左子樹 2）后序遍歷右子樹 3）訪問根結(jié)點(diǎn),算法描述: void Postorder (BiTree bt) /bt為根結(jié)點(diǎn)指針

8、 if( bt) /根非空 Postorder (bt-lchild) ; Postorder (bt-rchild) ; visit (bt -data)； ,對(duì)遍歷的分析：,37,1. 從前面的三種遍歷算法可以知道：如果將print語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時(shí)機(jī)不同。,從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑 上，每個(gè)結(jié)點(diǎn)經(jīng)過3次。,第1次經(jīng)過時(shí)訪問先序遍歷 第2次經(jīng)過時(shí)訪問中序遍歷 第3次經(jīng)過時(shí)訪問后序遍歷,2. 二叉樹遍歷的時(shí)間效率和空間效率 時(shí)間效率:O(n) /每個(gè)結(jié)點(diǎn)只訪問一次 空間效率:O(n) /棧占用的最大輔助

9、空間 （精確值：樹深為k的遞歸遍歷需要k+1個(gè)輔助單元！）,38,知識(shí)回顧： （1）二叉樹的存儲(chǔ)： 順序存儲(chǔ)方式： 完全二叉樹 滿二叉樹 一般樹補(bǔ)充成的完全二叉樹或滿二叉樹 鏈?zhǔn)酱鎯?chǔ)方式：適用于各種樹 （2）二叉樹的遍歷： 先序遍歷、中序遍歷、后序遍歷、層序遍歷,39,A,B,J,I,D,C,G,F,E,H,1、先序遍歷的結(jié)果為：,2、中序遍歷的結(jié)果為：,3、后序遍歷的結(jié)果為：,A B D H E C F I G J,D H B E A F I C J G,H D E B I F J G C,特點(diǎn)：先訪問根， 再遍歷左子樹， 再遍歷右子樹,特點(diǎn)：先遍歷左子樹， 再訪問根， 再遍歷右子樹,特點(diǎn)：

10、 先遍歷左子樹， 再遍歷右子樹 最后訪問根，,注：要實(shí)現(xiàn)遍歷運(yùn)算必須先把二叉樹存入機(jī)內(nèi)。,40,思路：利用前序遍歷來建樹 （結(jié)點(diǎn)值陸續(xù)從鍵盤輸入，用DLR為宜） Status createBiTree( BiTree ,怎樣建樹？見教材P131程序。,例：編寫遞歸算法，計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。,41,思路：輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計(jì)并打印出來。,DLR(BiTree *root) if ( root!=NULL ) if(!root-lchild /遞歸遍歷右子樹，直到葉子處； ,習(xí)題討論：,42,1. 求二叉樹深度，或從x結(jié)點(diǎn)開始的子

11、樹深度。 算法思路：只查各結(jié)點(diǎn)后繼鏈表指針，若左(右)孩子的左(右)指針非空，則層次數(shù)加1；否則函數(shù)返回。,Height=max(hl,hr)+1,43,后序遍歷求二叉樹的高度遞歸算法： Int PostTreeDepth(BiTree bt) int hl,hr,max; if(bt!=NULL) hl=PostTreeDepth（bt-Lchild); /求左子樹的深度 hr=PostTreeDepth(bt-Rchild); /求右子樹的深度 max=hlhr?hl:hr; /*得到左、右子樹深度較大者*/ return (max+1); /*返回樹的深度*/ else return 0

12、; ,44,2. 按層次輸出二叉樹中所有結(jié)點(diǎn)。 算法思路：既然要求從上到下，從左到右，則利用隊(duì)列存放各子樹結(jié)點(diǎn)的指針是個(gè)好辦法，而不必拘泥于遞歸算法。 技巧：當(dāng)根結(jié)點(diǎn)出隊(duì)后，令其左、右孩子結(jié)點(diǎn)入隊(duì)，而左孩子出隊(duì)時(shí)又令它的左右孩子結(jié)點(diǎn)入隊(duì)，由此便可產(chǎn)生按層次輸出的效果。,Void Layout(BiTree root) EnQueue(s,root); While(!QueueEmpty(s) DeQueue(s,p); printf(“%c”,s-data); EnQueue(s,p-lchild); EnQueue(s,p-rchild); ,6.3.3 遍歷的非遞歸(迭代)算法以中序遍歷,

13、45,算法思路：若不用遞歸，則要實(shí)現(xiàn)二叉樹遍歷的“嵌套”規(guī)則，必用堆棧?？芍苯佑脀hile語句和push/pop操作。參見教材P130-131程序。,在中序遍歷中，我們是通過順著左子樹的根直走到最左端，然后訪問最左端元素，遍歷右，再返回上一層，訪問結(jié)點(diǎn)，遍歷右，然后再訪問上一層，這樣又順著左子樹的根回到A。 在遞歸調(diào)用中，返回上一層的操作是通過調(diào)用函數(shù)執(zhí)行結(jié)束自然返回上一層的。如果不用遞歸，如何返回上一層。 先從A走到F，在從F返回到A，最后走到的先訪問，所以可以用棧。 把根和左子樹的根全部入棧 然后判斷是否有右子樹，如果有，則遍歷右子樹，,46,知識(shí)回顧：,1、按層遍歷,Void Layou

14、t(BiTree root) EnQueue(s,root); While(!QueueEmpty(s) DeQueue(s,p); printf(“%c”,root-data); EnQueue(s,p-lchild); EnQueue(s,p-rchild); ,47,2、非遞歸中序遍歷,首先走到最左邊（肯定沒有左子樹） 接著訪問根節(jié)點(diǎn) 再非遞歸中序遍歷右子樹,Status NoInOrderTraverse(BiTree T) InitStack( ,48,2、非遞歸先序遍歷,Status NoInOrderTraverse(BiTree T) InitStack( ,49,2、非遞歸后

15、序遍歷,Status NoPostTraverse(BiTree T) InitStack( ,50,知識(shí)回顧：,二叉樹的建立 二叉樹的應(yīng)用： （1）求二叉樹葉子節(jié)點(diǎn)的個(gè)數(shù) （2）求二叉樹的深度 非遞歸遍歷二叉樹 （1）層序遍歷二叉樹 （2）非遞歸先序遍歷二叉樹 （3）非遞歸中序遍歷二叉樹 （4）非遞歸后序遍歷二叉樹,特別討論：若已知先序/后序遍歷結(jié)果和中序遍歷結(jié)果，能否“恢復(fù)”出二叉樹？,證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。,51,例：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG 和 DECBHGFA，請(qǐng)畫出這棵二叉樹。 分析： 由后序遍歷特征，根結(jié)點(diǎn)必在

16、后序序列尾部（即A）； 由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹子孫（即BDCE），其右部必全部是右子樹子孫（即FHG）； 繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。,中序遍歷：B D C E A F H G后序遍歷：D E C B H G F A,52,（B D C E）,（ F H G）,A,B,F,（D C E）,（ H G）,C,D E,G,H,A,B,B,F,F,2020/9/1,53,6.3.2 線索二叉樹 問題的提出：通過遍歷二叉樹可得到結(jié)點(diǎn)的一個(gè)線性序列，在線性序列中，很容易求得某個(gè)結(jié)點(diǎn)的直接前驅(qū)和后繼。

17、,例如中序遍歷結(jié)果：B D C E A F H G，實(shí)際上已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！,但是在二叉樹上只能找到結(jié)點(diǎn)的左孩子、右孩子，結(jié)點(diǎn)的前驅(qū)和后繼只有在遍歷過程中才能得到，那么，如何保存遍歷二叉樹后動(dòng)態(tài)得到的線性序列，以便快速找到某個(gè)結(jié)點(diǎn)的直接前驅(qū)和后繼？,增加兩個(gè)標(biāo)志域，一個(gè)指向前驅(qū)、一個(gè)指向后繼。這樣使結(jié)構(gòu)的存儲(chǔ)密度大大降低。,54,置空,置空,置空,置空,55,2. 分析： n個(gè)結(jié)點(diǎn)有n-1個(gè)前驅(qū)和n-1個(gè)后繼； 一共有2n個(gè)鏈域，其中：n+1個(gè)空鏈域，n-1個(gè)指針域； 因此, 可以用空鏈域來存放結(jié)點(diǎn)的前驅(qū)和后繼。 線索二叉樹就是利用n+1個(gè)空鏈域來存放結(jié)點(diǎn)的前

18、驅(qū)和后繼結(jié)點(diǎn)的信息。 3. 線索二叉樹： 有效利用二叉鏈表中空的存儲(chǔ)空間，指定原有的孩子指針為空的域來存放指向前驅(qū)和后繼的信息，這樣的指針被稱為“線索”。加線索的過程稱為線索化，由此得到的二叉樹稱作線索二叉樹。 (1),規(guī) 定：,1）若結(jié)點(diǎn)有左子樹，則lchild指向其左孩子； 否則， lchild指向其直接前驅(qū)(即線索)；,2）若結(jié)點(diǎn)有右子樹，則rchild指向其右孩子； 否則， rchild指向其直接后繼(即線索) 。,56,為了避免混淆，增加兩個(gè)標(biāo)志域，如下圖所示：,約定:,當(dāng)Tag域?yàn)?時(shí),表示正常情況;,當(dāng)Tag域?yàn)?時(shí),表示線索情況.,注：在線索化二叉樹中，并不是每個(gè)結(jié)點(diǎn)都能直接找

19、到其后繼的，當(dāng)標(biāo)志為0時(shí)，則需要通過一定運(yùn)算才能找到它的后繼。,線索鏈表：用這種結(jié)點(diǎn)結(jié)構(gòu)所構(gòu)成的二叉鏈表 線索：指向結(jié)點(diǎn)前驅(qū)和后繼的指針 線索二叉樹：加上線索的二叉樹（圖形式樣） 線索化：對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程,2020/9/1,57,按中序遍歷得到的線索二叉樹稱為中序線索二叉樹； 按先序遍歷得到的線索二叉樹稱為先序線索二叉樹； 按后序遍歷得到的線索二叉樹稱為后序線索二叉樹；,例2：畫出以下二叉樹對(duì)應(yīng)的中序線索二叉樹。,58,懸空？,懸空？,解：該二叉樹中序遍歷結(jié)果為: H, D, I, B, E, A, F, C, G 所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：,為避免懸空態(tài)，

20、應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn),59,對(duì)應(yīng)的中序線索二叉樹存儲(chǔ)結(jié)構(gòu)如圖所示：,注：此圖中序遍歷結(jié)果為: H, D, I, B, E, A, F, C, G,60,（2）整體結(jié)構(gòu) 增設(shè)一個(gè)頭結(jié)點(diǎn)，令其lchild指向二叉樹的根結(jié)點(diǎn)ltag=0、rtag=1； 并將該結(jié)點(diǎn)作為遍歷訪問的第一個(gè)結(jié)點(diǎn)的前驅(qū)和最后一個(gè)結(jié)點(diǎn)的后繼；最后用頭指針指示該頭結(jié)點(diǎn)。,4 給定如圖所示二叉樹T，請(qǐng)畫出與其對(duì)應(yīng)的中序線索二叉樹。,61,解:因?yàn)橹行虮闅v序列是：55 40 25 60 28 08 33 54 對(duì)應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹中添加虛線。,62,typedef struct BiThrNode TElemType

21、 data; struct BiThrNode *lchild, *rchild; / 左右指針 PointerThr LTag, RTag; / 左右標(biāo)志 BiThrNode, *BiThrTree;,線索鏈表的類型描述：,typedef enum Link, Thread PointerThr; / Link=0:指針，Thread=1:線索,2. 線索二叉樹的生成,63,線索化過程就是在遍歷過程中修改空指針的過程： 將空的lchild改為結(jié)點(diǎn)的直接前驅(qū)； 將空的rchild改為結(jié)點(diǎn)的直接后繼。,非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為“正常情況”）,目的：在依某種順序遍歷二叉樹時(shí)修改空指針，添

22、加前驅(qū)或后繼。,注解：為方便添加結(jié)點(diǎn)的前驅(qū)或后繼，需要設(shè)置兩個(gè)指針： p指針當(dāng)前結(jié)點(diǎn)之指針； pre指針前驅(qū)結(jié)點(diǎn)之指針。,技巧：當(dāng)結(jié)點(diǎn)p的左/右域?yàn)榭諘r(shí)，只改寫它的左域（裝入前驅(qū)pre）, 而其右域（后繼）留給下一結(jié)點(diǎn)來填寫。 或者說，當(dāng)前結(jié)點(diǎn)的指針p應(yīng)當(dāng)送到前驅(qū)結(jié)點(diǎn)的空右域中。,若p-lchildNULL,則p-Ltag=1;p-lchildpre; /p的前驅(qū)結(jié)點(diǎn)指針pre存入左空域 若pre-rchildNULL, 則pre-Rtag1;pre-rchild=p; /p存入其前驅(qū)結(jié)點(diǎn)pre的右空域,線索二叉樹的生成算法,64,頭結(jié)點(diǎn),0,1,pre,pre,p,pre,p,1,65,vo

23、id InThreading(BiThrTree p) if (p) /對(duì)以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,66,Status InOrderThrea

24、ding(BiThrTree / InOrderThreading,67,3. 線索二叉樹的遍歷,理論上，只要找到序列中的第一個(gè)結(jié)點(diǎn)，然后依次訪問結(jié)點(diǎn)的后繼直到后繼為空時(shí)結(jié)束。,但是，在線索化二叉樹中，并不是每個(gè)結(jié)點(diǎn)都能直接找到其后繼的，當(dāng)標(biāo)志為0時(shí)，R_child=右孩子地址指針，并非后繼！需要通過一定運(yùn)算才能找到它的后繼。,以中序線索二叉樹為例： 對(duì)葉子結(jié)點(diǎn)（RTag=1），直接后繼指針就在其rchild域內(nèi)； 對(duì)其他結(jié)點(diǎn)（RTag=0），直接后繼是其右子樹最左下的結(jié)點(diǎn)； （因?yàn)橹行虮闅v規(guī)則是LDR，先左再根再右）,線索二叉樹的中序遍歷算法（參見教材P134）,68,程序注解 (非遞歸，不

25、用棧）： P=T-lchild; /從頭結(jié)點(diǎn)進(jìn)入到根結(jié)點(diǎn)； while( p!=T) while (p-LTag=link) p=p-lchild; /先找到中序遍歷起點(diǎn) if (!visit(p-data) return ERROR; /若起點(diǎn)值為空則出錯(cuò)告警 while (p-RTag=Thread ) p=p-rchild; Visit(p-data); /若有后繼標(biāo)志，則直接提取p-rchild中線索并訪問后繼結(jié)點(diǎn)； p=p-rchild; /當(dāng)前結(jié)點(diǎn)右域不空或已經(jīng)找好了后則一律從結(jié)點(diǎn)的右子樹開始重復(fù)的全部過程。 return OK;,LTag=0,RTag=1,6.4 樹和森林,69

26、,1. 樹和森林與二叉樹的轉(zhuǎn)換 2. 樹和森林的存儲(chǔ)方式 3. 樹和森林的遍歷,70,如何存儲(chǔ)一棵樹呢？,71,利用除根結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)只有唯一的雙親的性質(zhì)，以一組連續(xù)的空間存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示域指示其雙親結(jié)點(diǎn)在存儲(chǔ)空間中的位置。,6.4 樹的存儲(chǔ)結(jié)構(gòu) 一、雙親表示法,#define MAX_TREE_SIZE 100 結(jié)點(diǎn)結(jié)構(gòu)： Typedef struct PTNode Elem data; int parent; PTNode;,Data parent,Typedef struct PTNode nodesMAX_TRee_size; int r,n; ,6 .4 樹

27、的存儲(chǔ)結(jié)構(gòu),72,6,H,6,G,3,F,1,E,1,D,0,C,0,B,0,A,-1,R,K,6,0 1 2 3 4 5 6 7 8 9,R=0 N=10,73,特點(diǎn)： 1）求結(jié)點(diǎn)的雙親操作可以在常量時(shí)間內(nèi)實(shí)現(xiàn)； 2）求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)向量。,74,二、孩子表示法,孩子結(jié)點(diǎn)： Typedef struct CTNode int child; struct CTNode *next; *childPtr;,雙親結(jié)點(diǎn): Typedef struct Elem data; childPtr firstchild; CTBox;,75,樹結(jié)構(gòu)： Typedef struct CTBox no

28、desMAX_TREE_SIZE; int n,r; Ctree;,76,F,E,B,C,A,D,G,R=0 N=7,0 1 2 3 4 5 6,A B C D E F G,1,2,3,4,5,6,-1,0,0,0,2,2,5,77,三、樹的二叉鏈表 （孩子-兄弟）存儲(chǔ)表示法 typedef struct CSNode Elem data; struct CSNode *firstchild,*nextsibling; CSNode,*CSTree;,78,F,E,B,C,A,D,G,1. 樹和森林與二叉樹的轉(zhuǎn)換,79,轉(zhuǎn)換步驟： step1: 將樹中同一結(jié)點(diǎn)的兄弟相連; step2: 保留結(jié)

29、點(diǎn)的最左孩子連線，刪除其它孩子連線； step3: 將同一孩子的連線繞左孩子旋轉(zhuǎn)45度角。,加線,抹線,旋轉(zhuǎn),討論1：樹如何轉(zhuǎn)為二叉樹？,樹轉(zhuǎn)二叉樹舉例：,80,方法：加線抹線旋轉(zhuǎn),兄弟相連,長(zhǎng)兄為父,孩子靠左,根結(jié)點(diǎn)肯定沒有右孩子！,討論2：二叉樹怎樣還原為樹？,81,要點(diǎn)：把所有右孩子變?yōu)樾值埽?82,法一： 各森林先各自轉(zhuǎn)為二叉樹； 依次連到前一個(gè)二叉樹的右子樹上。,討論3：森林如何轉(zhuǎn)為二叉樹？,法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹,（參見教材P138圖6.17，兩種方法都有轉(zhuǎn)換示意圖）,森林轉(zhuǎn)二叉樹舉例：（法二）,83,兄弟相連 長(zhǎng)兄為父 孩子靠左 頭根為根,A,討論4：二叉樹如何還原為

30、森林？,84,要點(diǎn)：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值?85,樹的遍歷可有三條搜索路徑： 先根序（次序）遍歷 若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。 后根（次序）遍歷 若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。 按層次遍歷 若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。,86,先根遍歷時(shí)頂點(diǎn)的訪問次序： A B E F C D G H I J K 后根遍歷時(shí)頂點(diǎn)的訪問次序： E F B C I J K H G D A 層序遍歷時(shí)頂點(diǎn)的訪問次序： A B C D E F G H I J K,森林的遍歷,87,先序遍歷 若森林為空，返回； 訪問森林中第一棵樹的根結(jié)點(diǎn)

31、； 先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林； 先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 中序遍歷 若森林為空，返回； 中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林； 訪問第一棵樹的根結(jié)點(diǎn)； 中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。,88,A,B,C,D,E,F,G,H,K,I,L,J,6.5 Huffman樹及其應(yīng)用,89,路 徑： 路徑長(zhǎng)度： 樹的路徑長(zhǎng)度： 帶權(quán)路徑長(zhǎng)度： 樹的帶權(quán)路徑長(zhǎng)度： 霍 夫 曼 樹：,一、最優(yōu)二叉樹（霍夫曼樹）,由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成,路徑上的分支數(shù)目,從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。,結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積,預(yù)備知識(shí)：若干術(shù)語,樹中所有葉子

32、結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和,帶權(quán)路徑長(zhǎng)度最小的樹。,ae的路徑長(zhǎng)度,樹長(zhǎng)度,2,10,Huffman樹簡(jiǎn)介：,90,樹的帶權(quán)路徑長(zhǎng)度如何計(jì)算？,經(jīng)典之例：,WPL=36,WPL=46,WPL= 35,哈夫曼樹則是：WPL 最小的樹。,Huffman樹,Weighted Path Length,構(gòu)造霍夫曼樹的基本思想：,91,(1) 由給定的 n 個(gè)權(quán)值w0, w1, w2, , wn-1，構(gòu)造具有 n 棵擴(kuò)充二叉樹的森林F = T0, T1, T2, , Tn-1 ，其中每一棵擴(kuò)充二叉樹 Ti 只有一個(gè)帶有權(quán)值 wi 的根結(jié)點(diǎn)，其左、右子樹均為空。 (2) 重復(fù)以下步驟, 直到 F 中僅剩下一棵樹

33、為止： 在 F 中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。 在 F 中刪去這兩棵二叉樹。 把新的二叉樹加入 F。,構(gòu)造Huffman樹的步驟（即Huffman算法）：,權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑。,先舉例！,構(gòu)造Huffman樹的步驟：,92,操作要點(diǎn)：對(duì)權(quán)值的合并、刪除與替換 在權(quán)值集合7,5,2,4中，總是合并當(dāng)前值最小的兩個(gè)權(quán),注：方框表示外結(jié)點(diǎn)（葉子，字符對(duì)應(yīng)的權(quán)值）， 圓框表示內(nèi)結(jié)點(diǎn)（合并后的權(quán)值）。,6.2.2 赫夫曼編碼,93,例2：設(shè)有4個(gè)字符d,i,a,n，出現(xiàn)的頻度

34、分別為7,5,2, 4，怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？,法1：等長(zhǎng)編碼。例如用二進(jìn)制編碼來實(shí)現(xiàn)。 取 d=00，i=01，a=10，n=11,法2：不等長(zhǎng)編碼，例如用前綴編碼來實(shí)現(xiàn)。 取 d=0; i=10, a=110, n=111,最快的編碼是哪個(gè)？,是非等長(zhǎng)的前綴編碼！,任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴,約定： 左分支表示0 右分支表示1 則從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上分支字符組成的字符串作為該葉子的編碼。,94,如何得到電文長(zhǎng)度最短的二進(jìn)制前綴編碼？,若按各個(gè)字符出現(xiàn)的概率不同而給予不等長(zhǎng)編碼，可望減少總編碼長(zhǎng)度。,d,i,a,n，出現(xiàn)的頻度分別為7,5,2,4

35、,假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為wi,，其編碼長(zhǎng)度為L(zhǎng)i,電文中只有n種字符，則電文總長(zhǎng)度為,由此可見，設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼即為以n種字符出現(xiàn)的頻率作權(quán)，設(shè)計(jì)一顆赫夫曼樹的問題，由此得到的二進(jìn)制前綴編碼便稱為赫夫曼編碼。,對(duì)應(yīng)到二叉樹上，若置wi為葉子結(jié)點(diǎn)的權(quán)， Li恰為從根到葉子的路徑長(zhǎng)度。則： 恰為二叉樹上帶權(quán)路徑長(zhǎng)度。,操作要點(diǎn)：按左0右1對(duì)Huffman樹的所有分支編號(hào)！,95,Huffman編碼結(jié)果：d=0, i=10, a=110, n=111 WPL=1bit72bit5+3bit(2+4)=35,特點(diǎn)：每一碼都不是另一碼的前綴，絕不會(huì)錯(cuò)譯! 稱為前綴碼,將 Huf

36、fman樹 與 Huffman編碼 掛鉤,例2（嚴(yán)題集6.26）：假設(shè)用于通信的電文僅由8個(gè)字母 a, b, c, d, e, f, g, h 構(gòu)成，它們?cè)陔娢闹谐霈F(xiàn)的概率分別為 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10，試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。如果用07的二進(jìn)制編碼方案又如何？,96,霍夫曼編碼的基本思想是：概率大的字符用短碼，概率小的用長(zhǎng)碼。由于霍夫曼樹的WPL最小，說明編碼所需要的比特?cái)?shù)最少。這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。,解：先將概率放大100倍，以方便構(gòu)造哈夫曼樹。權(quán)值集合 w=7, 19, 2, 6, 32, 3, 21, 10， 按哈夫曼