第7章樹形結(jié)構(gòu)(最新修改)

1、第第7 7章章 樹形結(jié)構(gòu)樹形結(jié)構(gòu)7.1 7.1 樹的基本概念樹的基本概念 7.2 7.2 二叉樹概念和性質(zhì)二叉樹概念和性質(zhì)7.3 7.3 二叉樹存儲結(jié)構(gòu)二叉樹存儲結(jié)構(gòu)7.4 7.4 二叉樹的遍歷二叉樹的遍歷7.5 7.5 二叉樹的基本運算及其實現(xiàn)二叉樹的基本運算及其實現(xiàn)7.6 7.6 二叉樹的構(gòu)造二叉樹的構(gòu)造7.8 7.8 哈夫曼樹哈夫曼樹 本章小結(jié)本章小結(jié)7.7 7.7 線索二叉樹線索二叉樹7.9 7.9 并查集并查集 7.1 7.1 樹的基本概念樹的基本概念 7.1.1 7.1.1 樹的定義樹的定義 7.1.3 7.1.3 樹的基本術(shù)語樹的基本術(shù)語 7.1.2 7.1.2 樹的表示樹的表示

2、7.1.4 7.1.4 樹的性質(zhì)樹的性質(zhì)7.1.5 7.1.5 樹的基本運算樹的基本運算7.1.6 7.1.6 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)可分為可分為線性結(jié)構(gòu)線性結(jié)構(gòu)和和非線性結(jié)構(gòu)非線性結(jié)構(gòu)兩大類。在第兩大類。在第3，4，5章章討論的都是線性結(jié)構(gòu)，本章和下一章討論非線性結(jié)構(gòu)。討論的都是線性結(jié)構(gòu)，本章和下一章討論非線性結(jié)構(gòu)。 線性結(jié)構(gòu)線性結(jié)構(gòu)(線性表線性表, 棧棧,隊列等隊列等)：數(shù)據(jù)元素之間是一對一的關(guān)系，：數(shù)據(jù)元素之間是一對一的關(guān)系，除了第一個數(shù)據(jù)元素外，其它每個元素都有且只有一個直接前驅(qū)；除了第一個數(shù)據(jù)元素外，其它每個元素都有且只有一個直接前驅(qū)；除了最后一個數(shù)據(jù)元素，其它每個

3、元素都有且只有一個直接后繼。除了最后一個數(shù)據(jù)元素，其它每個元素都有且只有一個直接后繼。 非線性結(jié)構(gòu)非線性結(jié)構(gòu): 至少存在一個數(shù)據(jù)元素有不止一個直接前驅(qū)或后至少存在一個數(shù)據(jù)元素有不止一個直接前驅(qū)或后繼繼(樹樹,圖等圖等)7.1 樹的定義以及相關(guān)術(shù)語樹的定義以及相關(guān)術(shù)語BADEFGIHCa一個結(jié)點的樹一個結(jié)點的樹3. 廣義表表示法廣義表表示法(A(B(D),C)4.樹的形式化表示方法樹的形式化表示方法 樹的形式化表示法主要用于樹的理論描述。樹的形式化表示樹的形式化表示法主要用于樹的理論描述。樹的形式化表示法定義樹法定義樹T為為T=(D,R)。其中。其中D為為T中結(jié)點的集合，中結(jié)點的集合，R為樹為樹

4、T中結(jié)中結(jié)點之間關(guān)系的集合。例如右圖所示的樹用形式化表示方法表示點之間關(guān)系的集合。例如右圖所示的樹用形式化表示方法表示如下：如下： , （b b）樹的基本術(shù)語）樹的基本術(shù)語1. 1. 樹的結(jié)點樹的結(jié)點: :數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針合起來稱作結(jié)點針合起來稱作結(jié)點; ;2. 2. 結(jié)點的度結(jié)點的度: :一個結(jié)點擁有的子樹的個數(shù)一個結(jié)點擁有的子樹的個數(shù), ,稱作該結(jié)稱作該結(jié)點的度；點的度；3.3.葉子結(jié)點葉子結(jié)點：度為零的結(jié)點稱為：度為零的結(jié)點稱為葉結(jié)點葉結(jié)點; ;4.4.孩子結(jié)點，雙親結(jié)點孩子結(jié)點，雙親結(jié)點：樹中一個結(jié)點的子樹的根結(jié)：樹中一個結(jié)點的子樹

5、的根結(jié)點稱作這個結(jié)點的孩子結(jié)點，相應(yīng)地，該結(jié)點稱為孩點稱作這個結(jié)點的孩子結(jié)點，相應(yīng)地，該結(jié)點稱為孩子的雙親結(jié)點；子的雙親結(jié)點；5.5.兄弟結(jié)點，堂兄弟結(jié)點兄弟結(jié)點，堂兄弟結(jié)點：具有相同的雙親結(jié)點稱為：具有相同的雙親結(jié)點稱為兄弟結(jié)點；其雙親在同一層的結(jié)點互為堂兄弟結(jié)點；兄弟結(jié)點；其雙親在同一層的結(jié)點互為堂兄弟結(jié)點；6.6.祖先結(jié)點祖先結(jié)點：從根結(jié)點到樹中某結(jié)點所經(jīng)過的所有分：從根結(jié)點到樹中某結(jié)點所經(jīng)過的所有分支結(jié)點稱作該結(jié)點的祖先結(jié)點；支結(jié)點稱作該結(jié)點的祖先結(jié)點；7.7.子孫結(jié)點子孫結(jié)點：某一結(jié)點的所有孩子結(jié)點，以及這些孩：某一結(jié)點的所有孩子結(jié)點，以及這些孩子結(jié)點的孩子結(jié)點稱為該結(jié)點的子孫結(jié)點；

6、子結(jié)點的孩子結(jié)點稱為該結(jié)點的子孫結(jié)點；8. 8. 樹的度樹的度: :樹中所有結(jié)點的度的最大值稱為該樹的度；樹中所有結(jié)點的度的最大值稱為該樹的度； 含義含義: :樹中最大分支數(shù)為樹的度樹中最大分支數(shù)為樹的度; ;9. 9. 結(jié)點的層次結(jié)點的層次: :從根結(jié)點到樹中某結(jié)點所經(jīng)路徑上的從根結(jié)點到樹中某結(jié)點所經(jīng)路徑上的分支數(shù)稱為該結(jié)點的層次。分支數(shù)稱為該結(jié)點的層次。10.10.樹的深度樹的深度：樹中結(jié)點的最大層次稱為樹的深度或：樹中結(jié)點的最大層次稱為樹的深度或高度高度11.11.無序樹，有序樹無序樹，有序樹：如果將樹中結(jié)點的各子樹看成：如果將樹中結(jié)點的各子樹看成從左到右是有次序的（即不能互換），則稱該

7、樹為有從左到右是有次序的（即不能互換），則稱該樹為有序樹，否則稱為無序樹。序樹，否則稱為無序樹。12.12.森林森林: :是是m(m=0)m(m=0)棵互不相交的樹的集合?？没ゲ幌嘟坏臉涞募?。 7.2 二叉樹二叉樹 二叉樹是另外一種樹形結(jié)構(gòu)，它的特點是每個結(jié)點至二叉樹是另外一種樹形結(jié)構(gòu)，它的特點是每個結(jié)點至多只有兩棵子樹（即二叉樹中不存在大于多只有兩棵子樹（即二叉樹中不存在大于2的結(jié)點），并的結(jié)點），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。由且，二叉樹的子樹有左右之分，其次序不能任意顛倒。由于二叉樹的左右子樹也是二叉樹，則由二叉樹的定義，它于二叉樹的左右子樹也是二叉樹，則由二叉樹的

8、定義，它們也可以是空樹，由此，二叉樹可以有五種基本形態(tài)，如們也可以是空樹，由此，二叉樹可以有五種基本形態(tài)，如下圖所示。下圖所示。（1）二叉樹的定義）二叉樹的定義二叉樹的二叉樹的5種基本形態(tài)種基本形態(tài)（2）滿二叉樹和完全二叉樹的定義）滿二叉樹和完全二叉樹的定義1243567滿二叉樹：在一棵二叉樹中，如果所滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，有分支結(jié)點都存在左子樹和右子樹，并且所有葉子結(jié)點都在同一層上。并且所有葉子結(jié)點都在同一層上。124356完全二叉樹：如果一棵具完全二叉樹：如果一棵具有有n個結(jié)點的二叉樹的結(jié)構(gòu)個結(jié)點的二叉樹的結(jié)構(gòu)與滿二叉樹的前與滿二叉樹的前n個結(jié)點的

9、個結(jié)點的結(jié)構(gòu)相同，這樣的二叉樹稱結(jié)構(gòu)相同，這樣的二叉樹稱作完全二叉樹。作完全二叉樹。（3）二叉樹的性質(zhì)）二叉樹的性質(zhì) 性質(zhì)性質(zhì)1： 若規(guī)定根結(jié)點的層次為若規(guī)定根結(jié)點的層次為1，則一顆非空二叉樹的第，則一顆非空二叉樹的第i層層上最多有上最多有2i-1（i=1)個結(jié)點。個結(jié)點。 該性質(zhì)可以用數(shù)許歸納法來證明：該性質(zhì)可以用數(shù)許歸納法來證明：第一步：當(dāng)層次第一步：當(dāng)層次n=1是，二叉樹在根結(jié)點只有一個結(jié)點，是，二叉樹在根結(jié)點只有一個結(jié)點，21-1=1，結(jié)論成立；結(jié)論成立；第二步：假設(shè)當(dāng)層次第二步：假設(shè)當(dāng)層次n=t時結(jié)論成立，即在第時結(jié)論成立，即在第t層上最多有層上最多有2t-1個結(jié)個結(jié)點；點；第三步：

10、當(dāng)層次第三步：當(dāng)層次n=t+1時，根據(jù)二叉樹的定義，第時，根據(jù)二叉樹的定義，第t層上的每個結(jié)層上的每個結(jié)點最多有點最多有2個子結(jié)點，所以在第個子結(jié)點，所以在第t+1成上最多有成上最多有2*2t-1=2(t+1)-1個結(jié)點。個結(jié)點。因此，結(jié)論成立。因此，結(jié)論成立。性質(zhì)性質(zhì)2： 若規(guī)定空樹的深度為若規(guī)定空樹的深度為0，則，則深度為深度為h的二叉樹最大結(jié)點個數(shù)的二叉樹最大結(jié)點個數(shù)（至多）是（至多）是2h-1個結(jié)點（個結(jié)點（h00)。證明：證明： 當(dāng)深度為當(dāng)深度為=0時是空二叉樹，空二叉樹應(yīng)當(dāng)一個結(jié)點也沒有；時是空二叉樹，空二叉樹應(yīng)當(dāng)一個結(jié)點也沒有； 當(dāng)深度當(dāng)深度h0時是非空二叉樹，要求最大結(jié)點個數(shù)，

11、只要該時是非空二叉樹，要求最大結(jié)點個數(shù)，只要該二叉樹的每一層都達到最大，這樣，可以利用性質(zhì)二叉樹的每一層都達到最大，這樣，可以利用性質(zhì)1來計算，來計算，計算過程如下：計算過程如下： i=02i-1=2h-1h第第6層就是滿的，且第層就是滿的，且第6層的最后八個結(jié)點沒有孩子結(jié)點，其它的層的最后八個結(jié)點沒有孩子結(jié)點，其它的都有左右孩子結(jié)點。都有左右孩子結(jié)點。 26163第第6層上最多有層上最多有2i12612532 32824 24*2=48 48+63=111性質(zhì)性質(zhì)3：對任何一顆二叉樹對任何一顆二叉樹T，如果其終端結(jié)點數(shù)如果其終端結(jié)點數(shù) 為為n0,度為度為2的結(jié)點的結(jié)點數(shù)為數(shù)為n2，則則n0=

12、n2+1. 證明：設(shè)二叉樹度為證明：設(shè)二叉樹度為1的結(jié)點個數(shù)為的結(jié)點個數(shù)為n1，二叉樹的結(jié)點總數(shù)為二叉樹的結(jié)點總數(shù)為n， 則有：則有： n=n0+n1+n2 具有具有n個結(jié)點的二叉樹共有個結(jié)點的二叉樹共有n-1個分支，這個分支，這n-1個分支分別是由度為個分支分別是由度為1和度為和度為2的結(jié)點發(fā)出的，其中每個度為的結(jié)點發(fā)出的，其中每個度為1的結(jié)點發(fā)出一個分支，度的結(jié)點發(fā)出一個分支，度為為2的結(jié)點發(fā)出的結(jié)點發(fā)出2個分支，因此，有個分支，因此，有 n-1=0*n0+1*n1+2*n2.由由1.2.兩個方程，可以得到兩個方程，可以得到 n0=n2+1。舉例：證明由舉例：證明由n個葉子結(jié)點的哈夫曼樹共

13、有個葉子結(jié)點的哈夫曼樹共有2n-1個結(jié)點。個結(jié)點。 設(shè)二叉樹中所有非葉子結(jié)點均有非空左右設(shè)二叉樹中所有非葉子結(jié)點均有非空左右子二叉樹，并且葉子結(jié)點數(shù)目為子二叉樹，并且葉子結(jié)點數(shù)目為n，問：二，問：二叉樹中共有多少個結(jié)點？叉樹中共有多少個結(jié)點？ n+n2=m (1) 2n2=m-1 (2) 聯(lián)合（聯(lián)合（1）（）（2），解方程可得：），解方程可得： m=2n-1性質(zhì)性質(zhì)4： 具有具有n(n0)個結(jié)點的完全二叉樹的深度個結(jié)點的完全二叉樹的深度k不超過不超過ln2(n+1)證明：由性質(zhì)證明：由性質(zhì)2和完全二叉樹的定義可知，對于有和完全二叉樹的定義可知，對于有n個結(jié)點的深度個結(jié)點的深度為為k的完全二叉樹

14、有的完全二叉樹有 2k-1-1n=2k-1 2k-1n+1=2k k-1log2(n+1)1,i1,則其雙親則其雙親PARENT(i)PARENT(i)是結(jié)點是結(jié)點i/2.i/2. 2) 2)如果如果2in,2in,則結(jié)點則結(jié)點i i左孩子結(jié)點序號未左孩子結(jié)點序號未2i2i；否則序號為否則序號為i i的結(jié)點無左孩子的結(jié)點無左孩子; ; 3) 3)如果如果2i+1n2i+1n，則結(jié)點，則結(jié)點i i的右孩子結(jié)點的序號為的右孩子結(jié)點的序號為2i2i1 1；否則沒有右孩子。否則沒有右孩子。(4)二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 1）順序存儲結(jié)構(gòu)）順序存儲結(jié)構(gòu)ABDCEFGA B C D E F G 0

15、 1 2 3 4 5 6ABDCEFG 在最壞的情況下，一個深度為在最壞的情況下，一個深度為k并且只有并且只有k個結(jié)點的個結(jié)點的一路右偏的單支樹（樹中不存在度為一路右偏的單支樹（樹中不存在度為2的結(jié)點）卻需要的結(jié)點）卻需要長度為長度為2k-1的的 一維數(shù)組。一維數(shù)組。 結(jié)論：順序存儲適合完全二叉樹（當(dāng)然包括滿二叉結(jié)論：順序存儲適合完全二叉樹（當(dāng)然包括滿二叉樹。）樹。）AB C D E0 000 F G0 1 2 3 4 5 6 7 8 9 10 深度為深度為h的二叉樹，以一維數(shù)組的二叉樹，以一維數(shù)組BT12h-1作為存儲結(jié)構(gòu)。編寫一算法，作為存儲結(jié)構(gòu)。編寫一算法，求該二叉樹的葉子結(jié)點的個數(shù)。求

16、該二叉樹的葉子結(jié)點的個數(shù)。 【北航【北航1996】 int leafcount(int BT,ing h) len=pow(2,h); /計算出結(jié)點的個數(shù)計算出結(jié)點的個數(shù)2h count=0; for(int i=1;idata); /*訪問根結(jié)點訪問根結(jié)點*/ PreOrder(b-lchild); PreOrder(b-rchild); （b）中遍歷二叉樹）中遍歷二叉樹中序遍歷二叉樹中序遍歷二叉樹算法思想算法思想: : 若二叉樹非空，則：若二叉樹非空，則：(1) 中序遍歷左子樹中序遍歷左子樹(2) 訪問根結(jié)點訪問根結(jié)點(3) 中序遍歷右子樹中序遍歷右子樹ABDECGFvoid InOrde

17、r(BTNode *b) /*中序遍歷的遞歸算法中序遍歷的遞歸算法*/ if (b!=NULL) InOrder(b-lchild); printf(%c ,b-data); /*訪問根結(jié)點訪問根結(jié)點*/ InOrder(b-rchild); 二叉樹中序遍歷的遞歸算法實現(xiàn)如下：二叉樹中序遍歷的遞歸算法實現(xiàn)如下：（c）后遍歷二叉樹）后遍歷二叉樹后序遍歷二叉樹后序遍歷二叉樹算法思想算法思想: : 若二叉樹非空，則：若二叉樹非空，則：(1) 后序遍歷左子樹后序遍歷左子樹(2) 后序遍歷右子樹后序遍歷右子樹(3) 訪問根結(jié)點訪問根結(jié)點ABDECGF二叉樹后序遍歷的遞歸算法實現(xiàn)如下：二叉樹后序遍歷的遞歸

18、算法實現(xiàn)如下：void PostOrder(BTNode *b) /*后序遍歷遞歸算法后序遍歷遞歸算法*/ if (b!=NULL) PostOrder(b-lchild); PostOrder(b-rchild); printf(%c ,b-data); /*訪問根結(jié)點訪問根結(jié)點*/ （d）二叉樹的層次遍歷）二叉樹的層次遍歷從根結(jié)點至葉結(jié)點，從左子樹至右子樹的次序訪問二叉樹的結(jié)點。從根結(jié)點至葉結(jié)點，從左子樹至右子樹的次序訪問二叉樹的結(jié)點。ABDECGF這顆二叉樹的層次遍歷序列為這顆二叉樹的層次遍歷序列為ABCDEFG,遍歷的具體算法如下：遍歷的具體算法如下： 算法實現(xiàn)：算法實現(xiàn)： (1)初始

19、化一個隊列，并把根結(jié)點入隊列；初始化一個隊列，并把根結(jié)點入隊列； (2)當(dāng)隊列非空時，循環(huán)執(zhí)行（當(dāng)隊列非空時，循環(huán)執(zhí)行（3）（）（5）；否）；否則執(zhí)行（則執(zhí)行（6）；）； (3)出隊列取得一個結(jié)點，訪問該結(jié)點；出隊列取得一個結(jié)點，訪問該結(jié)點； (4)如果該結(jié)點的左子樹非空，則將左子樹入隊如果該結(jié)點的左子樹非空，則將左子樹入隊列；列； (5)如果該結(jié)點的右子樹非空，則將右子樹入隊如果該結(jié)點的右子樹非空，則將右子樹入隊列；列； (6)結(jié)束結(jié)束 具體實現(xiàn)的算法的如下：具體實現(xiàn)的算法的如下：void LevelOrder(BTNode *b) BTNode *p; BTNode *quMaxSize;

20、/*定義環(huán)形隊列定義環(huán)形隊列,存放結(jié)點指針存放結(jié)點指針*/ int front,rear;/*定義隊頭和隊尾指針定義隊頭和隊尾指針*/ front=rear=-1;/*置隊列為空隊列置隊列為空隊列*/ rear+; qurear=b;/*根結(jié)點指針進入隊列根結(jié)點指針進入隊列*/ while (front!=rear)/*隊列不為空隊列不為空*/ front=(front+1)%MaxSize; p=qufront;/*隊頭出隊列隊頭出隊列*/ printf(%c ,p-data);/*訪問結(jié)點訪問結(jié)點*/if (p-lchild!=NULL)/*有左孩子時將其進隊有左孩子時將其進隊*/ rea

21、r=(rear+1)%MaxSize; qurear=p-lchild; if (p-rchild!=NULL)/*有右孩子時將其進隊有右孩子時將其進隊*/ rear=(rear+1)%MaxSize; qurear=p-rchild; 例例7.2 假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲,試設(shè)試設(shè)計一個算法計一個算法,輸出一棵給定二叉樹的所有葉子結(jié)點。輸出一棵給定二叉樹的所有葉子結(jié)點。 解：輸出一棵二叉樹的所有葉子結(jié)點的遞歸模型解：輸出一棵二叉樹的所有葉子結(jié)點的遞歸模型f()如下：如下： f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：輸出：輸出*b

22、結(jié)點的結(jié)點的data域域 若若*b為葉子結(jié)點為葉子結(jié)點 f(b)：f(b-lchild);f(b-rchild) 其他情況其他情況 void DispLeaf(BTNode *b) if (b!=NULL) if (b-lchild=NULL & b-rchild=NULL) printf(%c ,b-data); else DispLeaf(b-lchild); DispLeaf(b-rchild); 課堂練習(xí)課堂練習(xí) 一、已知一顆二叉樹是以二叉鏈表的形式一、已知一顆二叉樹是以二叉鏈表的形式 存儲的，其結(jié)點結(jié)構(gòu)說明如下：存儲的，其結(jié)點結(jié)構(gòu)說明如下： struct node int d

23、ata; /結(jié)點的數(shù)據(jù)結(jié)點的數(shù)據(jù) struct node *left; /左孩子的地址左孩子的地址 struct node *right; /右孩子的地址右孩子的地址 請在（請在（1）（）（2）兩題的空白處進行填空，完成題目要求）兩題的空白處進行填空，完成題目要求的功能。注意，每空只能填一個語句，多填為的功能。注意，每空只能填一個語句，多填為0分。（上分。（上海交通大學(xué)，海交通大學(xué)，2004 三（三（10分）分） （1）求出以）求出以T為根的二叉樹或子樹的結(jié)點個數(shù)。為根的二叉樹或子樹的結(jié)點個數(shù)。 int size(struct node *T) if( (1) ) return 0; else

24、( (2) ) ; T=NULLreturn(1+size(T-left)+size(T-ringht) （2）求出以）求出以T為根的二叉樹或子樹的高度。為根的二叉樹或子樹的高度。 int height(struct node *T) if（T=NULL）( (3) ) ; else( (4) ) ; return 0return (height(T-left)height(T-right)?:height(T-left)+1;height(T-right)+1) 二叉樹的寬度：是指二叉樹每層結(jié)點數(shù)的最大值。ABDECGFint BTreeWidth(NODE *root,int k) /求二

25、叉樹的寬度求二叉樹的寬度if(root=NULL) return 0;elsecountk+;/count數(shù)組用來保存每層結(jié)點的個數(shù)數(shù)組用來保存每層結(jié)點的個數(shù)if(mleft,k+1);BTreeWidth(root-right,k+1);return m;int BTreeWidth(NODE *root,int k) /if(root=NULL) return 0;elsecountk+;/count if(mleft,k+1);BTreeWidth(root-right,k+1);return m; int main() NODE *t; int x; pre(t); x=BTreeWi

26、dth(t,0); coutlc!=NULL&(b=0) EnQueue(Q,p-lc); else if(p-lc!=NULL)&(b=1) return FALSE; else if(p-lc=NULL&b=0) b=1; If(p-rc!=NULL&b=0) EnQueue(Q,p-rc);else if(p-rc!=NULL)&(b=1) return FALSE; else if(p-rc=NULL&b=0) b=1;Return TRUE; （4）在遍歷的過程中建立二叉樹）在遍歷的過程中建立二叉樹 “遍歷遍歷”是二叉樹操作的基礎(chǔ)，可以

27、在遍歷的過程中對結(jié)點進行是二叉樹操作的基礎(chǔ)，可以在遍歷的過程中對結(jié)點進行各種操作，如：對于一顆已知樹可求結(jié)點的雙親，求結(jié)點的孩子各種操作，如：對于一顆已知樹可求結(jié)點的雙親，求結(jié)點的孩子結(jié)點，求判斷結(jié)點所在層等，反之，也可以在遍歷過程中生成節(jié)結(jié)點，求判斷結(jié)點所在層等，反之，也可以在遍歷過程中生成節(jié)點，建立二叉樹的存儲結(jié)構(gòu)。點，建立二叉樹的存儲結(jié)構(gòu)。例如下面算法是按先序序列建立二叉樹的二叉鏈表的過程。例如下面算法是按先序序列建立二叉樹的二叉鏈表的過程。void PreOrderC(BTNode * &t)char c; cinc;if(c=0 ) t=NULL;elset=(BTNode*

28、)malloc(sizeof(BTNode); t-data=c; t-lchild=NULL; t-rchild=NULL; PreOrderC(t-lchild);PreOrderC(t-rchild);void levelcreat(BTNode *&t)BTNode *s20;int rear(0),front(0); BTNode *p,*q,*root;char ch,ch1,ch2;coutch;if(ch=0) exit(1);層次遍歷建立二叉樹層次遍歷建立二叉樹else root=(BTNode*)malloc(sizeof(BTNode); root-data=c;

29、 root-lchild=NULL; root-rchild=NULL; srear+=root; while(front!=rear)p=s+front;coutch1ch2;if(ch1!=0) q=(BTNode*)malloc(sizeof(BTNode); q-data=c; q-lchild=NULL; q-rchild=NULL; p-lchild=q; s+rear=q; if(ch2!=0) q=(BTNode*)malloc(sizeof(BTNode); q-data=c; q-lchild=NULL; q-rchild=NULL; p-lchild=q; s+rear=

30、q; 已知二叉樹的先序序列為ABDGCEF，中序序列為DGBAECF，請畫出該二叉樹。ABCEDGF int creat(treenode *&root,char pre,char in,int n) int k;char *p;if(ndata=*pre; root-left=NULL;root-right=NULL;for(p=in;pleft,pre+1,in,k); creat(root-right,pre+k+1,p+1,n-k-1); 7.4.3 7.4.3 二叉樹遍歷非遞歸算法二叉樹遍歷非遞歸算法 1. 1. 中序遍歷非遞歸算法中序遍歷非遞歸算法中序遍歷二叉樹的非遞歸算法

31、需要使用棧作為輔助來完成。中序遍歷二叉樹的非遞歸算法需要使用棧作為輔助來完成。具體的算法描述如下：具體的算法描述如下：（a）設(shè)置一個堆棧并初始化；）設(shè)置一個堆棧并初始化；（b）使臨時指針）使臨時指針p指向根結(jié)點；指向根結(jié)點；（c）當(dāng)）當(dāng)p不為空，不為空，p被賦值為被賦值為p所指結(jié)點的左鏈；所指結(jié)點的左鏈；（d）判斷）判斷p是否為空，如果為空是否為空，如果為空void inorder(BTNode *&root)BTNode *p,*s20; int top=0;p=root;dowhile(p!=NULL)stop+=p; p=p-lchild;if(top!=0)p=s-top;co

32、utdatarchild;while(top!=0|p!=NULL);（2）先序遍歷二叉樹的非遞歸算法實現(xiàn)）先序遍歷二叉樹的非遞歸算法實現(xiàn)void preorder(BTNode *&root)BTNode*p,*s20;int top=0;p=root;dowhile(p!=NULL)coutdatalchild;if(p=NULL&top!=0)p=s-top;p=p-rchild;while(top!=0|p!=NULL);（3）后序遍歷二叉樹的非遞歸算法）后序遍歷二叉樹的非遞歸算法void postorder(BTNode *&root2) BTNode *p,

33、*s120;int s220,top=0,tag;p=root;doif(p!=NULL)s1top=p;s2top+=0;p=p-lchild;else while(top!=0)tag=s2-top;p=s1top;if(tag=0)s1top=p;s2top+=1;p=p-rchild;break;else if(tag=1) coutdata;while(p!=root&top!=0);7.8 哈夫曼樹哈夫曼樹BGFCDAE例例ABE 為結(jié)點為結(jié)點A到到E之間的路徑，之間的路徑，其路徑長度為其路徑長度為2，（1）路徑長度）路徑長度 由樹中一個結(jié)點到另一個結(jié)點的分支構(gòu)成這兩由樹中

34、一個結(jié)點到另一個結(jié)點的分支構(gòu)成這兩個結(jié)點之間的路徑，路徑上分支的數(shù)目稱為路徑長度。個結(jié)點之間的路徑，路徑上分支的數(shù)目稱為路徑長度。樹的路徑長度樹的路徑長度=lAD +lAE+ lAF +lAG =2+2+2+2=8（2）樹的路徑長度）樹的路徑長度 從根結(jié)點到每個結(jié)點的路徑長度之和。從根結(jié)點到每個結(jié)點的路徑長度之和。BGFCDAE例例 （3）結(jié)點的帶）結(jié)點的帶權(quán)權(quán)路徑長度路徑長度 從根結(jié)點到某個結(jié)點的路徑從根結(jié)點到某個結(jié)點的路徑長度與該結(jié)點所帶的權(quán)值的乘積。長度與該結(jié)點所帶的權(quán)值的乘積。結(jié)點結(jié)點a的帶權(quán)路徑長度為的帶權(quán)路徑長度為17，結(jié)點，結(jié)點b的帶權(quán)路徑長度為：的帶權(quán)路徑長度為：25 （4）樹

35、的帶權(quán)路徑長度）樹的帶權(quán)路徑長度 樹中所有葉子結(jié)點的帶權(quán)路徑樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，通常記作：長度之和，通常記作： 該樹的帶權(quán)路徑長度為：該樹的帶權(quán)路徑長度為：7152234335（5）哈夫曼樹）哈夫曼樹 考慮帶權(quán)時：設(shè)樹中有考慮帶權(quán)時：設(shè)樹中有m個葉結(jié)點，每個葉結(jié)點帶一個權(quán)值個葉結(jié)點，每個葉結(jié)點帶一個權(quán)值w,且根到葉結(jié)點且根到葉結(jié)點i的路徑長度為的路徑長度為 Li (=1，2， m），則樹），則樹的帶權(quán)路徑長度為樹中所有葉結(jié)點的權(quán)值與路徑長度的乘積的的帶權(quán)路徑長度為樹中所有葉結(jié)點的權(quán)值與路徑長度的乘積的總和?？偤汀?即：即： 使使WPL最小的二叉樹成為最優(yōu)二叉樹最小的二叉樹成為最

36、優(yōu)二叉樹(Huffman 樹樹)B BD DA AC C7 5 2 47 5 2 4A AC C D DB B4 47 75 52 2WPL=7WPL=7* *2+52+5* *2+22+2* *2+42+4* *2=362=36WPL=7WPL=7* *3+53+5* *3+23+2* *1+41+4* *2=462=46例例1： 有有4個結(jié)點個結(jié)點A，B，C，D，權(quán)值分別為，權(quán)值分別為7，5，2和和4，分別，分別 以這以這4個結(jié)點作為葉子結(jié)點，構(gòu)造不同形態(tài)的二叉樹并計算其個結(jié)點作為葉子結(jié)點，構(gòu)造不同形態(tài)的二叉樹并計算其WPL值。值。C CA A B BD D4 47 75 52 2WPL=

37、7WPL=7* *1+51+5* *2+22+2* *3+43+4* *3=353=35可以驗證，最后這個二叉樹為哈夫曼樹。可以驗證，最后這個二叉樹為哈夫曼樹。例例2 : 編制一個將百分制轉(zhuǎn)換成五分制的程序。編制一個將百分制轉(zhuǎn)換成五分制的程序。 最直觀的方法是利用最直觀的方法是利用if語句來實現(xiàn)?？捎枚鏄涿枋雠卸ㄟ^程。語句來實現(xiàn)。可用二叉樹描述判定過程。a a 80 80a a 90 90不及格不及格良好良好中等中等及格及格優(yōu)秀優(yōu)秀a a 60 60a a 70 70 設(shè)有設(shè)有10000個百分制分數(shù)要轉(zhuǎn)換，設(shè)學(xué)生成績在個百分制分數(shù)要轉(zhuǎn)換，設(shè)學(xué)生成績在5個等級上的個等級上的分布如下：分布如下：

38、分數(shù)分數(shù) 0-59 60-69 70-79 80-89 90-1000-59 60-69 70-79 80-89 90-100比例數(shù)比例數(shù) 0.05 0.15 0.40 0.30 0.100.05 0.15 0.40 0.30 0.10按上圖的判定過程按上圖的判定過程: 轉(zhuǎn)換一個分數(shù)所需的比較次數(shù)轉(zhuǎn)換一個分數(shù)所需的比較次數(shù)= 從根到對應(yīng)結(jié)點的路徑長度。從根到對應(yīng)結(jié)點的路徑長度。a a 80 80a a 90 90不及格不及格良好良好中等中等及格及格優(yōu)秀優(yōu)秀a a 60 60a a 70 70轉(zhuǎn)換轉(zhuǎn)換10000個分數(shù)所需的總比較次數(shù)個分數(shù)所需的總比較次數(shù)= 10000 (0.05 1+0.15

39、2+0.4 3+0.3 4+0.1 4） =31500 分數(shù)分數(shù) 0-59 60-69 70-79 80-89 90-1000-59 60-69 70-79 80-89 90-100比例數(shù)比例數(shù) 0.05 0.15 0.40 0.30 0.100.05 0.15 0.40 0.30 0.10轉(zhuǎn)換轉(zhuǎn)換10000個分數(shù)所需的總比較次數(shù)個分數(shù)所需的總比較次數(shù)= 10000 (0.05 3+0.15 3+0.4 2+0.3 2+0.1 2）=22000分數(shù)分數(shù) 0-59 60-69 70-79 80-89 90-1000-59 60-69 70-79 80-89 90-100比例數(shù)比例數(shù) 0.05 0

40、.15 0.40 0.30 0.100.05 0.15 0.40 0.30 0.103 哈夫曼樹的構(gòu)造算法哈夫曼樹的構(gòu)造算法（1）以權(quán)值分別為）以權(quán)值分別為W1,W2的個結(jié)點，構(gòu)成的個結(jié)點，構(gòu)成n棵二叉棵二叉樹樹T1,T2,Tn并組成森林并組成森林F=T1,T2,Tn,其中每棵二叉其中每棵二叉樹樹 Ti僅有一個權(quán)值為僅有一個權(quán)值為 Wi的根結(jié)點；的根結(jié)點；（2）在）在F中選取兩棵根結(jié)點權(quán)值最小的樹作為左右子樹構(gòu)造一中選取兩棵根結(jié)點權(quán)值最小的樹作為左右子樹構(gòu)造一棵新二叉樹，并且置新二叉樹根結(jié)點權(quán)值為左右子樹上根結(jié)點棵新二叉樹，并且置新二叉樹根結(jié)點權(quán)值為左右子樹上根結(jié)點的權(quán)值之和；的權(quán)值之和；（3

41、）從）從F中刪除這兩棵二叉樹，同時將新二叉樹加入到中刪除這兩棵二叉樹，同時將新二叉樹加入到F中中;（4）重復(fù)）重復(fù)(2)()直到直到F中只含一棵二叉樹為止，這棵二叉樹中只含一棵二叉樹為止，這棵二叉樹就是就是Huffman 樹。樹。9例3: 已知權(quán)值 W= 5, 6, 2, 9, 7 56272576976713925767139257925716671329HT不唯一性不唯一性,可能出現(xiàn)在可能出現(xiàn)在:（1）構(gòu)造新樹時，左、右孩子未作規(guī)定。）構(gòu)造新樹時，左、右孩子未作規(guī)定。（2）當(dāng)有多個權(quán)值相同的樹可作有候選樹時，選擇）當(dāng)有多個權(quán)值相同的樹可作有候選樹時，選擇誰未作規(guī)定。誰未作規(guī)定。257697

42、4 4 哈夫曼編碼（哈夫曼編碼（ HuffmanHuffman樹的應(yīng)用之二樹的應(yīng)用之二在通信中）在通信中）（1）問題的提出）問題的提出 通訊中常需要將文字轉(zhuǎn)換成二進制字符串通訊中常需要將文字轉(zhuǎn)換成二進制字符串“電文電文”進進行傳送。文字行傳送。文字 反之，收到電文后要將電文轉(zhuǎn)換成原來的文字，反之，收到電文后要將電文轉(zhuǎn)換成原來的文字，電文電文電文，稱為電文，稱為編碼編碼。文字，稱為文字，稱為譯碼譯碼。例如：需將文字例如：需將文字“ABACCDA”轉(zhuǎn)換成電文。文之轉(zhuǎn)換成電文。文之中有四種字符，用中有四種字符，用2位二進制便可分辨。位二進制便可分辨。 A B C D00 01 10 11編碼方案編碼

43、方案1：則上述文字的電文為：則上述文字的電文為：00010010101100 共共14位。位。譯碼時，只需每譯碼時，只需每2位一譯即可。位一譯即可。特點：等長等頻率編碼，譯碼容易，但電文不一定最短特點：等長等頻率編碼，譯碼容易，但電文不一定最短。 A B C D0 00 1 01編碼方案編碼方案2： 采用不等長編碼，讓出現(xiàn)次數(shù)多的字符用短碼。采用不等長編碼，讓出現(xiàn)次數(shù)多的字符用短碼。 則上述文字則上述文字ABACCDA”的電文為：的電文為：000011010 共共9位。位。 但無法譯碼，它即可譯為但無法譯碼，它即可譯為BBCCACA，也可譯為，也可譯為AAAACCDA等。等。 A B C D0

44、 110 10 111編碼方案編碼方案3： 采用不等長編碼，讓出現(xiàn)次數(shù)多的字符用短碼，采用不等長編碼，讓出現(xiàn)次數(shù)多的字符用短碼，且任一編碼不能是另一編碼的前綴。且任一編碼不能是另一編碼的前綴。前綴編碼前綴編碼則上述文字則上述文字ABACCDA”的電文為：的電文為：0110010101110 共共13位。位。設(shè)有設(shè)有n種字符，每種字符出現(xiàn)的次數(shù)為種字符，每種字符出現(xiàn)的次數(shù)為Wi ,其編碼長度為其編碼長度為Li (i=1,2,n)，則整個電文總長度為則整個電文總長度為 Wi Li ，要得到最短的電文，即使得要得到最短的電文，即使得 Wi Li最小。最小。也就是以字符出現(xiàn)的次數(shù)為權(quán)值，構(gòu)造一棵也就是

45、以字符出現(xiàn)的次數(shù)為權(quán)值，構(gòu)造一棵 Huffman樹，并樹，并規(guī)定左分支編碼位規(guī)定左分支編碼位0，右分支編碼為，右分支編碼為1，則字符的編碼就是從，則字符的編碼就是從根到該字符所在的葉結(jié)點的路徑上的分支編號序列。根到該字符所在的葉結(jié)點的路徑上的分支編號序列。用構(gòu)造用構(gòu)造Huffman樹編出來的碼，稱為樹編出來的碼，稱為Huffman編碼。編碼。 例例5 已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)，試設(shè)計哈夫曼編碼。計哈夫曼編碼。2342871514

46、292958100001111901538011111000編碼：編碼：0.05 00010.29 100.07 11100.08 11110.14 1100.23 01 0.03 00000.11 0015 5 哈夫曼編碼問題數(shù)據(jù)結(jié)構(gòu)設(shè)計哈夫曼編碼問題數(shù)據(jù)結(jié)構(gòu)設(shè)計 哈夫曼樹的特點是不存在度為哈夫曼樹的特點是不存在度為1的最優(yōu)二叉樹，且哈夫曼編碼的最優(yōu)二叉樹，且哈夫曼編碼問題主要涉及到父結(jié)點，左右孩子結(jié)點的操作，因此用一維數(shù)問題主要涉及到父結(jié)點，左右孩子結(jié)點的操作，因此用一維數(shù)組順序存儲哈夫曼樹，此數(shù)組為結(jié)構(gòu)體數(shù)組。組順序存儲哈夫曼樹，此數(shù)組為結(jié)構(gòu)體數(shù)組。 有有n個葉子結(jié)點的哈夫滿樹，共有多少

47、個結(jié)點？個葉子結(jié)點的哈夫滿樹，共有多少個結(jié)點？ 上圖所示二叉樹的存儲結(jié)構(gòu)的初始狀態(tài)為圖一所示，其終結(jié)狀上圖所示二叉樹的存儲結(jié)構(gòu)的初始狀態(tài)為圖一所示，其終結(jié)狀態(tài)為圖二所示。態(tài)為圖二所示。？2n-101234567891011121314weight parent lchild rchild flag圖圖101234567891011121314weight parent lchild rchild flag圖圖2void haffman(int weight,int n,haffnode hafftree)int j,m1,m2,x1,x2;for(int i=0;i2*n-1;i+)if(in) hafftreei.weight=weighti;else hafftreei.weight=0;hafftreei.parent=0;hafftreei.flag=0;hafftreei.leftchild=-1;hafftreei.rightchild=-1;for(i=0;in-1;i+)m1=m2=maxvalue;x1=x2=0;for(j=0;jn+i;j+)if(hafftree