樹與二叉樹典型例題講解ppt課件

1、例題例題6.1 6.1 知一棵度為知一棵度為mm的樹有的樹有n1n1個(gè)度為個(gè)度為1 1的結(jié)點(diǎn)，的結(jié)點(diǎn)，n2n2個(gè)度為個(gè)度為2 2的結(jié)的結(jié)點(diǎn)，點(diǎn)，nmnm個(gè)為個(gè)為mm結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)？結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)？解：設(shè)解：設(shè)n n為總結(jié)點(diǎn)個(gè)數(shù)，為總結(jié)點(diǎn)個(gè)數(shù)，n0n0為葉子結(jié)點(diǎn)為葉子結(jié)點(diǎn)( (即度為即度為0 0的結(jié)點(diǎn)個(gè)數(shù)的結(jié)點(diǎn)個(gè)數(shù)) )，那么有，那么有: : n=n0+n1+n2+nm (1) n=n0+n1+n2+nm (1)又有分支總數(shù)：又有分支總數(shù)：n-1=n1n-1=n1* *1+n21+n2* *2+n32+n3* *3+nm3+nm* *m (2)m (2)由于一個(gè)結(jié)

2、點(diǎn)對(duì)應(yīng)一個(gè)分支由于一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)分支式式(2)-(1)得得:1=n0-n2-2n3-(m-1)nm1=n0-n2-2n3-(m-1)nm那么有那么有:n0=1+n2+2n3+(m-1)nm:n0=1+n2+2n3+(m-1)nm練習(xí) 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1 那么T中的葉子數(shù)為證明：二叉樹度為二叉樹度為0的結(jié)點(diǎn)總比度為的結(jié)點(diǎn)總比度為2的結(jié)點(diǎn)多的結(jié)點(diǎn)多1個(gè)個(gè)由于二叉樹一切結(jié)點(diǎn)滴個(gè)數(shù)都不大于由于二叉樹一切結(jié)點(diǎn)滴個(gè)數(shù)都不大于2，所以結(jié)點(diǎn)總數(shù)，所以結(jié)點(diǎn)總數(shù)n=n0+n1+n2 (1)又由于度為又由于度為1和度為和度為2的結(jié)點(diǎn)分別有的結(jié)點(diǎn)分別有1個(gè)子樹和個(gè)子

3、樹和2個(gè)子樹，個(gè)子樹，所以，二叉樹中子樹結(jié)點(diǎn)就有所以，二叉樹中子樹結(jié)點(diǎn)就有n(子子=n1+2n2二叉樹中只需根節(jié)點(diǎn)不是子樹結(jié)點(diǎn)，所以二叉樹結(jié)點(diǎn)總二叉樹中只需根節(jié)點(diǎn)不是子樹結(jié)點(diǎn)，所以二叉樹結(jié)點(diǎn)總數(shù)數(shù)n=n(子子+1 即即 n=n1+2n2+1 (2)結(jié)合結(jié)合1式和式和2式就得式就得n0=n2+1練習(xí)1、具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有 個(gè)度為2的結(jié)點(diǎn) A8 B9 C10 Dll2、一棵具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度深度是 Alogn+1 Blogn+1 Clogn Dlogn-13、一棵樹高為K的完全二叉樹至少有 個(gè)結(jié)點(diǎn)。A2k 1 B. 2k-1 1 C. 2k-1 D. 2k例題例題6.2

4、6.2 寫出如圖寫出如圖6.26.2所示的二叉樹的前所示的二叉樹的前( (先先) )序中序和后序遍歷序列序中序和后序遍歷序列. .解：解：前序?yàn)榍靶驗(yàn)椤案笥遥瑥淖蟮接宜鸭那靶蛐蛄袨椋焊笥?，從左到右搜集的前序序列為：fdbacegihjfdbacegihj；中序?yàn)橹行驗(yàn)椤白蟾遥瑥淖蟮接宜鸭闹行蛐蛄袨椋鹤蟾?，從左到右搜集的中序序列為：abcdefghijabcdefghij；后序?yàn)楹笮驗(yàn)椤白笥腋?，從左到右搜集的后序序列為：左右根，從左到右搜集的后序序列為：acbedhjigfacbedhjigf。fdgibehjac練習(xí) 一棵二叉樹如下圖：寫出對(duì)此樹的先根、中跟、后跟序列。 先根序列:

5、ABDEFC 中根序列:DEFBAC 后根序列:FEDBCA知先序和中序求后序 先序：ABCDEFGH 中序：BDCEAFHG 后序：知中序和后序求先序 中序：BDCEAFHG 后序：DECBHGFA 求先序：問題 知先序和后序能求中序么?例題例題6.3 6.3 假設(shè)一棵二叉樹，左右子樹均有三個(gè)結(jié)點(diǎn)，其左子樹的前先假設(shè)一棵二叉樹，左右子樹均有三個(gè)結(jié)點(diǎn)，其左子樹的前先序序列與中序序列一樣，右子樹的中序序列與后序序列一樣，試構(gòu)序序列與中序序列一樣，右子樹的中序序列與后序序列一樣，試構(gòu)造該樹。造該樹?！窘狻繐?jù)題意，左子樹的前序序列與中序序列一樣，即有：【解】據(jù)題意，左子樹的前序序列與中序序列一樣，即

6、有： 前序：前序： 根根 左左 右右 中序：中序： 左左 根根 右右 也即，以左子樹為根的樹無左孩子。此處，右子樹的中序序列與后序也即，以左子樹為根的樹無左孩子。此處，右子樹的中序序列與后序序列一樣，即有：序列一樣，即有： 中序：中序： 左左 根根 右右 后序：后序： 左左 右右 根根 也即，以右子樹為根的樹無右孩子。由此構(gòu)造該樹如以下圖所示。也即，以右子樹為根的樹無右孩子。由此構(gòu)造該樹如以下圖所示。 例題例題4 4 一棵非空的二叉樹其先序序列和后序序列正好相反，畫出這棵二一棵非空的二叉樹其先序序列和后序序列正好相反，畫出這棵二叉樹的外形。叉樹的外形。解：先序遍歷為解：先序遍歷為“根左右，后序

7、遍歷為根左右，后序遍歷為“左右根。左右根。根結(jié)點(diǎn)在兩個(gè)序列中的位置分別在最前和最后，正好相反；因此，假設(shè)根結(jié)點(diǎn)在兩個(gè)序列中的位置分別在最前和最后，正好相反；因此，假設(shè)要兩個(gè)序列正好相反，那么左右子樹必有一個(gè)不存在。其先序序列和后要兩個(gè)序列正好相反，那么左右子樹必有一個(gè)不存在。其先序序列和后序序列正好相反的二叉樹必為單支樹。即這棵二叉樹的外形如以下圖所序序列正好相反的二叉樹必為單支樹。即這棵二叉樹的外形如以下圖所示示 。 例題例題6.5 知一棵完全二叉樹共有知一棵完全二叉樹共有892個(gè)結(jié)點(diǎn)，試求：個(gè)結(jié)點(diǎn)，試求： 樹的高度；樹的高度； 葉結(jié)點(diǎn)數(shù)；葉結(jié)點(diǎn)數(shù)； 單支單支(度為度為1)結(jié)點(diǎn)數(shù)；結(jié)點(diǎn)數(shù)；

8、最后一個(gè)非終端結(jié)點(diǎn)的序號(hào)。最后一個(gè)非終端結(jié)點(diǎn)的序號(hào)。解：解：(1) 根據(jù)性質(zhì)根據(jù)性質(zhì)2，知深度為，知深度為k的二叉樹至多有的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k1)，由，由于：于：29-1892 210-1，所以樹的高度為，所以樹的高度為10。(2) 對(duì)完全二叉樹來說，度為對(duì)完全二叉樹來說，度為1的結(jié)點(diǎn)只能是的結(jié)點(diǎn)只能是0或或1。由。由n=n0+n1+n2和和n0=n2+1性質(zhì)性質(zhì)3得：設(shè)得：設(shè)n1=0，那么有，那么有892=n0+0+n2=n2+1+n2=2n2+1，因得到的，因得到的n2=891/2不為整數(shù)而出錯(cuò)；不為整數(shù)而出錯(cuò)；n1=1，那么有，那么有892=n0+1+n2=n2+1+1

9、 +n2=2n2+2，得，得n2=445，代入，代入n0=n2+1得得n0=446；故葉結(jié)點(diǎn)數(shù)為；故葉結(jié)點(diǎn)數(shù)為446。(3) 由解過程可知由解過程可知n1=1 ，單支結(jié)點(diǎn)數(shù)為，單支結(jié)點(diǎn)數(shù)為1 。(4) 對(duì)有對(duì)有n個(gè)結(jié)點(diǎn)的完全二叉樹，最后一個(gè)樹葉結(jié)點(diǎn)，即序號(hào)為個(gè)結(jié)點(diǎn)的完全二叉樹，最后一個(gè)樹葉結(jié)點(diǎn)，即序號(hào)為n的葉的葉結(jié)點(diǎn)其雙親結(jié)點(diǎn)結(jié)點(diǎn)其雙親結(jié)點(diǎn)n/2為最后一個(gè)非終端結(jié)點(diǎn)，那么序號(hào)為為最后一個(gè)非終端結(jié)點(diǎn)，那么序號(hào)為892/2=446。此外，由可知：此外，由可知：n2=445n2=445，n1=1n1=1；那么最后一個(gè)非終端結(jié)點(diǎn)的序號(hào)為；那么最后一個(gè)非終端結(jié)點(diǎn)的序號(hào)為445+1=446445+1=44

10、6。對(duì)于還可以采用如下：因?qū)τ谶€可以采用如下：因89289229-129-1，那么前，那么前9 9層的結(jié)點(diǎn)數(shù)為層的結(jié)點(diǎn)數(shù)為29-29-1=5111=511個(gè)；而第個(gè)；而第1010層的結(jié)點(diǎn)為層的結(jié)點(diǎn)為892-511=381892-511=381個(gè)，且個(gè)，且381381個(gè)結(jié)點(diǎn)對(duì)應(yīng)第個(gè)結(jié)點(diǎn)對(duì)應(yīng)第9 9層層的父結(jié)點(diǎn)為的父結(jié)點(diǎn)為381/2=191381/2=191，而第，而第9 9層的其他結(jié)點(diǎn)也是葉結(jié)點(diǎn)，即層的其他結(jié)點(diǎn)也是葉結(jié)點(diǎn)，即29-29-1=2561=256，256-191=65256-191=65，故第，故第9 9層共有層共有6565個(gè)葉結(jié)點(diǎn)，那么第個(gè)葉結(jié)點(diǎn)，那么第1010層葉結(jié)點(diǎn)層葉結(jié)點(diǎn)+ +

11、第第9 9層葉結(jié)點(diǎn)層葉結(jié)點(diǎn)=381+65=446=381+65=446。例題例題6.6 6.6 對(duì)如以下圖所示的二叉樹對(duì)如以下圖所示的二叉樹: : 寫出對(duì)它們進(jìn)展先序中序和后序遍歷時(shí)得到的結(jié)點(diǎn)序列寫出對(duì)它們進(jìn)展先序中序和后序遍歷時(shí)得到的結(jié)點(diǎn)序列; ; 畫出它們的先序線索二叉樹和后序線索二叉樹。畫出它們的先序線索二叉樹和后序線索二叉樹?！窘狻俊窘狻繉?duì)圖進(jìn)展先序中序和后序遍歷時(shí)得到的對(duì)圖進(jìn)展先序中序和后序遍歷時(shí)得到的結(jié)點(diǎn)序列分別如下結(jié)點(diǎn)序列分別如下: :先序遍歷的結(jié)點(diǎn)序列為：先序遍歷的結(jié)點(diǎn)序列為：ABDFGHIECABDFGHIEC中序遍歷的結(jié)點(diǎn)序列為：中序遍歷的結(jié)點(diǎn)序列為：FDHGIBEACFD

12、HGIBEAC后序遍歷的結(jié)點(diǎn)序列為：后序遍歷的結(jié)點(diǎn)序列為：FHIGDEBCAFHIGDEBCAABCGDEHIF二叉樹的先序線索二叉樹如下左圖所示，后序線索二叉樹如下右圖所示。二叉樹的先序線索二叉樹如下左圖所示，后序線索二叉樹如下右圖所示。ABCGDEHIFNIL先序線索二叉樹先序線索二叉樹ABCGDEHIF后序線索二叉樹后序線索二叉樹NIL例題例題6.7 假設(shè)知森林的前序序列和后序序列分別為假設(shè)知森林的前序序列和后序序列分別為ABCDEFIGJH和和BDCAIFJGHE，請(qǐng)畫出該森林。，請(qǐng)畫出該森林。【解】由于森林的前序序列與其對(duì)應(yīng)的二叉樹前序序列一樣，而森林的【解】由于森林的前序序列與其對(duì)

13、應(yīng)的二叉樹前序序列一樣，而森林的后序序列與其對(duì)應(yīng)的二叉樹中序序列一樣。因此，根據(jù)二叉樹前序序后序序列與其對(duì)應(yīng)的二叉樹中序序列一樣。因此，根據(jù)二叉樹前序序列列ABCDEFIGJH和中序序列和中序序列BDCAIFJGHE可畫出二叉樹如以下圖所可畫出二叉樹如以下圖所示。示。ABEDCGJIFH而由二叉樹轉(zhuǎn)化為森林的步驟得到對(duì)應(yīng)的森林。而由二叉樹轉(zhuǎn)化為森林的步驟得到對(duì)應(yīng)的森林。ABDCEGJIFH例題例題6.8 6.8 證明證明n0n0個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2n0-12n0-1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。證明：設(shè)度為證明：設(shè)度為1 1和和2 2的結(jié)點(diǎn)個(gè)數(shù)分別為的結(jié)點(diǎn)個(gè)數(shù)分別為n1n1和和

14、 n2 n2，二叉樹結(jié)點(diǎn)總數(shù)為，二叉樹結(jié)點(diǎn)總數(shù)為n n，那么有：那么有：n=n0+n1+n2n=n0+n1+n2根據(jù)二叉樹的性質(zhì)知：根據(jù)二叉樹的性質(zhì)知：n0=n2+1n0=n2+1此外，由哈夫曼樹的構(gòu)造原理可知：哈夫曼樹不存在度為此外，由哈夫曼樹的構(gòu)造原理可知：哈夫曼樹不存在度為1 1的結(jié)點(diǎn)，即的結(jié)點(diǎn)，即n1=0n1=0；所以由可得：；所以由可得： n=n0+0+n2=n0+n0-1=2n0-1 n=n0+0+n2=n0+n0-1=2n0-1abcdefhgi601234578 bdefghi cdatafc 1 2 3 4 8 67 5 aCTree.r=0CTree.n=9例例6.9 用孩

15、子鏈表構(gòu)造表示西圖所示的樹用孩子鏈表構(gòu)造表示西圖所示的樹612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgiPCTree.r=1PCTree.r=1PCTree.n=9PCTree.n=9例例6.10 用帶雙親的孩子鏈表表示以下圖所示的用帶雙親的孩子鏈表表示以下圖所示的樹樹例6.11 用孩子兄弟表示法表示以下圖所示的樹(重點(diǎn)掌握)abcdefhgib d a c e f g h i與樹對(duì)應(yīng)的二叉樹表示其根結(jié)與樹對(duì)應(yīng)的二叉樹表示其根結(jié)點(diǎn)無右子樹。點(diǎn)無右子樹。1樹與二叉樹轉(zhuǎn)換ACBED樹ABCDE二叉樹 A B C D E

16、 A B C D E A B C D E 對(duì)應(yīng)存儲(chǔ)存儲(chǔ)解釋解釋例6.12 森林、樹與二叉樹轉(zhuǎn)換以二叉鏈表為紐帶森林轉(zhuǎn)換成二叉樹森林轉(zhuǎn)換成二叉樹將各棵樹分別轉(zhuǎn)換成二叉樹根結(jié)點(diǎn)均無右孩子；將各棵樹分別轉(zhuǎn)換成二叉樹根結(jié)點(diǎn)均無右孩子；將各二叉樹的根結(jié)點(diǎn)依次用分支線連起來；將各二叉樹的根結(jié)點(diǎn)依次用分支線連起來；以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹型構(gòu)造。叉樹型構(gòu)造。森林轉(zhuǎn)化成二叉樹的過程森林轉(zhuǎn)化成二叉樹的過程: :ABCDEFGHIJ森林森林ABCDEFGHIJ對(duì)應(yīng)二叉樹對(duì)應(yīng)二叉樹ABCDEFGHIJAB

17、CDEFGHIJ銜接跟結(jié)點(diǎn)銜接跟結(jié)點(diǎn)旋轉(zhuǎn)成二叉樹旋轉(zhuǎn)成二叉樹例例6.13 6.13 二叉樹轉(zhuǎn)換成森林二叉樹轉(zhuǎn)換成森林抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的一切右孩子間抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的一切右孩子間連線全部抹掉，使之變成孤立的二叉樹連線全部抹掉，使之變成孤立的二叉樹復(fù)原：將孤立的二叉樹復(fù)原成樹復(fù)原：將孤立的二叉樹復(fù)原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ例例6.14 Huffman6.14 Huffman編碼設(shè)計(jì)實(shí)例編碼設(shè)計(jì)實(shí)例知某系統(tǒng)在通訊聯(lián)絡(luò)中只能夠出現(xiàn)知某系統(tǒng)在通訊聯(lián)絡(luò)中只能夠出現(xiàn)8 8種

18、字符，其概率分別為種字符，其概率分別為0.050.05， 0.290.29，0.070.07，0.080.08，0.140.14， 0.23 0.23，0.030.03，0.110.11，試設(shè)計(jì)，試設(shè)計(jì)HuffmanHuffman編編碼。碼。解一：先構(gòu)造解一：先構(gòu)造HuffmanHuffman樹，再進(jìn)展編碼。樹，再進(jìn)展編碼。 Huffman Huffman編碼實(shí)現(xiàn)過程：以報(bào)文所用的不同字符為葉結(jié)點(diǎn)，以字符編碼實(shí)現(xiàn)過程：以報(bào)文所用的不同字符為葉結(jié)點(diǎn)，以字符出現(xiàn)頻率為權(quán)重構(gòu)造出現(xiàn)頻率為權(quán)重構(gòu)造HuffmanHuffman樹；然后將樹中結(jié)點(diǎn)指向其左孩子的樹；然后將樹中結(jié)點(diǎn)指向其左孩子的分支標(biāo)分支標(biāo)“

19、0 0，指向其右孩子的分支標(biāo)，指向其右孩子的分支標(biāo)“1 1；每個(gè)字符的編碼即為從；每個(gè)字符的編碼即為從根到每個(gè)葉子字符的途徑上得到的根到每個(gè)葉子字符的途徑上得到的0 0、1 1序列。這種對(duì)字符的編序列。這種對(duì)字符的編碼就是碼就是HuffmanHuffman編碼。編碼。1135819234229148715295810001000011100111 HC 1 01102 10 3 11104 11115 110 6 00 7 01118 011 HuffmanHuffman編碼編碼HuffmanHuffman樹樹解二：利用解二：利用HuffmanHuffman編碼算法實(shí)現(xiàn)。根據(jù)題意，取編碼算法實(shí)

20、現(xiàn)。根據(jù)題意，取8 8個(gè)字符的權(quán)分別為個(gè)字符的權(quán)分別為5 5，2929，7 7，8 8，1414，2323，3 3，1111，n=8n=8，那么，那么m=2m=2* *8-1=158-1=15，按上，按上述算法可構(gòu)造一棵述算法可構(gòu)造一棵HuffmanHuffman樹，如下左圖和右圖分別樹，如下左圖和右圖分別HuffmanHuffman樹的樹的初始形狀和終止形狀。初始形狀和終止形狀。 weightparentlchildrchild150002290003700048000514000623000730008110009000100001100012000130001400015000 weightparentlchildrch