例題6.1

已知一棵度為m的樹有n1個度為1的結點，n2個度為2的結點，…，nm個為m結點，問該樹中有多少個葉子結點？解：設n為總結點個數，n0為葉子結點(即度為0的結點個數)，則有:n=n0+n1+n2+…+nm(1)又有（分支總數）：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的結點個數分別為4，2，1，1則T中的葉子數為練習1、具有10個葉結點的二叉樹中有（

）個度為2的結點

A．8B．9C．10D．ll2、一棵具有n個結點的完全二叉樹的樹高度（深度）是（

）A．logn+1B．logn+1C．lognD．logn-13、一棵樹高為K的完全二叉樹至少有（

）個結點。A．2k

–1B.2k-1

–1C.2k-1D.2k例題6.2寫出如圖6.2所示的二叉樹的前(先)序﹑中序和后序遍歷序列.解：⑴前序為“根左右”，從左到右收集的前序序列為：fdbacegihj；⑵中序為“左根右”，從左到右收集的中序序列為：abcdefghij；⑶后序為“左右根”，從左到右收集的后序序列為：acbedhjigf。fdgibehjac練習一棵二叉樹如圖所示：寫出對此樹的先根、中跟、后跟序列。先根序列:ABDEFC中根序列:DEFBAC后根序列:FEDBCA已知先序和中序求后序先序：ABCDEFGH中序：BDCEAFHG后序：已知中序和后序求先序中序：BDCEAFHG后序：DECBHGFA求先序：例題6.5已知一棵完全二叉樹共有892個結點，試求：⑴樹的高度；⑵葉結點數；⑶單支(度為1)結點數；⑷最后一個非終端結點的序號。解：(1)根據性質2，已知深度為k的二叉樹至多有2k-1個結點(k≥1)，由于：29-1﹤892﹤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/2不為整數而出錯；n1=1，則有892=n0+1+n2=n2+1+1+n2=2n2+2，得n2=445，代入n0=n2+1得n0=446；故葉結點數為446。(3)

由⑵解過程可知n1=1，單支結點數為1。(4)對有n個結點的完全二叉樹，最后一個樹葉結點，即序號為n的葉結點其雙親結點[n/2]為最后一個非終端結點，則序號為892/2=446。此外，由⑵可知：n2=445，n1=1；則最后一個非終端結點的序號為445+1=446。對于⑵還可以采用如下：因892﹥29-1，則前9層的結點數為29-1=511個；而第10層的結點為892-511=381個，且381個結點對應第9層的父結點為[381/2]=191，而第9層的其余結點也是葉結點，即29-1=256，256-191=65，故第9層共有65個葉結點，則第10層葉結點+第9層葉結點=381+65=446。例題6.6

對如下圖所示的二叉樹:⑴寫出對它們進行先序﹑中序和后序遍歷時得到的結點序列;⑵畫出它們的先序線索二叉樹和后序線索二叉樹。【解】對圖進行先序﹑中序和后序遍歷時得到的結點序列分別如下:先序遍歷的結點序列為：ABDFGHIEC中序遍歷的結點序列為：FDHGIBEAC后序遍歷的結點序列為：FHIGDEBCAABCGDEHIF二叉樹的先序線索二叉樹如下左圖所示，后序線索二叉樹如下右圖所示。ABCGDEHIFNIL先序線索二叉樹ABCGDEHIF后序線索二叉樹NIL例題6.7如果已知森林的前序序列和后序序列分別為ABCDEFIGJH和BDCAIFJGHE，請畫出該森林。【解】由于森林的前序序列與其對應的二叉樹前序序列相同，而森林的后序序列與其對應的二叉樹中序序列相同。因此，根據二叉樹前序序列ABCDEFIGJH和中序序列BDCAIFJGHE可畫出二叉樹如下圖所示。ABEDCGJIFH而由二叉樹轉化為森林的步驟得到對應的森林。ABDCEGJIFH例題6.8證明n0個葉子結點的哈夫曼樹共有2n0-1個結點。證明：設度為1和2的結點個數分別為n1和n2，二叉樹結點總數為n，則有：n=n0+n1+n2根據二叉樹的性質知：n0=n2+1此外，由哈夫曼樹的構造原理可知：哈夫曼樹不存在度為1的結點，即n1=0；所以由①②可得：

n=n0+0+n2=n0+n0-1=2n0-1abcdefhgi601234578

bdefghi

cdatafc12^34^^867^5^^^^

a^CTree.r=0CTree.n=9例6.9用孩子鏈表結構表示西圖所示的樹612345789acdefghibdatafc23459786^^^^^^^^^012235551parentabcdefhgiPCTree.r=1PCTree.n=9例6.10用帶雙親的孩子鏈表表示下圖所示的樹例6.11用孩子兄弟表示法表示下圖所示的樹(重點掌握)abcdefhgibda^c^^e^f^^g^h^i^^與樹對應的二叉樹表示其根結點無右子樹。森林轉換成二叉樹將各棵樹分別轉換成二叉樹（根結點均無右孩子）；將各二叉樹的根結點依次用分支線連起來；以第一棵樹根結點為二叉樹的根，再以根結點為軸心，順時針旋轉，構成二叉樹型結構。森林轉化成二叉樹的過程:ABCDEFGHIJ森林ABCDEFGHIJ對應二叉樹ABCDEFGHIJABCDEFGHIJ連接跟結點旋轉成二叉樹例6.13二叉樹轉換成森林抹線：將二叉樹中根結點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ例6.14Huffman編碼設計實例已知某系統在通信聯絡中只可能出現8種字符，其概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設計Huffman編碼。解一：先構造Huffman樹，再進行編碼。

Huffman編碼實現過程：以報文所用的不同字符為葉結點，以字符出現頻率為權重構造Huffman樹；然后將樹中結點指向其左孩子的分支標“0”，指向其右孩子的分支標“1”；每個字符的編碼即為從根到每個葉子（字符）的路徑上得到的0、1序列。這種對字符的編碼就是Huffman編碼。1135819234229148715295810001000011100111

HC

1

01102

10

3

11104

11115

110

6

00

7

01118

011

Huffman編碼Huffman樹解二：利用Huffman編碼算法實現。根據題意，取8個字符的權分別為（5，29，7，8，14，23，3，11），n=8，則m=2*8-1=15，按上述算法可構造一棵Huffman樹，如下左圖和右圖分別Huffman樹的初始狀態和終止狀態。

weightparentlchildrchild150002290003700048000514000623000730008110009000100001100012000130001400015000

weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458152141510001314HT初始狀態HT終止狀態1135819234229148715295810001000011100111

HC

1

01102

10

3

11104

11115

110

6

00

7

01118

011

Huffman編碼Huffman樹3.樹的遍歷遍歷：按一定搜索路經走遍樹的各個頂點，使樹中每一結點均被且僅被訪問一次。目的：產生樹中所有結點的一個線性排列。常用方法：先根（序）遍歷：先訪問樹的根結點，然后依次先根遍歷根的每棵子樹。后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結點。按層次遍歷：先訪問第一層上的結點，然后依次遍歷第二