樹與二叉樹分析

1、第六章第六章深圳大學計算機系一、樹的定義一、樹的定義( (Tree)Tree)2第一節(jié)樹的概念與基本術(shù)語第一節(jié)樹的概念與基本術(shù)語n樹是有樹是有n(n0)n(n0)個結(jié)點的有限集合。個結(jié)點的有限集合。n如果如果 n=0n=0，稱為空樹；稱為空樹；n如果如果 n0,n0,稱為非空樹稱為非空樹, ,對于非空樹對于非空樹, ,有且僅有一個特有且僅有一個特定的稱為根定的稱為根( (Root)Root)的節(jié)點的節(jié)點( (無直接前驅(qū)無直接前驅(qū)) )n如果如果 n1n1，則除根以外的其它結(jié)點劃分為則除根以外的其它結(jié)點劃分為 m (m0)m (m0)個個互不相交的有限集互不相交的有限集 T1, T2 ,T1,

2、T2 , Tm, Tm，其中每個集合其中每個集合本身又是一棵樹，并且稱為根的子樹本身又是一棵樹，并且稱為根的子樹( (SubTree)SubTree)。( (此此為遞歸定義為遞歸定義) )n每個結(jié)點都有唯一的直接前驅(qū)，但可能有多個后繼每個結(jié)點都有唯一的直接前驅(qū)，但可能有多個后繼第章樹與二叉樹第章樹與二叉樹一、樹的定義一、樹的定義( (舉例舉例) )3第一節(jié)樹的概念與基本術(shù)語第一節(jié)樹的概念與基本術(shù)語n其中：其中：A A是根；其余結(jié)點分成三個互不相交的子集，是根；其余結(jié)點分成三個互不相交的子集，nT1=B,E,F,K,LT1=B,E,F,K,L； T2=C,G T2=C,G； T3=D,H,I,J

3、,M, T3=D,H,I,J,M,nT1,T2,T3T1,T2,T3都是根都是根A A的子樹，且本身也是一棵樹的子樹，且本身也是一棵樹第章樹與二叉樹第章樹與二叉樹A只有根結(jié)點的樹只有根結(jié)點的樹ACGBDEFKLHMIJ有有13個結(jié)點的樹個結(jié)點的樹二、樹的基本術(shù)語二、樹的基本術(shù)語4第一節(jié)樹的概念與基本術(shù)語第一節(jié)樹的概念與基本術(shù)語n結(jié)點：結(jié)點：包含一個數(shù)據(jù)元素及若干指向其子樹的分支包含一個數(shù)據(jù)元素及若干指向其子樹的分支n結(jié)點的度：結(jié)點的度：結(jié)點擁有的子樹數(shù)結(jié)點擁有的子樹數(shù)n葉結(jié)點：葉結(jié)點：度為度為0 0的結(jié)點的結(jié)點 沒有子樹的結(jié)點沒有子樹的結(jié)點 n分支結(jié)點：分支結(jié)點：度不為度不為0 0的結(jié)點的結(jié)點

4、 包括根結(jié)點包括根結(jié)點 ，也稱為非終端結(jié)點。也稱為非終端結(jié)點。除根外稱為內(nèi)部結(jié)點除根外稱為內(nèi)部結(jié)點第章樹與二叉樹第章樹與二叉樹1層2層4層3層Height= 4ACGBDEFKLHMIJ二、樹的基本術(shù)語二、樹的基本術(shù)語5第一節(jié)樹的概念與基本術(shù)語第一節(jié)樹的概念與基本術(shù)語n孩子：孩子：結(jié)點的子樹的根結(jié)點的子樹的根 直接后繼，可能有多個直接后繼，可能有多個 n雙親：雙親：孩子的直接前驅(qū)孩子的直接前驅(qū) 最多只能有一個最多只能有一個 n兄弟：兄弟：同一雙親的孩子同一雙親的孩子n子孫：子孫：以某結(jié)點為根的以某結(jié)點為根的樹中的所有結(jié)點樹中的所有結(jié)點n祖先：祖先：從根到該結(jié)點從根到該結(jié)點所經(jīng)分支上的所有結(jié)點所

5、經(jīng)分支上的所有結(jié)點第章樹與二叉樹第章樹與二叉樹1層2層4層3層Height= 4ACGBDEFKLHMIJ二、樹的基本術(shù)語二、樹的基本術(shù)語6第一節(jié)樹的概念與基本術(shù)語第一節(jié)樹的概念與基本術(shù)語n層次：根結(jié)點為第一層，其孩子為第二層，依此類推層次：根結(jié)點為第一層，其孩子為第二層，依此類推n深度：樹中結(jié)點的最大層次深度：樹中結(jié)點的最大層次n有序樹：子樹之間存有序樹：子樹之間存 在確定的次序關(guān)系。在確定的次序關(guān)系。n無序樹無序樹: :子樹之間子樹之間 不存在確定的次序關(guān)系。不存在確定的次序關(guān)系。第章樹與二叉樹第章樹與二叉樹1層2層4層3層Height= 4ACGBDEFKLHMIJ二、樹的基本術(shù)語二、樹

6、的基本術(shù)語7第一節(jié)樹的概念與基本術(shù)語第一節(jié)樹的概念與基本術(shù)語n森林：互不相交的樹的集合。森林：互不相交的樹的集合。對樹中每個結(jié)點而言，對樹中每個結(jié)點而言，其子樹的集合即為森林其子樹的集合即為森林. .第章樹與二叉樹第章樹與二叉樹ArootBCDEFGHIJMKLF任何一棵非空樹是一個二元組 Tree = （root，F(xiàn)）其中：root 被稱為根結(jié)點 F 被稱為子樹森林線性結(jié)構(gòu)線性結(jié)構(gòu)樹型結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素第一個數(shù)據(jù)元素 ( (無前驅(qū)無前驅(qū)) ) 根結(jié)點根結(jié)點 ( (無前驅(qū)無前驅(qū)) )最后一個數(shù)據(jù)元素最后一個數(shù)據(jù)元素 (無后繼無后繼)多個葉子結(jié)點多個葉子結(jié)點 ( (無后繼無后繼) )其它

7、數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個前驅(qū)、一個前驅(qū)、 一個后繼一個后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個前驅(qū)、一個前驅(qū)、 多個后繼多個后繼) )一、二叉樹一、二叉樹( (Binary Tree)Binary Tree)9第二節(jié)二叉樹第二節(jié)二叉樹n二叉樹是一種特殊的樹二叉樹是一種特殊的樹n每個結(jié)點最多有棵子樹每個結(jié)點最多有棵子樹n二叉樹的子樹有左右之分二叉樹的子樹有左右之分第章樹與二叉樹第章樹與二叉樹LLRR空樹只有根只有左子樹 只有右子樹有左右子樹二、二叉樹性質(zhì)二、二叉樹性質(zhì)10第二節(jié)二叉樹第二節(jié)二叉樹n在二叉樹的第在二叉樹的第i i層上至多有層上至多有2 2i-1i-1個結(jié)點個結(jié)點n證明：證

8、明：1.1.i=1, i=1, 只有一個根節(jié)點，因此只有一個根節(jié)點，因此2 2i-1i-1=2=20 0=1=12.2.設(shè)第設(shè)第i-1i-1層上，以上性質(zhì)成立，即第層上，以上性質(zhì)成立，即第i-1i-1層至層至多有多有2 2(i-1)-1(i-1)-1結(jié)點。由二叉樹的定義可知，任何結(jié)點。由二叉樹的定義可知，任何結(jié)點的度小于結(jié)點的度小于2 2，因此，第，因此，第i i層上的結(jié)點數(shù)最多層上的結(jié)點數(shù)最多為第為第i-1i-1層上的兩倍，即層上的兩倍，即2 2* *2 2i-2i-2=2=2i-1i-1第章樹與二叉樹第章樹與二叉樹三、二叉樹性質(zhì)三、二叉樹性質(zhì)11第二節(jié)二叉樹第二節(jié)二叉樹n深度為深度為k k

9、的二叉樹至多有的二叉樹至多有2 2k k-1-1個結(jié)點個結(jié)點n證明：證明：1.1.由性質(zhì)，已知第由性質(zhì)，已知第i i層上結(jié)點數(shù)最多為層上結(jié)點數(shù)最多為2 2i-1i-1 k k2.2. 2 2i-1 i-1 = 2= 2k k-1-1 i=1i=1第章樹與二叉樹第章樹與二叉樹四、二叉樹性質(zhì)四、二叉樹性質(zhì)12第二節(jié)二叉樹第二節(jié)二叉樹n如果二叉樹終端結(jié)點數(shù)為如果二叉樹終端結(jié)點數(shù)為n n0 0，度為度為2 2的結(jié)點數(shù)為的結(jié)點數(shù)為n n2 2，則則n n0 0=n=n2 2+1+1n證明：證明：1.1.設(shè)設(shè)n n1 1為度為為度為1 1的結(jié)點，則總結(jié)點數(shù)的結(jié)點，則總結(jié)點數(shù)n= nn= n0 0+n+n1

10、 1+n+n2 22.2.設(shè)設(shè)B B為二叉樹的分支數(shù)，除根結(jié)點外，每個結(jié)點有且為二叉樹的分支數(shù)，除根結(jié)點外，每個結(jié)點有且只有一個分支，因此只有一個分支，因此n=B+1n=B+13.3.每個分支皆由度為每個分支皆由度為1 1或或2 2的結(jié)點發(fā)出，的結(jié)點發(fā)出，B=nB=n1 1+2n+2n2 24.n=B+1=(n4.n=B+1=(n1 1+2n+2n2 2)+1 )+1 = = n n0 0+n+n1 1+n+n2 2，因此，因此 n n0 0=n=n2 2+1+1第章樹與二叉樹第章樹與二叉樹五、滿二叉樹五、滿二叉樹13第二節(jié)二叉樹第二節(jié)二叉樹n一個深度為一個深度為k k且有且有2 2k k-1

11、-1個結(jié)點的二叉樹個結(jié)點的二叉樹n每層上的結(jié)點數(shù)都是最大數(shù)每層上的結(jié)點數(shù)都是最大數(shù)n可以自上而下、可以自上而下、自左至右連續(xù)編號自左至右連續(xù)編號第章樹與二叉樹第章樹與二叉樹621754389 10 1113 14 1512六、完全二叉樹六、完全二叉樹14第二節(jié)二叉樹第二節(jié)二叉樹n當且僅當每一個結(jié)點都與深度相同的滿二叉樹當且僅當每一個結(jié)點都與深度相同的滿二叉樹中編號從中編號從1 1到到n n的結(jié)點一一對應(yīng)的二叉樹的結(jié)點一一對應(yīng)的二叉樹n葉子結(jié)點只在最大兩層上出現(xiàn)葉子結(jié)點只在最大兩層上出現(xiàn)n左子樹深度與右子樹左子樹深度與右子樹深度相等或大深度相等或大第章樹與二叉樹第章樹與二叉樹621754389

12、10 11 12六、完全二叉樹六、完全二叉樹( (性質(zhì)性質(zhì)) )15第二節(jié)二叉樹第二節(jié)二叉樹n具有具有n n個結(jié)點的完全二叉樹個結(jié)點的完全二叉樹, ,其深度為其深度為loglog2 2n +1n +1n設(shè)設(shè)k k為深度，由二叉樹性質(zhì)，已知為深度，由二叉樹性質(zhì)，已知 2 2k-1k-1-1-1 n n 2 2k k-1-1即即 2 2k-1k-1 n n 2 2k k即即 k = logk = log2 2n +1n +1第章樹與二叉樹第章樹與二叉樹621754389 10 11 12六、完全二叉樹六、完全二叉樹( (性質(zhì)性質(zhì)) )16第二節(jié)二叉樹第二節(jié)二叉樹n在完全二叉樹中，結(jié)點在完全二叉樹中

13、，結(jié)點i i的雙親為的雙親為 i/2i/2n結(jié)點結(jié)點i i的左孩子的左孩子LCHILD(i)=2iLCHILD(i)=2in結(jié)點結(jié)點i i的右孩子的右孩子RCHILD(i)=2i+1RCHILD(i)=2i+1第章樹與二叉樹第章樹與二叉樹621754389 10 11 122i+2i2i+32i+12ii+1i/2七、二叉樹的順序存儲結(jié)構(gòu)七、二叉樹的順序存儲結(jié)構(gòu)17第二節(jié)二叉樹第二節(jié)二叉樹n用一組連續(xù)的存儲單元依次自上而下用一組連續(xù)的存儲單元依次自上而下, ,自左至右自左至右存儲結(jié)點存儲結(jié)點第章樹與二叉樹第章樹與二叉樹完全二叉樹的順序表示一般二叉樹的順序表示完全二叉樹的順序表示一般二叉樹的順序

14、表示1 2 3 4 5 6 7 8 9101 2 3 4 0 5 6 7 8 0 0 910 12489 105673912364789 105一、一、 二叉樹的順序存儲表示二叉樹的順序存儲表示例例:ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326二叉樹的順序存儲缺點：浪費空間。二叉樹的順序存儲缺點：浪費空間。七、二叉樹的鏈式存儲結(jié)構(gòu)七、二叉樹的鏈式存儲結(jié)構(gòu)20第二節(jié)二叉樹第二節(jié)二叉樹1.1.二叉鏈表二叉鏈表n采用數(shù)據(jù)域加上左、右孩子指針采用數(shù)據(jù)域加上左、右孩子指針第章樹與二叉樹第章樹與二叉樹datalChildrChildlC

15、hild data rChild七、二叉樹的鏈式存儲結(jié)構(gòu)七、二叉樹的鏈式存儲結(jié)構(gòu)21第二節(jié)二叉樹第二節(jié)二叉樹1.1.二叉鏈表二叉鏈表( (舉例舉例) )n二叉樹（左）及其二叉鏈表（右）二叉樹（左）及其二叉鏈表（右）第章樹與二叉樹第章樹與二叉樹ABCDFEroot ABCDFErootlchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):；七、二叉樹的鏈式存儲結(jié)構(gòu)七、二叉樹的鏈式存儲結(jié)構(gòu)23第二節(jié)二叉樹第二節(jié)二叉樹. .三叉鏈表三叉鏈表n采用數(shù)據(jù)域加上左、右孩子指針及雙親指針采用數(shù)據(jù)域加上左、右孩子指針及雙親指針第章樹與二叉樹第章樹與二叉樹lChild data parent rChildpar

16、entdatalChildrChild七、二叉樹的鏈式存儲結(jié)構(gòu)七、二叉樹的鏈式存儲結(jié)構(gòu)24第二節(jié)二叉樹第二節(jié)二叉樹. .三叉鏈表三叉鏈表( (舉例舉例) )n二叉樹（左）及其三叉鏈表（右）二叉樹（左）及其三叉鏈表（右）第章樹與二叉樹第章樹與二叉樹ABCDFEroot ABCDFE root一、遍歷二叉樹一、遍歷二叉樹25第三節(jié)遍歷二叉樹第三節(jié)遍歷二叉樹n樹的遍歷就是按某種次序訪問樹中的結(jié)點，要樹的遍歷就是按某種次序訪問樹中的結(jié)點，要求每個結(jié)點訪問一次且僅訪問一次求每個結(jié)點訪問一次且僅訪問一次（非線性結(jié)（非線性結(jié)構(gòu)線性化）構(gòu)線性化）n對對“二叉樹二叉樹”而言，可以有三條搜索路徑：而言，可以有三條

17、搜索路徑：n1先上后下先上后下的按層次遍歷；n2先左先左（子樹）后右后右（子樹）的遍歷；n3先右先右（子樹）后左后左（子樹）的遍歷。第章樹與二叉樹第章樹與二叉樹LR一、遍歷二叉樹一、遍歷二叉樹26第三節(jié)遍歷二叉樹第三節(jié)遍歷二叉樹n一個二叉樹由根節(jié)點與左子樹和右子樹組成一個二叉樹由根節(jié)點與左子樹和右子樹組成n設(shè)訪問根結(jié)點用設(shè)訪問根結(jié)點用D D表示，遍歷左、右子樹用表示，遍歷左、右子樹用L L、R R表示表示n如果規(guī)定如果規(guī)定先左子樹后右子樹先左子樹后右子樹，則共有三種組合，則共有三種組合1.1.DLR DLR 先序遍歷先序遍歷 2.LDR 2.LDR 中序遍歷中序遍歷 3.LRD 3.LRD 后

18、序遍歷后序遍歷 第章樹與二叉樹第章樹與二叉樹LR二、先序遍歷二叉樹二、先序遍歷二叉樹27第三節(jié)遍歷二叉樹第三節(jié)遍歷二叉樹n算法：算法：1.1.若二叉樹為空，則返回；否則：若二叉樹為空，則返回；否則：2.2.訪問根節(jié)點訪問根節(jié)點( (D)D)3.3.先序遍歷左子樹先序遍歷左子樹( (L)L)4.4.先序遍歷右子樹先序遍歷右子樹( (R)R)第章樹與二叉樹第章樹與二叉樹LR二、先序遍歷二叉樹二、先序遍歷二叉樹28第三節(jié)遍歷二叉樹第三節(jié)遍歷二叉樹n算法算法( (舉例舉例) )：第章樹與二叉樹第章樹與二叉樹ADBFCGE輸出結(jié)果：輸出結(jié)果：ABDEGCFABDEGCF二、先序遍歷二叉樹二、先序遍歷二叉

19、樹29第三節(jié)遍歷二叉樹第三節(jié)遍歷二叉樹第章樹與二叉樹第章樹與二叉樹三、中序遍歷二叉樹三、中序遍歷二叉樹30第三節(jié)遍歷二叉樹第三節(jié)遍歷二叉樹n算法：算法：1.1.若二叉樹為空，則返回；否則：若二叉樹為空，則返回；否則：2.2.中序遍歷左子樹中序遍歷左子樹( (L)L)3.3.訪問根節(jié)點訪問根節(jié)點( (D)D)4.4.中序遍歷右子樹中序遍歷右子樹( (R)R)第章樹與二叉樹第章樹與二叉樹LR三、中序遍歷二叉樹三、中序遍歷二叉樹31第三節(jié)遍歷二叉樹第三節(jié)遍歷二叉樹n算法算法( (舉例舉例) )：第章樹與二叉樹第章樹與二叉樹ADBFCGE輸出結(jié)果：輸出結(jié)果：DBGEAFCDBGEAFC三、中序遍歷二叉

20、樹三、中序遍歷二叉樹32第三節(jié)遍歷二叉樹第三節(jié)遍歷二叉樹第章樹與二叉樹第章樹與二叉樹；四、后序遍歷二叉樹四、后序遍歷二叉樹33第三節(jié)遍歷二叉樹第三節(jié)遍歷二叉樹n算法：算法：1.1.若二叉樹為空，則返回；否則：若二叉樹為空，則返回；否則：2.2.后序遍歷左子樹后序遍歷左子樹( (L)L)3.3.后序遍歷右子樹后序遍歷右子樹( (R)R)4.4.訪問根節(jié)點訪問根節(jié)點( (D)D)第章樹與二叉樹第章樹與二叉樹LR四、后序遍歷二叉樹四、后序遍歷二叉樹34第三節(jié)遍歷二叉樹第三節(jié)遍歷二叉樹n算法算法( (舉例舉例) )：第章樹與二叉樹第章樹與二叉樹ADBFCGE輸出結(jié)果：輸出結(jié)果：DGEBFCADGEBF

21、CA四、后序遍歷二叉樹四、后序遍歷二叉樹35第三節(jié)遍歷二叉樹第三節(jié)遍歷二叉樹第章樹與二叉樹第章樹與二叉樹；遍歷練習遍歷練習n 用二叉樹來表示表達式n 先序遍歷得到前綴表達式（波蘭式）-+ a b c / d en 中序遍歷得到中綴表達式 (a+b)c d/en 后續(xù)遍歷得到后綴表達式（逆波蘭式）ab+cde/-eabcd- -+/e e e遍歷的應(yīng)用遍歷的應(yīng)用1.根據(jù)遍歷順序來確定二叉樹的結(jié)構(gòu)（邏輯上）2. 根據(jù)先序序列建立二叉樹的二叉鏈表（物理上） 僅知二叉樹的先序序列“abcdefg” 不能唯一確定一棵二叉樹，由二叉樹的先序和中序序列建樹由二叉樹的先序和中序序列建樹 如果同時已知二叉樹的中

22、序序列“cbdaegf”，則會如何？ 二叉樹的先序序列二叉樹的中序序列左子樹左子樹左子樹左子樹 右子樹右子樹右子樹右子樹根根根根a b c d e f gc b d a e g f例例: :aab bccddeeffggabcdefg先序序列中序序列練習練習n假設(shè)一顆二叉樹的先序遍歷序列為ABDEHCFGIn中序遍歷序列為DBEHAFCIGn請畫出這顆二叉樹n思考：如果給出后序遍歷序列和中序遍歷序列，是否可以確定該二叉樹的結(jié)構(gòu)？4、建立二叉樹的存儲結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法在此討論利用先序序列，建立二叉鏈表在此討論利用先序序列，

23、建立二叉鏈表 以先序序列創(chuàng)建一棵二叉樹以先序序列創(chuàng)建一棵二叉樹ABCD以空白字符“ ”表示A(B( ,C( , ),D( , )空樹空樹只含一個根結(jié)點只含一個根結(jié)點的二叉樹的二叉樹A以字符串“A ”表示以下列字符串表示A B C D A BCD上頁算法執(zhí)行過程舉例如下：ATBCD一、增加新指針一、增加新指針45第四節(jié)線索二叉樹第四節(jié)線索二叉樹n最簡單的方法是在每個結(jié)點中，增加前驅(qū)最簡單的方法是在每個結(jié)點中，增加前驅(qū)( (fwd)fwd)和后繼和后繼( (bkwd)bkwd)指針指針n在做二叉樹遍歷（前、中、后序），將每個結(jié)在做二叉樹遍歷（前、中、后序），將每個結(jié)點的前驅(qū)和后繼信息添入點的前驅(qū)和

24、后繼信息添入fwdfwd和和bkwdbkwd域中域中第章樹與二叉樹第章樹與二叉樹fwdlChilddatarChildbkwd問題：遍歷是將非線性結(jié)構(gòu)線性化，結(jié)點的先后關(guān)系的信息（某個結(jié)點在序列中的前驅(qū)和后繼等信息）在遍歷的動態(tài)過程中得到，如何保存這些動態(tài)信息呢？二、利用空指針二、利用空指針46第四節(jié)線索二叉樹第四節(jié)線索二叉樹n在有在有n n個結(jié)點的二叉樹中，必定存在個結(jié)點的二叉樹中，必定存在n+1n+1個空鏈個空鏈域域n因為每個結(jié)點有兩個鏈域（左、右孩子指針），因為每個結(jié)點有兩個鏈域（左、右孩子指針），因此共有因此共有2 2n n個鏈域個鏈域n除根結(jié)點外，每個結(jié)點都有且僅有一個分支相除根結(jié)點

25、外，每個結(jié)點都有且僅有一個分支相連，即連，即n-1n-1個鏈域被使用個鏈域被使用第章樹與二叉樹第章樹與二叉樹二、利用空指針二、利用空指針47第四節(jié)線索二叉樹第四節(jié)線索二叉樹n在結(jié)點中增加兩個標記位（在結(jié)點中增加兩個標記位（LTag, RTag)LTag, RTag)nLTag=0, lChildLTag=0, lChild域指示結(jié)點的左孩子域指示結(jié)點的左孩子LTag=1, lChildLTag=1, lChild域指示結(jié)點的前驅(qū)結(jié)點域指示結(jié)點的前驅(qū)結(jié)點nRTag=0, lChildRTag=0, lChild域指示結(jié)點的右孩子域指示結(jié)點的右孩子RTag=1, lChildRTag=1, lCh

26、ild域指示結(jié)點的后繼結(jié)點域指示結(jié)點的后繼結(jié)點第章樹與二叉樹第章樹與二叉樹LTaglChilddatarChildRTag懂原理，最多會畫即可，對于建立過程不需要掌握一、樹的存儲結(jié)構(gòu)一、樹的存儲結(jié)構(gòu)48第五節(jié)樹與森林第五節(jié)樹與森林1.1.雙親表示法雙親表示法n采用一組連續(xù)的存儲空間采用一組連續(xù)的存儲空間n由于每個結(jié)點只有一個雙親，只需要一個指針由于每個結(jié)點只有一個雙親，只需要一個指針第章樹與二叉樹第章樹與二叉樹ABCDEFG-10001130 1 2 3 4 5 6AEBGDFC一、樹的存儲結(jié)構(gòu)一、樹的存儲結(jié)構(gòu)49第五節(jié)樹與森林第五節(jié)樹與森林2.2.孩子表示法孩子表示法n可以采用多重鏈表，即每

27、個結(jié)點有多個指針可以采用多重鏈表，即每個結(jié)點有多個指針n最大缺點是空鏈域太多最大缺點是空鏈域太多(d-1)n+1d-1)n+1個個 第章樹與二叉樹第章樹與二叉樹AEBGDFC data child1child2child3childd一、樹的存儲結(jié)構(gòu)一、樹的存儲結(jié)構(gòu)50第五節(jié)樹與森林第五節(jié)樹與森林2.2.孩子表示法孩子表示法n將每個結(jié)點的孩子排列起來，用單鏈表表示將每個結(jié)點的孩子排列起來，用單鏈表表示n將每個結(jié)點排列成一個線性表將每個結(jié)點排列成一個線性表第章樹與二叉樹第章樹與二叉樹AEBGDFCABCDEFG0123456Root123 45 6 一、樹的存儲結(jié)構(gòu)一、樹的存儲結(jié)構(gòu)51第五節(jié)樹與

28、森林第五節(jié)樹與森林3.3.孩子兄弟表示法孩子兄弟表示法n采用二叉鏈表采用二叉鏈表n左邊指針指向第一個孩子，右邊指針指向兄弟左邊指針指向第一個孩子，右邊指針指向兄弟第章樹與二叉樹第章樹與二叉樹AEBGDFC datafirstChild nextSiblingBCDGFE A 二、樹與二叉樹的對應(yīng)關(guān)系二、樹與二叉樹的對應(yīng)關(guān)系52第五節(jié)樹與森林第五節(jié)樹與森林n樹與二叉樹都可以采用二叉鏈表作存儲結(jié)構(gòu)樹與二叉樹都可以采用二叉鏈表作存儲結(jié)構(gòu)n任意給定一棵樹，可以找到一個唯一的二叉樹任意給定一棵樹，可以找到一個唯一的二叉樹( (沒有右子樹沒有右子樹) )第章樹與二叉樹第章樹與二叉樹AEBGDFCBCDGF

29、E A ABGDFCE樹對應(yīng)的二叉樹樹與二叉樹的轉(zhuǎn)換樹與二叉樹的轉(zhuǎn)換: :以二叉鏈表作為存儲結(jié)構(gòu)，將其解釋為樹或二叉樹，以二叉鏈表作為存儲結(jié)構(gòu)，將其解釋為樹或二叉樹，實現(xiàn)兩者之間的轉(zhuǎn)換。實現(xiàn)兩者之間的轉(zhuǎn)換。三、森林與二叉樹的對應(yīng)關(guān)系三、森林與二叉樹的對應(yīng)關(guān)系54第五節(jié)樹與森林第五節(jié)樹與森林n如果把森林中的第二棵樹的根結(jié)點看作是第一如果把森林中的第二棵樹的根結(jié)點看作是第一棵樹的根結(jié)點的兄弟，則可找到一個唯一的二棵樹的根結(jié)點的兄弟，則可找到一個唯一的二叉樹與之對應(yīng)叉樹與之對應(yīng)第章樹與二叉樹第章樹與二叉樹三棵樹的森林對應(yīng)的二叉樹T1 T2 T3AFHB C DGIJEKABCEDHIKFGJ四、樹的

30、遍歷四、樹的遍歷55第五節(jié)樹與森林第五節(jié)樹與森林n對樹的遍歷主要有兩種：對樹的遍歷主要有兩種：1. 1. 先根（次序）遍歷先根（次序）遍歷2. 2. 后根（次序）遍歷后根（次序）遍歷第章樹與二叉樹第章樹與二叉樹AEBGDFC四、樹的遍歷四、樹的遍歷56第五節(jié)樹與森林第五節(jié)樹與森林1. 1. 先根（次序）遍歷先根（次序）遍歷 當樹非空時當樹非空時n 訪問根結(jié)點訪問根結(jié)點n 依次先根遍歷根的各棵子樹依次先根遍歷根的各棵子樹 輸出結(jié)果：輸出結(jié)果：ABEFCDGABEFCDG第章樹與二叉樹第章樹與二叉樹AEBGDFC四、樹的遍歷四、樹的遍歷57第五節(jié)樹與森林第五節(jié)樹與森林2. 2. 后根（次序）遍歷后

31、根（次序）遍歷 當樹非空時當樹非空時n依次后根遍歷根的各棵子樹依次后根遍歷根的各棵子樹n訪問根結(jié)點訪問根結(jié)點 輸出結(jié)果：輸出結(jié)果：EFBCGDAEFBCGDA第章樹與二叉樹第章樹與二叉樹AEBGDFC五、森林的遍歷五、森林的遍歷58第五節(jié)樹與森林第五節(jié)樹與森林n對森林的遍歷主要有兩種：對森林的遍歷主要有兩種：1. 1. 先序遍歷先序遍歷2. 2. 中序遍歷中序遍歷第章樹與二叉樹第章樹與二叉樹AEBGDFC五、森林的遍歷五、森林的遍歷59第五節(jié)樹與森林第五節(jié)樹與森林1. 1. 先序遍歷 若森林不空，則n訪問訪問森林中第一棵樹的根結(jié)點；n先序遍歷先序遍歷森林中第一棵樹的子樹森林；n先序遍歷先序遍歷

32、森林中(除第一棵樹之外)其余樹構(gòu)成的森林。第章樹與二叉樹第章樹與二叉樹即：依次從左至右依次從左至右對森林中的每一棵樹樹進行先根遍歷先根遍歷。AFHBCDGIJEK先序遍歷：ABCDEFGHIKJ五、森林的遍歷五、森林的遍歷第五節(jié)樹與森林第五節(jié)樹與森林第章樹與二叉樹第章樹與二叉樹1. 1. 先序遍歷五、森林的遍歷五、森林的遍歷61第五節(jié)樹與森林第五節(jié)樹與森林2.2. 中序遍歷 若森林不空，則n中序遍歷中序遍歷森林中第一棵樹的子樹森林；n訪問訪問森林中第一棵樹的根結(jié)點；n中序遍歷中序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。第章樹與二叉樹第章樹與二叉樹即：依次從左至右依次從左至右對森林中的每一

33、棵樹樹進行后根遍歷后根遍歷。AFHBCDGIJEK中序遍歷：BCEDAGFKIJH五、森林的遍歷五、森林的遍歷第五節(jié)樹與森林第五節(jié)樹與森林第章樹與二叉樹第章樹與二叉樹2. 2. 中序遍歷思考？思考？n當樹以二叉鏈表(孩子兄弟表示法)進行存儲，則樹的先根遍歷和后根遍歷與二叉樹的遍歷算法有什么關(guān)系？樹的先根-二叉樹的先序樹的后根-二叉樹的中序 遍歷的對應(yīng)關(guān)系遍歷的對應(yīng)關(guān)系先根遍歷先根遍歷后根遍歷后根遍歷樹樹二叉樹二叉樹森林森林先序遍歷先序遍歷先序遍歷先序遍歷中序遍歷中序遍歷中序遍歷中序遍歷練習練習1.1.若一個二叉樹具有若一個二叉樹具有8個度為個度為2的結(jié)點，的結(jié)點，7個度為個度為1的結(jié)點，則度為

34、的結(jié)點，則度為0的結(jié)點（葉子）個數(shù)是的結(jié)點（葉子）個數(shù)是_。2.2.具有具有n個結(jié)點的二叉樹中，一共有個結(jié)點的二叉樹中，一共有_個指針個指針域，其中域，其中_個用來指向結(jié)點的左右孩子，有個用來指向結(jié)點的左右孩子，有_個為個為NULL。練習練習3.3.假定用一維數(shù)組假定用一維數(shù)組a7順序存儲一個循環(huán)隊列，順序存儲一個循環(huán)隊列，隊首和隊尾指針分別用隊首和隊尾指針分別用front和和rear表示，當前表示，當前隊列中已有隊列中已有4個元素：個元素：12，23，78，60，其中，其中12為隊首元素，為隊首元素，front的值為的值為3，請畫出對應(yīng)的，請畫出對應(yīng)的存儲狀態(tài)。當連續(xù)做存儲狀態(tài)。當連續(xù)做2次

35、出隊運算后，再讓次出隊運算后，再讓15，36，40，50，60元素依次進隊，分別畫出隊、元素依次進隊，分別畫出隊、入隊后對應(yīng)的存儲狀態(tài)。入隊后對應(yīng)的存儲狀態(tài)。練習練習4.4.二叉樹的中序和后序遍歷結(jié)果分別為二叉樹的中序和后序遍歷結(jié)果分別為EFBCGHIDA和和FEIHGDCBA。 （1） 畫出該樹，求其先序遍歷的結(jié)果；畫出該樹，求其先序遍歷的結(jié)果； （2）將其轉(zhuǎn)換為樹，畫出轉(zhuǎn)換后的樹）將其轉(zhuǎn)換為樹，畫出轉(zhuǎn)換后的樹。 （3）求其先根、后根遍歷序列。求其先根、后根遍歷序列。一、最優(yōu)二叉樹一、最優(yōu)二叉樹68第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫夫曼樹及其應(yīng)用n路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分路徑：從

36、樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑支構(gòu)成這兩個結(jié)點之間的路徑n路徑長度：路徑上的分支數(shù)目路徑長度：路徑上的分支數(shù)目n樹的路徑長度：從樹根到樹的路徑長度：從樹根到每個結(jié)點的路徑長度之和每個結(jié)點的路徑長度之和n右樹路徑長度為：右樹路徑長度為：2 2* *1 + 31 + 3* *2 + 12 + 1* *3 = 113 = 11第章樹與二叉樹第章樹與二叉樹ADBFCGE一、最優(yōu)二叉樹一、最優(yōu)二叉樹69第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫夫曼樹及其應(yīng)用n結(jié)點的帶權(quán)路徑長度：從結(jié)點到樹根之間的路結(jié)點的帶權(quán)路徑長度：從結(jié)點到樹根之間的路徑長度與結(jié)點上權(quán)的乘積徑長度與結(jié)點上權(quán)的乘積n樹的

37、帶權(quán)路徑長度樹的帶權(quán)路徑長度( (WPL)WPL)：樹中所有葉子結(jié)點樹中所有葉子結(jié)點的帶權(quán)路徑長度之和的帶權(quán)路徑長度之和nWPL = 2WPL = 2* *5+35+3* *3+23+2* *4=274=27第章樹與二叉樹第章樹與二叉樹ADBFCGE5一、最優(yōu)二叉樹一、最優(yōu)二叉樹70第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫夫曼樹及其應(yīng)用n最優(yōu)二叉樹：假設(shè)二叉樹有最優(yōu)二叉樹：假設(shè)二叉樹有n n個葉子，其每個個葉子，其每個葉子結(jié)點帶權(quán)葉子結(jié)點帶權(quán)w wi i，則帶權(quán)路徑長度則帶權(quán)路徑長度WPLWPL最小的最小的二叉樹稱為最優(yōu)二叉樹或赫夫曼二叉樹稱為最優(yōu)二叉樹或赫夫曼( (Huffman)Huffman)樹。

38、樹。nWPL = 1WPL = 1* *5+25+2* *3+23+2* *4=194=19第章樹與二叉樹第章樹與二叉樹ADBCE5第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫夫曼樹及其應(yīng)用第章樹與二叉樹第章樹與二叉樹例：例：設(shè)設(shè)5 5個葉子結(jié)點，分別帶權(quán)個葉子結(jié)點，分別帶權(quán)7 7、9 9、5 5、4 4、2 2， 至少畫出至少畫出2 2種二叉樹，并計算帶權(quán)路徑長度。種二叉樹，并計算帶權(quán)路徑長度。27549WPL(T)= 72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 7 9 254二、二、HuffmanHuffman樹樹( (構(gòu)造構(gòu)造) )73第六節(jié)赫夫曼樹及其應(yīng)

39、用第六節(jié)赫夫曼樹及其應(yīng)用n在在HuffmanHuffman樹中，權(quán)值最大的結(jié)點離根最近樹中，權(quán)值最大的結(jié)點離根最近n權(quán)值最小的結(jié)點離根最遠權(quán)值最小的結(jié)點離根最遠第章樹與二叉樹第章樹與二叉樹ADBCE5二、二、HuffmanHuffman樹樹( (算法算法) )74第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫夫曼樹及其應(yīng)用1.1.根據(jù)給定的根據(jù)給定的n n個權(quán)值個權(quán)值( (w w1 1, w, w2 2, , , w, wn n) )構(gòu)成構(gòu)成n n棵二叉樹棵二叉樹的集合的集合F=TF=T1 1, T, T2 2, , , T, Tn n ，其中每棵二叉樹其中每棵二叉樹T Ti i中只中只有一個帶權(quán)為有一個帶權(quán)

40、為w wi i的根結(jié)點，左右子樹為空的根結(jié)點，左右子樹為空2.2.在在F F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置其根結(jié)點的權(quán)值為其左右構(gòu)造一棵新的二叉樹，且置其根結(jié)點的權(quán)值為其左右子樹根結(jié)點的權(quán)值之和子樹根結(jié)點的權(quán)值之和3.3.在在F F中刪除這兩棵樹，同時將新得到的二叉樹加入中刪除這兩棵樹，同時將新得到的二叉樹加入F F中中4.4.重復(fù)重復(fù)2, 32, 3，直到，直到F F只含一棵樹為止只含一棵樹為止第章樹與二叉樹第章樹與二叉樹二、二、HuffmanHuffman樹樹( (舉例舉例) )75第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫

41、夫曼樹及其應(yīng)用第章樹與二叉樹第章樹與二叉樹F : 7 5 2 4F : 7 5 6F : 7 11 7524初始合并2 475246F : 18 1175246合并5 65合并7 11274611189例如例如: : 已知權(quán)值已知權(quán)值 W= 5, 6, 2, 9, 7 56275276976713975267139797166713295252第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫夫曼樹及其應(yīng)用第章樹與二叉樹第章樹與二叉樹練習：練習：設(shè)葉子結(jié)點設(shè)葉子結(jié)點a a、b b、c c、d d、e e的權(quán)值分別的權(quán)值分別為為5 5 、4 4 、10 10 、12 12 、9 9，構(gòu)造，構(gòu)造HuffmanHuff

42、man樹，并樹，并計算帶權(quán)路徑長度。計算帶權(quán)路徑長度。三、三、HuffmanHuffman編碼編碼79第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫夫曼樹及其應(yīng)用n設(shè)給出一段報文：設(shè)給出一段報文：GOOD_GOOD_GOOD_GOOOOOOOO_OFFGOOD_GOOD_GOOD_GOOOOOOOO_OFFn字符集合是字符集合是 O, G, _, D, FO, G, _, D, F，各個字符出各個字符出現(xiàn)的頻度現(xiàn)的頻度( (次數(shù)次數(shù)) )是是 W W 15, 4, 4, 3, 2 15, 4, 4, 3, 2。n若給每個字符以等長編碼若給每個字符以等長編碼O: 000 G: 001 _: 010 D: 011

43、 F: 100O: 000 G: 001 _: 010 D: 011 F: 100n則總編碼長度為則總編碼長度為 (1 (15+4+4+3+2) 5+4+4+3+2) * * 3 = 84. 3 = 84.第章樹與二叉樹第章樹與二叉樹三、三、HuffmanHuffman編碼編碼80第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫夫曼樹及其應(yīng)用n若按各個字符出現(xiàn)的概率不同而給予不等長編若按各個字符出現(xiàn)的概率不同而給予不等長編碼，可望減少總編碼長度。碼，可望減少總編碼長度。n各字符各字符 O, G, _, D, F O, G, _, D, F 出現(xiàn)概率為出現(xiàn)概率為 1 15/28, 4/28, 4/28, 3/28

44、, 2/28 ,5/28, 4/28, 4/28, 3/28, 2/28 ,化整化整為為 1 15, 4, 4, 3, 2 5, 4, 4, 3, 2 第章樹與二叉樹第章樹與二叉樹三、三、HuffmanHuffman編碼編碼81第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫夫曼樹及其應(yīng)用n各字符出現(xiàn)概率各字符出現(xiàn)概率 取整數(shù)取整數(shù) 為為115, 4, 4, 3, 25, 4, 4, 3, 2n如果規(guī)定，如果規(guī)定，HuffmanHuffman樹的左子樹小于右子樹，樹的左子樹小于右子樹，則可構(gòu)成右圖所示則可構(gòu)成右圖所示HuffmanHuffman樹樹第章樹與二叉樹第章樹與二叉樹415423G_FDO三、三、Huf

45、fmanHuffman編碼編碼82第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫夫曼樹及其應(yīng)用n令左孩子分支為編碼令左孩子分支為編碼0 0，右，右孩子分支為編碼孩子分支為編碼1 1n將根結(jié)點到葉子結(jié)點路徑上的將根結(jié)點到葉子結(jié)點路徑上的分支編碼，組合起來，作為該分支編碼，組合起來，作為該字符的字符的HuffmanHuffman碼，則可得到：碼，則可得到：O:1 _:011 G:010 D:001 O:1 _:011 G:010 D:001 F:000 F:000第章樹與二叉樹第章樹與二叉樹41542300001111G_FDO三、三、HuffmanHuffman編碼編碼83第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫夫曼樹及

46、其應(yīng)用n則總編碼長度為則總編碼長度為 1 15 5* *1+(2+3+4+4)1+(2+3+4+4)* *3 = 54 3 = 54 84 84nHuffmanHuffman是一種前綴編碼，解碼是一種前綴編碼，解碼時不會混淆時不會混淆n如如GOODGOOD編碼為：編碼為：0101100101011001第章樹與二叉樹第章樹與二叉樹41542300001111G_FDO 若設(shè)計長短不等的編碼，則必須是任一個若設(shè)計長短不等的編碼，則必須是任一個字符的編碼都不是另一個字符編碼的前綴，稱為字符的編碼都不是另一個字符編碼的前綴，稱為前綴編碼。前綴編碼。前綴編碼前綴編碼 利用利用赫夫曼樹赫夫曼樹可以構(gòu)造一

47、種不等長的二進制可以構(gòu)造一種不等長的二進制編碼，并且構(gòu)造所得的赫夫曼編碼是編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)一種最優(yōu)前綴編碼前綴編碼，即使，即使所傳電文的總長度最短所傳電文的總長度最短。第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫夫曼樹及其應(yīng)用第章樹與二叉樹第章樹與二叉樹練習：練習：對電文對電文abbaccdeecabbaccdeec進行進行HuffmanHuffman編碼。編碼。四、四、HuffmanHuffman編碼實現(xiàn)編碼實現(xiàn)86第六節(jié)赫夫曼樹及其應(yīng)用第六節(jié)赫夫曼樹及其應(yīng)用第章樹與二叉樹第章樹與二叉樹HuffmanHuffman樹的構(gòu)造。用靜態(tài)鏈表實現(xiàn)樹的構(gòu)造。用靜態(tài)鏈表實現(xiàn), ,結(jié)構(gòu)如下。結(jié)構(gòu)

48、如下。n n個葉子結(jié)點的個葉子結(jié)點的HuffmanHuffman樹共樹共2n-12n-1個結(jié)點。個結(jié)點。( (兩兩合兩兩合并，直至一個，共生成并，直至一個，共生成n-1n-1個結(jié)點）個結(jié)點）設(shè)靜態(tài)鏈表為設(shè)靜態(tài)鏈表為HTHT，計算過程如下：，計算過程如下： 初始令初始令n=n=葉子結(jié)點數(shù)，設(shè)置葉子結(jié)點數(shù)，設(shè)置0 0nn-1-1結(jié)點的結(jié)點的datadata、weightweight，并令所有單元的，并令所有單元的parent,lchild,rchildparent,lchild,rchild為為0 0 從從0n-10n-1中選取中選取parentparent為為0 0，權(quán)值最小的兩個結(jié)點，權(quán)值最小的兩個結(jié)點， 設(shè)為設(shè)為s1,s2,s1,s2,令令n n為此兩結(jié)點的父結(jié)點，修改為此兩結(jié)點的父結(jié)點，修改: : HTs1.parent = n; HTs2.parent = n; HTs1.parent = n; HTs2.parent = n; HTn.lchild = s1; HTn.rchild = s2; HTn.lchild = s1; HTn.rchild = s2; HTn.weight = HTs1.weight+HTs2.weight