數(shù)據(jù)結(jié)構(gòu)ppt 第6章 樹和二叉樹

1、6.1 6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語6.2 6.2 二叉樹二叉樹6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 6.4 樹和森林樹和森林6.5 6.5 樹與等價問題樹與等價問題 * * *6.6 6.6 赫夫曼樹及其應用赫夫曼樹及其應用6.7 6.7 回溯法與樹的遍歷回溯法與樹的遍歷 * * *6.8 6.8 樹的計數(shù)樹的計數(shù) * * *由一個或多個由一個或多個( (n0n0) )結(jié)點組成的有限集合結(jié)點組成的有限集合T T，有且僅有，有且僅有一一個結(jié)點稱為根個結(jié)點稱為根（rootroot），），當當n1n1時，其余的結(jié)點分為時，其余的結(jié)點分為m(m0)m(m

2、0)個個互不相交互不相交的有限集合的有限集合T1,T2T1,T2，TmTm。每個集合本身又是棵樹，。每個集合本身又是棵樹，被稱作這個根的被稱作這個根的子樹子樹 。對于一棵非空樹，每個節(jié)點可有對于一棵非空樹，每個節(jié)點可有 0 0個或個或多個多個后繼節(jié)點，后繼節(jié)點，根節(jié)點沒有前驅(qū)節(jié)點，其它節(jié)點均根節(jié)點沒有前驅(qū)節(jié)點，其它節(jié)點均有且僅有有且僅有一個前驅(qū)節(jié)點。一個前驅(qū)節(jié)點。注注1 1：過去許多書籍中都定義樹為過去許多書籍中都定義樹為n1n1，曾經(jīng)有，曾經(jīng)有“空樹不是樹空樹不是樹” 的說法，但現(xiàn)在樹的定義已修改。的說法，但現(xiàn)在樹的定義已修改。注注2 2：樹的定義具有樹的定義具有遞歸性遞歸性，即樹中還有樹。

3、，即樹中還有樹。ABCGEIDHFJMLKADT Tree 數(shù)據(jù)對象數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R:基本操作基本操作 P： ADT Tree若若D為空集，則稱為空樹；為空集，則稱為空樹；/允許允許n=0若若D中僅含一個數(shù)據(jù)元素，中僅含一個數(shù)據(jù)元素，則則R為空集為空集；其他情況下的其他情況下的R存在二元關(guān)系存在二元關(guān)系H： root 唯一，在關(guān)系唯一，在關(guān)系H下無前趨下無前趨 / 根的說明根的說明 DjDk= , H / 子樹不相交子樹不相交 ( Di, Hi ) 是一棵樹是一棵樹 / 子樹的遞歸描述子樹的遞歸描述D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。/至少有至少有1

4、5個個注：注：抽象數(shù)據(jù)類型樹的完整定義見教材抽象數(shù)據(jù)類型樹的完整定義見教材 P119P119圖形表示法圖形表示法嵌套集合表示法嵌套集合表示法廣義表表示法廣義表表示法目錄表示法目錄表示法左孩子右兄弟表示法左孩子右兄弟表示法這些表示法的示意圖這些表示法的示意圖參見教材參見教材P120P120教師教師學生學生其他人員其他人員20082008級級 20092009級級 20112011級級20122012級級機電與信息工程學院機電與信息工程學院電子系電子系計算機系計算機系自控系自控系葉子葉子根根子樹子樹即上層的那個結(jié)點即上層的那個結(jié)點(直接前驅(qū)直接前驅(qū))即下層結(jié)點的子樹的根即下層結(jié)點的子樹的根(直接后

5、繼直接后繼)同一雙親下的同層結(jié)點（孩子之間互稱兄弟）同一雙親下的同層結(jié)點（孩子之間互稱兄弟） 即雙親位于同一層的結(jié)點（但并非同一雙親）即雙親位于同一層的結(jié)點（但并非同一雙親）即從根到該結(jié)點所經(jīng)分支的所有結(jié)點即從根到該結(jié)點所經(jīng)分支的所有結(jié)點即該結(jié)點下層子樹中的任一結(jié)點即該結(jié)點下層子樹中的任一結(jié)點 根根 葉子葉子 森林森林有序樹有序樹無序樹無序樹即根結(jié)點即根結(jié)點(沒有前驅(qū)沒有前驅(qū))即終端結(jié)點即終端結(jié)點(沒有后繼沒有后繼)指指m棵不相交的樹的集合棵不相交的樹的集合 (例如刪除例如刪除A后的子樹集合后的子樹集合)雙親雙親孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孫子孫ABCGEIDHFJMLK即樹的數(shù)據(jù)元

6、素即樹的數(shù)據(jù)元素結(jié)點掛接的子樹數(shù)結(jié)點掛接的子樹數(shù)（有幾個直接后繼就是幾度，亦有幾個直接后繼就是幾度，亦稱稱“次數(shù)次數(shù)”）結(jié)點結(jié)點結(jié)點的度結(jié)點的度結(jié)點的層次結(jié)點的層次終端結(jié)點終端結(jié)點分支結(jié)點分支結(jié)點樹的度樹的度樹的深度樹的深度(或高度或高度)從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）即度為即度為0的結(jié)點，即葉子的結(jié)點，即葉子即度不為即度不為0的結(jié)點（也稱為內(nèi)部結(jié)點）的結(jié)點（也稱為內(nèi)部結(jié)點）所有結(jié)點度中的最大值（所有結(jié)點度中的最大值（Max各結(jié)點的度各結(jié)點的度）指所有結(jié)點中最大的層數(shù)（指所有結(jié)點中最大的層數(shù)（Max各結(jié)點的層次各結(jié)點的層次）右上圖中的結(jié)點數(shù)右上圖中的結(jié)

7、點數(shù) ；樹的度；樹的度 ；樹的深度；樹的深度13133 34 4ABCGEIDHFJMLK可規(guī)定為：從上至下、從左至右將樹的結(jié)點依次存入內(nèi)存。重大缺陷：復原困難（不能唯一復原就沒有實用價值）。討論：討論：樹的樹的順序存儲順序存儲方案應該怎樣制定？方案應該怎樣制定？可用多重鏈表：可用多重鏈表：一個前趨指針，一個前趨指針，n n個后繼指針。個后繼指針。問題：問題：樹中結(jié)點的結(jié)構(gòu)類型樣式該如何設(shè)計？樹中結(jié)點的結(jié)構(gòu)類型樣式該如何設(shè)計？ 即應該設(shè)計成即應該設(shè)計成“等長等長”還是還是“不等長不等長”？缺點：缺點：等長結(jié)構(gòu)太浪費（每個結(jié)點的度不一定相同）；等長結(jié)構(gòu)太浪費（每個結(jié)點的度不一定相同）； 不等長結(jié)

8、構(gòu)太復雜（要定義好多種結(jié)構(gòu)類型）。不等長結(jié)構(gòu)太復雜（要定義好多種結(jié)構(gòu)類型）。解決思路：解決思路：先研究最簡單、最有規(guī)律的樹，然后設(shè)法把先研究最簡單、最有規(guī)律的樹，然后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹。一般的樹轉(zhuǎn)化為簡單樹。為何要重點研究每結(jié)點最多只有兩個為何要重點研究每結(jié)點最多只有兩個 “叉叉” 的樹的樹？二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；可以證明，所有樹都能轉(zhuǎn)為唯一對應的二叉樹，不失一般性?？梢宰C明，所有樹都能轉(zhuǎn)為唯一對應的二叉樹，不失一般性。定義：定義：是是n（n0）個結(jié)點的有限集合，由一個根結(jié)點以及兩）個結(jié)點的有限集合，由一個根結(jié)點以及兩棵互不相交的、分別稱為棵互

9、不相交的、分別稱為左子樹和右子樹左子樹和右子樹的二叉樹組成的二叉樹組成 ?；咎卣骰咎卣? 每個結(jié)點最多只有兩棵子樹（不存在度大于每個結(jié)點最多只有兩棵子樹（不存在度大于2 2的結(jié)點）；的結(jié)點）； 左子樹和右子樹次序不能顛倒（有序樹）。左子樹和右子樹次序不能顛倒（有序樹）?；拘螒B(tài)：基本形態(tài)： 5種種/2種種ADT BinaryTree 數(shù)據(jù)對象數(shù)據(jù)對象D: 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R: 基本操作基本操作 P：ADT BinaryTree若若D =，則，則R= ；若若D，則，則R= H；存在二元關(guān)系：；存在二元關(guān)系： root 唯一，它在關(guān)系唯一，它在關(guān)系H下無前趨下無前趨 若若D-root ,則存在

10、則存在Dl, Dr滿足滿足:D-root = Dl, Dr，且，且DlDr = 若若Dl，則唯一存在，則唯一存在xl Dl , H, 且存在且存在Dl上的關(guān)系上的關(guān)系Hl H; 同樣定義同樣定義 xr 及及 Hr H = , , Hl, Hr ( Dl, Hl ) 及及( Dl, Hl ) 均是是符合本定義的二叉樹，均是是符合本定義的二叉樹， 其根分別是其根分別是xl（若（若Dl ）、）、xr（若（若Dr ）D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。/至少有至少有20個，見教材個，見教材P122性質(zhì)性質(zhì)1: 1: 在二叉樹的第在二叉樹的第i i層上至多有層上至多有個個

11、結(jié)點（結(jié)點（i0i0）。）。性質(zhì)性質(zhì)2: 2: 深度為深度為k k的二叉樹至多有的二叉樹至多有個個 結(jié)點（結(jié)點（k0k0）。）。性質(zhì)性質(zhì)3: 3: 對于任何一棵二叉樹，若對于任何一棵二叉樹，若2 2度的結(jié)點數(shù)有度的結(jié)點數(shù)有n n2 2個，則葉子個，則葉子數(shù)（數(shù)（n n0 0）必定為）必定為n n2 21 1 （即（即n0=n2+1）二叉樹中全部結(jié)點數(shù)二叉樹中全部結(jié)點數(shù)nn0+n1+n2( (葉子數(shù)葉子數(shù)1 1度結(jié)點數(shù)度結(jié)點數(shù)2 2度結(jié)點數(shù)度結(jié)點數(shù)) )二叉樹中全部結(jié)點數(shù)二叉樹中全部結(jié)點數(shù)nB+1 ( ( 總分支數(shù)根結(jié)點總分支數(shù)根結(jié)點 ) ) （除根結(jié)點外，每個結(jié)點必有一個直接前趨，即一個分支）

12、（除根結(jié)點外，每個結(jié)點必有一個直接前趨，即一個分支）總分支數(shù)總分支數(shù)B= n1+2n2 (1(1度結(jié)點必有度結(jié)點必有1 1個直接后繼，個直接后繼，2 2度結(jié)點必有度結(jié)點必有2 2個個) )n0+n1+n2= n1+2n2 +1, 即即n0=n2+1實際意義：實際意義：葉子數(shù)葉子數(shù)2 2度結(jié)點數(shù)度結(jié)點數(shù)1 1ABCGEIDHFJ完全二叉樹：完全二叉樹：深度為深度為k 的的，有有n個結(jié)點個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與的二叉樹，當且僅當其每一個結(jié)點都與深度為深度為k 的滿二叉樹中編號從的滿二叉樹中編號從1至至n的結(jié)的結(jié)點一一對應。點一一對應。AOBCGEKDJFIHNML深度為深度為4 4

13、的滿二叉樹的滿二叉樹深度為深度為4 4的的完全二叉樹完全二叉樹ABCGEIDHFJ為何要研究這兩種特殊形式？為何要研究這兩種特殊形式？因為它們在順序存儲方式下可以復原！因為它們在順序存儲方式下可以復原！ 解釋：完全二叉樹的特點就是，只有最后解釋：完全二叉樹的特點就是，只有最后一層葉子不滿，且全部集中在左邊。一層葉子不滿，且全部集中在左邊。性質(zhì)性質(zhì)4: 4: 具有具有n n個結(jié)點的完全二叉樹的深度必為個結(jié)點的完全二叉樹的深度必為loglog2 2nn1 1性質(zhì)性質(zhì)5: 5: 對完全二叉樹，若從上至下、從左至右編號，則對完全二叉樹，若從上至下、從左至右編號，則編號為編號為i 的結(jié)點，若存在左孩子，

14、其左孩子編號必為的結(jié)點，若存在左孩子，其左孩子編號必為2i，若，若存在右孩子，其右孩子編號必為存在右孩子，其右孩子編號必為2i1；且其雙親的編號必；且其雙親的編號必為為i/2（i1 時為根時為根, ,除外除外）。）。 證明：根據(jù)性質(zhì)證明：根據(jù)性質(zhì)2 2，深度為，深度為k k的二叉樹最多只有的二叉樹最多只有2 2k k-1-1個結(jié)個結(jié)點，且完全二叉樹的定義是與同深度的滿二叉樹前面編點，且完全二叉樹的定義是與同深度的滿二叉樹前面編號相同，即它的總結(jié)點數(shù)號相同，即它的總結(jié)點數(shù)n n位于位于k k層和層和k-1k-1層滿二叉樹容量層滿二叉樹容量之間，即之間，即 2 2k-1k-1-1-1 n n 2

15、2k k-1 -1 或或 2 2k-1 k-1 n 2 n 2k k三邊同時取對數(shù)，于是有：三邊同時取對數(shù)，于是有：k-1logk-1log2 2nk ndata); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); / if / PreOrderTraverse中序遍歷中序遍歷:InOrderTraverse(T-lchild, vist);vist(T-data); InOrderTraverse(T-rchild, vist);后序遍歷后序遍歷:LastOrderTraverse(T-lchild, vist);LastOrd

16、erTraverse(T- rchild, vist);vist(T-data); AFEDCBG中序遍歷：中序遍歷：void InOrderTraverse(BiTree T, void (* Vist)(TElemType e) if (T) InOrderTraverse(T-lchild); vist(T-data); InOrderTraverse(T-rchild); / if / PreOrderTraverse1. 從前面的三種遍歷算法可以知道：如果將從前面的三種遍歷算法可以知道：如果將vist語句抹去，從語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍遞歸的角

17、度看，這三種算法是完全相同的，或者說這三種遍歷算法的歷算法的訪問路徑是相同的，只是訪問結(jié)點的時機不同訪問路徑是相同的，只是訪問結(jié)點的時機不同。從虛線的出發(fā)點到終點的路徑從虛線的出發(fā)點到終點的路徑上，每個結(jié)點經(jīng)過上，每個結(jié)點經(jīng)過3次次。AFEDCBG第第1次次經(jīng)過時訪問經(jīng)過時訪問先序先序遍歷遍歷第第2次次經(jīng)過時訪問經(jīng)過時訪問中序中序遍歷遍歷第第3次次經(jīng)過時訪問經(jīng)過時訪問后序后序遍歷遍歷2. 2. 二叉樹遍歷的時間效率和空間效率二叉樹遍歷的時間效率和空間效率時間效率時間效率: : /每個結(jié)點只訪問一次每個結(jié)點只訪問一次空間效率空間效率: : /棧占用的最大輔助空間棧占用的最大輔助空間（精確值：樹深

18、為（精確值：樹深為k k的遞歸遍歷需要的遞歸遍歷需要k+1k+1個輔助單元?。﹤€輔助單元?。﹙oid CreateBiTree(BiTree &T) scanf(&ch); if (ch= ) T=NULL; else if (!T=(BiTree)malloc(sizeof(BiTNode) exit(OVERFLOW); T-Data=ch; CreateBTree (T-lchild); CreateBTree (T-rchlid); /if/CreateBeTree思路：思路：利用利用前序前序遍歷來建樹遍歷來建樹（結(jié)點值陸續(xù)從鍵盤輸入）（結(jié)點值陸續(xù)從鍵盤輸入）&假設(shè)節(jié)點的數(shù)據(jù)域為字符類

19、型，那么對于假設(shè)節(jié)點的數(shù)據(jù)域為字符類型，那么對于先序建樹算法先序建樹算法，欲建，欲建下述二叉樹，請給出需要由鍵盤錄入的下述二叉樹，請給出需要由鍵盤錄入的字符序列字符序列ABCEDF答答：A B D F E C void CreateBiTree(BiTree &T) scanf(&ch); if (ch= ) T=NULL; else CreateBTree (T-lchild); CreateBTree (T-rchlid); if (!T=(BiTree)malloc(sizeof(BiTNode) exit(OVERFLOW); T-Data=ch; /if/CreateBeTree思路

20、：思路：利用利用后序后序遍歷來建樹遍歷來建樹（結(jié)點值陸續(xù)從鍵盤輸入）（結(jié)點值陸續(xù)從鍵盤輸入）void CreateBiTree(BiTree &T) scanf(&ch); if (ch= ) T=NULL; else CreateBTree ( L ); CreateBTree ( R ); if (!T=(BiTree)malloc(sizeof(BiTNode) exit(OVERFLOW); T-Data=ch; T-lchild=L; T-rchild=R /if/CreateBeTree思路：思路：利用利用后序后序遍歷來建樹遍歷來建樹（結(jié)點值陸續(xù)從鍵盤輸入）（結(jié)點值陸續(xù)從鍵盤輸入）

21、&假設(shè)節(jié)點的數(shù)據(jù)域為字符類型，那么對于假設(shè)節(jié)點的數(shù)據(jù)域為字符類型，那么對于后序建樹算法后序建樹算法，欲建，欲建下述二叉樹，請給出需要由鍵盤錄入的下述二叉樹，請給出需要由鍵盤錄入的字符序列字符序列ABCEDF答答：A B D F E C 基本思路：基本思路：若不用遞歸，要實現(xiàn)遍歷具有若不用遞歸，要實現(xiàn)遍歷具有 “嵌套嵌套”、“回溯回溯” 結(jié)構(gòu)特征的二叉樹，則必用堆棧。結(jié)構(gòu)特征的二叉樹，則必用堆棧。Void InOrderTraverse(BiTree T, void (* vist)(TElementType e) InitStack(S); Push(S,T); while (!StackEm

22、pty(s) while (Gettop(S,p)&p) Push(S,p-lchild); Pop(S,p); if (!StackEmpty(S) Pop(S,p); Visit(p-Data); Push(S,p-rchild); /if /while /InOrderTraverse ABCEDGFpA中根序訪問序列：pApBpDABCEDGF/ (pDL)中根序訪問序列：pApBpDABCEDGF中根序訪問序列：pApB中根序訪問序列：D ABCEDGFpApB/ (pDR)中根序訪問序列：D ABCEDGFpApB中根序訪問序列：D ABCEDGFpA中根序訪問序列：D BABCE

23、DGFpA中根序訪問序列：D BABCEDGFpEpApF中根序訪問序列：D BABCEDGFpE/ (pFR)pApF中根序訪問序列：D BABCEDGFpEpA中根序訪問序列：D B FABCEDGFpEpA中根序訪問序列：D B FABCEDGFpE/ (pFR)pA中根序訪問序列：D B FABCEDGFpEpA中根序訪問序列：D B F EABCEDGFpA中根序訪問序列：D B F EABCEDGFpGpA中根序訪問序列：D B F EABCEDGFpG/ (pGL)pA中根序訪問序列：D B F EABCEDGFpGpA中根序訪問序列：D B F E GABCEDGFpA中根序訪

24、問序列：D B F E GABCEDGF/ (pGR)pA中根序訪問序列：D B F E GABCEDGF中根序訪問序列：D B F E G AABCEDGFpC中根序訪問序列：D B F E G AABCEDGFpC中根序訪問序列：D B F E G AABCEDGF/ (pCL)pC中根序訪問序列：D B F E G AABCEDGF中根序訪問序列：D B F E G A CABCEDGF中根序訪問序列：D B F E G A CABCEDGF/ (pCR)中根序訪問序列：D B F E G A CABCEDGFvoid InOrderTraverse(BiTree T, void (*

25、vist)(TElementType e) InitStack(S); p=T; while (p|!StackEmpty(s) if(p) Push(S,p); p=p-lchild; else Pop(S,p); Visit(p-Data); p=p-rchild; /if /while /InOrderTraverse 普通二叉樹只能找到結(jié)點的左右孩子信息，普通二叉樹只能找到結(jié)點的左右孩子信息，而該結(jié)點的而該結(jié)點的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。直接前驅(qū)和直接后繼只能在遍歷過程中獲得。若將若將遍歷后對應的有關(guān)前驅(qū)和后繼預存遍歷后對應的有關(guān)前驅(qū)和后繼預存起來，則從起來，則從第一第一

26、個結(jié)點個結(jié)點開始就能很快開始就能很快“順藤摸瓜順藤摸瓜”而遍歷整個樹了。而遍歷整個樹了。兩種解決方法兩種解決方法增加兩個域：增加兩個域：fwd和和bwd； 利用空鏈域（利用空鏈域（n+1個空鏈域）個空鏈域）存放前驅(qū)指針存放前驅(qū)指針存放后繼指針存放后繼指針 如何預存這類信息？如何預存這類信息？例如中序遍歷結(jié)果：例如中序遍歷結(jié)果：B D C E A F H GB D C E A F H G，實際上，實際上已將二叉已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！1）若結(jié)點有左子樹，則）若結(jié)點有左子樹，則lchild指向其左孩子；指向其左孩子； 否則，否

27、則， lchild指向其直接前驅(qū)指向其直接前驅(qū)(即線索即線索)；2）若結(jié)點有右子樹，則）若結(jié)點有右子樹，則rchild指向其右孩子；指向其右孩子； 否則，否則， rchild指向其直接后繼指向其直接后繼(即線索即線索) 。為了避免混淆，增加兩個標志域為了避免混淆，增加兩個標志域，如下圖所示：，如下圖所示：lchildLTagdataRTagrchild約定約定:當當Tag域為域為0時時,表示表示正常正常情況情況;當當Tag域為域為1時時,表示表示線索線索情況情況.ABCGEIDHFroot懸空？懸空？解：解：該二叉樹中序遍歷結(jié)果為該二叉樹中序遍歷結(jié)果為: : H, D, I, B, E, A,

28、 F, C, G 所以添加線索應當按如下路徑進行：所以添加線索應當按如下路徑進行：為避免懸空為避免懸空態(tài)，應增設(shè)態(tài)，應增設(shè)一個頭結(jié)點一個頭結(jié)點00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為注：此圖中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G0-root1typedef enum PointerTag Link, Thread ;/Link=0: 指針標志指針標志, Thread=1: 線索標志線索標志typedef struct BiThrNode TElemTypedata;struct BiThrNode *lchild, *rch

29、ild;PointerTagLTag, Rtag BiThrNode, *BiThrTree;00A00C00B11E11F11G00D11I01H0-T111JStatus InOrderTraverse_Thr(BiThrTree T, void(*visit)(ElemType e) p=T-lchild; while (p!=T) while (p-Ltag=Link) p = p-lchild;visit(p-data); /訪問左子樹為空的結(jié)點訪問左子樹為空的結(jié)點while (p-Rtag=Thread & p-rchild!=T) p = p-rchild; visit(p-da

30、ta); /訪問由線索所指的后繼結(jié)點訪問由線索所指的后繼結(jié)點 /whilep = p-rchild; /while/ InOrderTraverse_Thr00A00C00B11E11F11G00D11I01H0-T111JThrtStatus InOrderThreading(BiThrTree &Thrt, BiThrTree T) if (!Thrt = (BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW); Thrt-LTag =Link; Thrt-RTag=Thrad; Thrt-rchild=Thrt; if (!T) Thrt-l

31、child=Thrt; else Thrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt; pre-RTag=Thread;Thrt-rchild=pre; return OK;/InOrderTheadingvoid InThreading(BiThrTree p) if (p) InThreading(p-lchild);if (!p-lchild) p-LTag=Thread; p-lchild=pre;if (!pre-rchild) p-RTag=Thread; pre-rchild=p;pre=p;InThreading(p-rc

32、hild); /if /InThreading70問題：問題：如何利用中序線索線性的遍歷各個結(jié)點？如何利用中序線索線性的遍歷各個結(jié)點？中序序列：中序序列：D-G-B-A-E-C-H-FD-G-B-A-E-C-H-F D B G A C E H F思路：思路：if (if (有左孩子有左孩子) ) 沿沿lchildlchild直到端節(jié)點，訪問端節(jié)點直到端節(jié)點，訪問端節(jié)點 else if ( else if (沒有右孩子沒有右孩子) ) 沿中序后繼線索沿中序后繼線索rchildrchild ，逐步訪問節(jié)點，逐步訪問節(jié)點 else else 以以rchildrchild為子樹根指針，重復上述過程為子

33、樹根指針，重復上述過程 71 D B G A C E H F問題：問題：如何利用后序線索遍歷各個結(jié)點？（如何利用后序線索遍歷各個結(jié)點？（D的后繼？）的后繼？）易漏畫易漏畫不應指不應指ANULL后序序列：后序序列：G-D-B-E-H-F-C-AG-D-B-E-H-F-C-A思路：思路：逆序遍歷（逆序遍歷（A-C-F-H-E-B-D-GA-C-F-H-E-B-D-G）72問題：問題：如何利用先序線索線性的遍歷各個結(jié)點？如何利用先序線索線性的遍歷各個結(jié)點？不應指不應指A D B G C E H F易漏畫易漏畫NULL先序序列：先序序列：A-B-D-G-C-E-F-HA-B-D-G-C-E-F-H思路

34、：思路：先訪問根節(jié)點先訪問根節(jié)點 if (if (有左孩子有左孩子) ) 沿沿lchildlchild，逐步訪問節(jié)點，逐步訪問節(jié)點 else if ( else if (沒有右孩子沒有右孩子) ) 沿先序后繼線索沿先序后繼線索rchild, rchild, 逐步訪問節(jié)點逐步訪問節(jié)點 else else 以以rchildrchild為子樹根指針，重復上述過程為子樹根指針，重復上述過程 A樹有三種常用存儲方式：樹有三種常用存儲方式：雙親表示法雙親表示法 孩子表示法孩子表示法 孩子兄弟表示法孩子兄弟表示法 1 1、用雙親表示法來存儲、用雙親表示法來存儲思路：思路：用一組用一組連續(xù)空間連續(xù)空間來存儲樹

35、的結(jié)點，同時在每個結(jié)點中來存儲樹的結(jié)點，同時在每個結(jié)點中附附設(shè)一個指示器設(shè)一個指示器，指示其雙親結(jié)點在鏈表中的位置。，指示其雙親結(jié)點在鏈表中的位置。parentsdata結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)dataparents1樹結(jié)構(gòu)樹結(jié)構(gòu) 23n缺點：缺點：求結(jié)點的孩子時需要遍歷整個結(jié)構(gòu)。求結(jié)點的孩子時需要遍歷整個結(jié)構(gòu)。0A-11B02C03D14E15F26G27H38I3思路：思路：將每個結(jié)點的將每個結(jié)點的孩子孩子排列起來，形成一個排列起來，形成一個帶表頭帶表頭（其中填（其中填入父結(jié)點）入父結(jié)點）的線性表的線性表（n n個結(jié)點要設(shè)立個結(jié)點要設(shè)立n n個鏈表）；再將個鏈表）；再將n n個表個表頭用數(shù)組存放頭

36、用數(shù)組存放起來，這樣就形成一個起來，這樣就形成一個混合結(jié)構(gòu)混合結(jié)構(gòu)。例如例如：abecdfhgdefghgfedcbah123456782、用孩子表示法來存儲bc思路：思路：用二叉鏈表用二叉鏈表來表示樹，但其中的兩個指針域含義不同。來表示樹，但其中的兩個指針域含義不同。左指針指向該結(jié)點的第一個孩子；左指針指向該結(jié)點的第一個孩子；右指針指向該結(jié)點的下一個兄弟結(jié)點。右指針指向該結(jié)點的下一個兄弟結(jié)點。nextsiblingdatafirstchild指向左孩子指向左孩子指向右兄弟指向右兄弟abecdfhgbacedfgh方法：方法：加加線線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn) abeidfhgcabeidfhgc兄弟相

37、連兄弟相連長兄為父長兄為父孩子靠左孩子靠左abeidfhgc要點：要點：把右孩子變?yōu)樾值馨延液⒆幼優(yōu)樾值?abeidfhgc方法：方法： 各森林先各自轉(zhuǎn)為二叉樹；各森林先各自轉(zhuǎn)為二叉樹； 依次連到前一個二叉樹的右子樹上。依次連到前一個二叉樹的右子樹上。將森林轉(zhuǎn)換為二叉樹：將森林轉(zhuǎn)換為二叉樹：即即F=TF=T1 1, T, T2 2, , ,T,Tm m B=root, LB, RB B=root, LB, RBABCDEFGHJIABCDEFGHJIBCDEFGHJIABCDEFGHJIABCDEFGHJIEFABCDGHJI先序遍歷先序遍歷C訪問根結(jié)點；訪問根結(jié)點；C依次先序遍歷根結(jié)點的每棵

38、子樹。依次先序遍歷根結(jié)點的每棵子樹。abdec先序序列：先序序列：后序序列：后序序列：a b c d eb d c e a后序遍歷后序遍歷F依次后序遍歷根結(jié)點的每棵子樹；依次后序遍歷根結(jié)點的每棵子樹；F訪問根結(jié)點。訪問根結(jié)點。樹沒有中序遍歷（因子樹不分左右）樹沒有中序遍歷（因子樹不分左右）分別對應二叉樹的先序和中序序列&先序遍歷先序遍歷若森林為空，返回；若森林為空，返回；訪問森林中第一棵樹的根結(jié)點；訪問森林中第一棵樹的根結(jié)點；先序遍歷第一棵樹中根結(jié)點的子樹森林；先序遍歷第一棵樹中根結(jié)點的子樹森林；先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。&中序遍歷

39、中序遍歷若森林為空，返回；若森林為空，返回；中序遍歷森林中第一棵樹的根結(jié)點的子樹森林；中序遍歷森林中第一棵樹的根結(jié)點的子樹森林；訪問第一棵樹的根結(jié)點；訪問第一棵樹的根結(jié)點；中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。&后序遍歷后序遍歷若森林為空，返回；若森林為空，返回；后序遍歷森林中第一棵樹的根結(jié)點的子樹森林；后序遍歷森林中第一棵樹的根結(jié)點的子樹森林；后序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。后序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。訪問第一棵樹的根結(jié)點；訪問第一棵樹的根結(jié)點；ABCDEFGHJI討論：討論：若采用若采用“先轉(zhuǎn)換，后遍歷先轉(zhuǎn)換，后

40、遍歷”方式，結(jié)果是否相同？方式，結(jié)果是否相同？先序序列：先序序列：中序序列：中序序列：A B C D E F G H I JB C D A F E H J I G先序序列：先序序列：中序序列：中序序列：A B C D E F G H I JB C D A F E H J I G結(jié)論：結(jié)論：森林與對應的二叉樹結(jié)果相同。森林與對應的二叉樹結(jié)果相同。 前提：前提：森林的三種遍歷定義（前頁）森林的三種遍歷定義（前頁）后序序列：后序序列：D C B F J I H G E A后序序列：后序序列：D C B F J I H G E A樹的帶權(quán)路徑長度：樹的帶權(quán)路徑長度：WPLWPL = = w wk kl

41、 lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)WPL=36WPL=46WPL= 35哈夫曼哈夫曼樹樹則則是是：WPL WPL 最小的二叉樹。最小的二叉樹。Huffman樹樹構(gòu)造赫夫曼樹的基本思想：構(gòu)造構(gòu)造HuffmanHuffman樹的步驟（即樹的步驟（即HuffmanHuffman算法）：算法）：操作要點：操作要點：對權(quán)值的合并、刪除與替換對權(quán)值的合并、刪除與替換注：方框表示外結(jié)點（葉子注：方框表示外結(jié)點（葉子-字符對應的權(quán)值），字符對應的權(quán)值）， 圓框表示內(nèi)結(jié)點（合并后的權(quán)值）。圓框表示內(nèi)結(jié)點（合并后的權(quán)值）。if(a 60)b = “不及

42、格不及格”;else if(a 70)b = “級格級格”;else if(a 80)b = “中等中等”;else if(a 90)b = “良好良好”;elseb = “優(yōu)秀優(yōu)秀”;判定算法示例判定算法示例: 將百分將百分制數(shù)制數(shù)a,轉(zhuǎn)換為對應的五轉(zhuǎn)換為對應的五級分制數(shù)級分制數(shù)b表示判定過程的判表示判定過程的判定樹定樹a60a70a80a90不及格不及格級格級格中等中等良好良好優(yōu)秀優(yōu)秀YYYYNNNN分數(shù)05960697079808990100比例數(shù)00501504003001070=a8080=a9060=a70a60中等中等良好良好及格及格不及格不及格優(yōu)秀優(yōu)秀YYYYNNNNa80a7

43、0a90a60中等中等不及格不及格及格及格良好良好優(yōu)秀優(yōu)秀YYYYNNN31500次比較次比較 / / 22000次比較（次比較（10000個輸入數(shù)據(jù)）個輸入數(shù)據(jù)）等長編碼：等長編碼：00、01、10、11不等長編碼：不等長編碼：0、1、10、11前綴編碼：前綴編碼：0、10、110、111對對A A、B B、C C、D D進行編碼：進行編碼：在一個字符集中，任何一個字符的編碼都不是另一個字符在一個字符集中，任何一個字符的編碼都不是另一個字符編碼的前綴，這種編碼稱為編碼的前綴，這種編碼稱為前綴編碼前綴編碼。d da ai in n1 11 11 10 00 00 0HuffmanHuffman

44、編碼結(jié)果：編碼結(jié)果：d=d=0 0, i=, i=1010, a=, a=110110, n=, n=111111WPL=1bitWPL=1bit7 72bit2bit5+3bit(2+4)=5+3bit(2+4)=3535特點：每一碼都不是另一碼的前綴，絕不會錯譯特點：每一碼都不是另一碼的前綴，絕不會錯譯! ! 稱為前綴碼稱為前綴碼HuffmanHuffman樹樹 HuffmanHuffman編碼編碼&例例 已知某通訊系統(tǒng)在通訊聯(lián)絡(luò)中只可能出現(xiàn)已知某通訊系統(tǒng)在通訊聯(lián)絡(luò)中只可能出現(xiàn)8中字符，其概率中字符，其概率分別別是分別別是0.05, 0.29, 0.07, 0.08, 0.14, 0.23

45、, 0.03, 0.11, 試設(shè)計赫夫試設(shè)計赫夫曼編碼。曼編碼。&答：答：設(shè)設(shè)8 8個字符分別為個字符分別為A, B, C, D, E, F, G, H, A, B, C, D, E, F, G, H, 對應的一組權(quán)值為對應的一組權(quán)值為 w = 5, 29, 7, 8, 14, 23, 3, 11w = 5, 29, 7, 8, 14, 23, 3, 11，按赫夫曼算法可構(gòu)造一顆赫夫曼，按赫夫曼算法可構(gòu)造一顆赫夫曼樹，并由赫夫曼樹得到各字符的編碼。樹，并由赫夫曼樹得到各字符的編碼。42192385829151001129143578BADCFEHG11111110000000011111011

46、101111110000110010A:B:C:D:E:F:G:H:&例例 已知某通訊系統(tǒng)在通訊聯(lián)絡(luò)中只可能出現(xiàn)已知某通訊系統(tǒng)在通訊聯(lián)絡(luò)中只可能出現(xiàn)8中字符，其概率中字符，其概率分別別是分別別是0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11, 試設(shè)計赫夫試設(shè)計赫夫曼編碼。曼編碼。&對于本例，對于本例， 的具體意義是什么？的具體意義是什么？42192385829151001129143578BADCFEHG11111110000000011111011101111110000110010A:B:C:D:E:F:G:H:WPLWPL = = w wk

47、kl lk k k=1k=1n ntypedef struct unsigned int weight;unsigned int parent, lchild, rchild; HTNode, *HuffmanTree;/動態(tài)分配數(shù)組存儲赫夫曼樹動態(tài)分配數(shù)組存儲赫夫曼樹typedef char *HuffmanCode;/動態(tài)分配數(shù)組存儲赫夫曼編碼表動態(tài)分配數(shù)組存儲赫夫曼編碼表void Huffmacoding(HuffmanTree &HT, Huffmancode &HC, int *w, int n)&建立初始森林建立初始森林m=2*n-1; /其中其中n是待編碼的字符是待編碼的字符(權(quán)

48、值權(quán)值)的數(shù)量，本例的數(shù)量，本例n=8HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); RLPW8765432 RLPW151413121110910共有2*8-1=15個結(jié)點&建立初始森林建立初始森林m=2*n-1; /其中其中n是待編碼的字符是待編碼的字符(權(quán)值權(quán)值)的數(shù)量，本例的數(shù)量，本例n=8HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for (p=HT+1, i=1; i=n; +i, +p, +w) *p = *w, 0, 0, 0 ;0001100030002300014000800070002900

49、0 5RLPW8765432RLPW10共有2*8-1=15個結(jié)點 RLPW1514131211109&建立初始森林建立初始森林m=2*n-1; /其中其中n是待編碼的字符是待編碼的字符(權(quán)值權(quán)值)的數(shù)量，本例的數(shù)量，本例n=8HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for (p=HT+1, i=1; i=n; +i, +p, +w) *p = *w, 0, 0, 0 ;for ( ; i=m; +i, +p) *p = 0, 0, 0, 0 ;00011000300023000140008000700029000 5RLPW87654320000

50、000000000000000000000000RLPW151413121110910共有2*8-1=15個結(jié)點&構(gòu)造赫夫曼樹構(gòu)造赫夫曼樹樹中共有樹中共有m-n個分支結(jié)點（本例：個分支結(jié)點（本例：15 - 8 = 7，存放在，存放在HT的的第第9 第第15個分量中）個分量中）重復重復m-n次：次：“選擇選擇 造樹造樹 加入加入刪除刪除”操作，完成目操作，完成目標赫夫曼樹的構(gòu)造（本例：標赫夫曼樹的構(gòu)造（本例： 根節(jié)點根節(jié)點存放在存放在HT的的 第第15個分量個分量中）中） for ( i = n+1; i=m; +i ) Select( HT, i-1, s1, s2 ); HTs1.paren

51、t = i; HTs2.parent=i; HTi.lchild = s1; HTi.rchild=s2; HTi.weight = HTs1.weight + HTs2.weight; /for&造樹過程（造樹過程（HT中的內(nèi)容變化）中的內(nèi)容變化） 00011000300023000140008000700029000 5RLPW87654320000000000000000000000000000RLPW151413121110910&造樹過程（造樹過程（HT中的內(nèi)容變化）中的內(nèi)容變化） 00011000300023000140008000700029000 5RLPW8765432000

52、0000000000000000000000000RLPW151413121110910&造樹過程（造樹過程（HT中的內(nèi)容變化）中的內(nèi)容變化） 00011000300023000140008000700029000 5RLPW87654320000000000000000000000007108RLPW151413121110910&造樹過程（造樹過程（HT中的內(nèi)容變化）中的內(nèi)容變化） 00011009300023000140008000700029009 5RLPW87654320000000000000000000000007108RLPW151413121110910&造樹過程（造樹過程

53、（HT中的內(nèi)容變化）中的內(nèi)容變化） 00011009300023000140008000700029009 5RLPW87654320000000000000000000000007108RLPW151413121110910&造樹過程（造樹過程（HT中的內(nèi)容變化）中的內(nèi)容變化） 00011009300023000140008000700029009 5RLPW87654320000000000000000000000007108RLPW151413121110910&造樹過程（造樹過程（HT中的內(nèi)容變化）中的內(nèi)容變化） 00011009300023000140008000700029009 5RLPW876543200000000000000000000430157108RLPW151413121110910&造樹過程（造樹過程（HT中的內(nèi)容變化）中的內(nèi)容變化） 0001100930002300014001080010700029009 5RLPW876543200000000000000000000430157108RLPW151413121110910&造樹過程（造樹過程（HT中的內(nèi)容變化）中的內(nèi)容