1、例題6.1 已知一棵度為m的樹有n1個度為1的結點，n2個度為2的結點，nm個為m結點，問該樹中有多少個葉子結點？ 解：設n為總結點個數(shù)，n0為葉子結點(即度為0的結點個數(shù))，則有: n=n0+n1+n2+nm (1) 又有（分支總數(shù)）：n-1=n1*1+n2*2+n3*3+nm*m (2) （因為一個結點對應一個分支） 式(2)-(1)得: 1=n0-n2-2n3-(m-1)nm 則有:n0=1+n2+2n3+(m-1)nm,練習,設樹T的度為4，其中度為1，2，3和4的結點個數(shù)分別為4，2，1，1 則T中的葉子數(shù)為,證明：,二叉樹度為0的結點總比度為2的結點多1個 因為二叉樹所有結點滴個數(shù)

2、都不大于2，所以結點總數(shù)n=n0+n1+n2 (1) 又因為度為1和度為2的結點分別有1個子樹和2個子樹，所以，二叉樹中子樹結點就有n(子）=n1+2n2 二叉樹中只有根節(jié)點不是子樹結點，所以二叉樹結點總數(shù)n=n(子）+1 即 n=n1+2n2+1 (2) 結合（1）式和（2）式就得n0=n2+1,練習,1、具有10個葉結點的二叉樹中有（ ）個度為2的結點 A8 B9 C10 Dll 2、一棵具有 n個結點的完全二叉樹的樹高度（深度）是（ ） Alogn+1 Blogn+1 Clogn Dlogn-1 3、一棵樹高為K的完全二叉樹至少有（ ）個結點。 A2k 1 B. 2k-1 1 C. 2k

3、-1 D. 2k,例題6.2 寫出如圖6.2所示的二叉樹的前(先)序中序和后序遍歷序列. 解： 前序為“根左右”，從左到右收集的前序序列為：fdbacegihj； 中序為“左根右”，從左到右收集的中序序列為：abcdefghij； 后序為“左右根”，從左到右收集的后序序列為：acbedhjigf。,練習,一棵二叉樹如圖所示：寫出對此樹的先根、中跟、后跟序列。,先根序列:ABDEFC 中根序列:DEFBAC 后根序列:FEDBCA,已知先序和中序求后序,先序：ABCDEFGH 中序：BDCEAFHG 后序：,已知中序和后序求先序,中序：BDCEAFHG 后序：DECBHGFA 求先序：,問題,已

4、知先序和后序能求中序么?,例題6.3 若一棵二叉樹，左右子樹均有三個結點，其左子樹的前（先）序序列與中序序列相同，右子樹的中序序列與后序序列相同，試構造該樹。 【解】據(jù)題意，左子樹的前序序列與中序序列相同，即有： 前序： 根 左 右 中序： 左 根 右 也即，以左子樹為根的樹無左孩子。此處，右子樹的中序序列與后序序列相同，即有： 中序： 左 根 右 后序： 左 右 根 也即，以右子樹為根的樹無右孩子。由此構造該樹如下圖所示。,例題4 一棵非空的二叉樹其先序序列和后序序列正好相反，畫出這棵二叉樹的形狀。 解：先序遍歷為“根左右”，后序遍歷為“左右根”。 根結點在兩個序列中的位置分別在最前和最后，

5、正好相反；因此，若要兩個序列正好相反，則左右子樹必有一個不存在。其先序序列和后序序列正好相反的二叉樹必為單支樹。即這棵二叉樹的形狀如下圖所示 。,例題6.5 已知一棵完全二叉樹共有892個結點，試求： 樹的高度； 葉結點數(shù)； 單支(度為1)結點數(shù)； 最后一個非終端結點的序號。 解：(1) 根據(jù)性質2，已知深度為k的二叉樹至多有2k-1個結點(k1)，由于：29-1892 210-1，所以樹的高度為10。 (2) 對完全二叉樹來說，度為1的結點只能是0或1。由n=n0+n1+n2和n0=n2+1（性質3）得：設n1=0，則有892=n0+0+n2=n2+1+n2=2n2+1，因得到的n2=891

6、/2不為整數(shù)而出錯；n1=1，則有892=n0+1+n2=n2+1+1 +n2=2n2+2，得n2=445，代入n0=n2+1得n0=446；故葉結點數(shù)為446。 (3) 由解過程可知n1=1 ，單支結點數(shù)為1 。 (4) 對有n個結點的完全二叉樹，最后一個樹葉結點，即序號為n的葉結點其雙親結點n/2為最后一個非終端結點，則序號為892/2=446。,此外，由可知：n2=445，n1=1；則最后一個非終端結點的序號為445+1=446。 對于還可以采用如下：因89229-1，則前9層的結點數(shù)為29-1=511個；而第10層的結點為892-511=381個，且381個結點對應第9層的父結點為38

7、1/2=191，而第9層的其余結點也是葉結點，即29-1=256，256-191=65，故第9層共有65個葉結點，則第10層葉結點+第9層葉結點=381+65=446。,例題6.6 對如下圖所示的二叉樹: 寫出對它們進行先序中序和后序遍歷時得到的結點序列; 畫出它們的先序線索二叉樹和后序線索二叉樹。,【解】 對圖進行先序中序和后序遍歷時得到的結點序列分別如下: 先序遍歷的結點序列為：ABDFGHIEC 中序遍歷的結點序列為：FDHGIBEAC 后序遍歷的結點序列為：FHIGDEBCA,二叉樹的先序線索二叉樹如下左圖所示，后序線索二叉樹如下右圖所示。,NIL,先序線索二叉樹,例題6.7 如果已知

8、森林的前序序列和后序序列分別為ABCDEFIGJH和BDCAIFJGHE，請畫出該森林。 【解】由于森林的前序序列與其對應的二叉樹前序序列相同，而森林的后序序列與其對應的二叉樹中序序列相同。因此，根據(jù)二叉樹前序序列ABCDEFIGJH和中序序列BDCAIFJGHE可畫出二叉樹如下圖所示。,而由二叉樹轉化為森林的步驟得到對應的森林。,例題6.8 證明n0個葉子結點的哈夫曼樹共有2n0-1個結點。 證明：設度為1和2的結點個數(shù)分別為n1和 n2，二叉樹結點總數(shù)為n，則有：n=n0+n1+n2 根據(jù)二叉樹的性質知：n0=n2+1 此外，由哈夫曼樹的構造原理可知：哈夫曼樹不存在度為1的結點，即n1=0

9、；所以由可得： n=n0+0+n2=n0+n0-1=2n0-1,a,CTree.r=0 CTree.n=9,例6.9 用孩子鏈表結構表示西圖所示的樹,PCTree.r=1 PCTree.n=9,例6.10 用帶雙親的孩子鏈表表示下圖所示的樹,例6.11 用孩子兄弟表示法表示下圖所示的樹(重點掌握),與樹對應的二叉樹表示其根結點無右子樹。,（1）樹與二叉樹轉換,例6.12 森林、樹與二叉樹轉換（以二叉鏈表為紐帶）,森林轉換成二叉樹 將各棵樹分別轉換成二叉樹（根結點均無右孩子）； 將各二叉樹的根結點依次用分支線連起來； 以第一棵樹根結點為二叉樹的根，再以根結點為軸心，順時針旋轉，構成二叉樹型結構。

10、 森林轉化成二叉樹的過程:,連接跟結點,旋轉成二叉樹,例6.13 二叉樹轉換成森林 抹線：將二叉樹中根結點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹 還原：將孤立的二叉樹還原成樹,例6.14 Huffman編碼設計實例,已知某系統(tǒng)在通信聯(lián)絡中只可能出現(xiàn)8種字符，其概率分別為0.05， 0.29，0.07，0.08，0.14， 0.23，0.03，0.11，試設計Huffman編碼。 解一：先構造Huffman樹，再進行編碼。 Huffman編碼實現(xiàn)過程：以報文所用的不同字符為葉結點，以字符出現(xiàn)頻率為權重構造Huffman樹；然后將樹中結點指向其左孩子的分支

11、標“0”，指向其右孩子的分支標“1”；每個字符的編碼即為從根到每個葉子（字符）的路徑上得到的0、1序列。這種對字符的編碼就是Huffman編碼。,Huffman編碼,Huffman樹,解二：利用Huffman編碼算法實現(xiàn)。根據(jù)題意，取8個字符的權分別為（5，29，7，8，14，23，3，11），n=8，則m=2*8-1=15，按上述算法可構造一棵Huffman樹，如下左圖和右圖分別Huffman樹的初始狀態(tài)和終止狀態(tài)。,HT初始狀態(tài),HT終止狀態(tài),Huffman編碼,Huffman樹,3. 樹的遍歷 遍歷：按一定搜索路經走遍樹的各個頂點，使樹中每一結點均被且僅被訪問一次。 目的：產生樹中所有結點的一個線性排列。 常用方法： 先根（序）遍歷：先訪問樹的根結點，然后依次先根遍歷根的每棵子樹。 后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結點。 按層次遍歷：先訪問第一層上的結點，然后依次遍歷第二層，直到最后一層的結點。,先序遍歷