1、第六章 樹(shù)和二叉樹(shù)一、樹(shù)的基本概念1、樹(shù)的定義：2、樹(shù)的基本術(shù)語(yǔ)（1）節(jié)點(diǎn)的度和樹(shù)的度（2）分支節(jié)點(diǎn)和葉節(jié)點(diǎn)（3）路徑和路徑長(zhǎng)度（4）孩子節(jié)點(diǎn)、雙親結(jié)點(diǎn)和兄弟節(jié)點(diǎn)（5）節(jié)點(diǎn)的層次和樹(shù)的高度（6）有序樹(shù)和無(wú)序樹(shù)（7）森林3、樹(shù)的邏輯表示（1）樹(shù)形表示法（2）文氏圖表示法（3）凹入表示法（4）嵌套括號(hào)表示法4、樹(shù)的性質(zhì)（1）樹(shù)中節(jié)點(diǎn)數(shù)等于所有節(jié)點(diǎn)的度加1。（2）度為m的樹(shù)中第i層至多有mi-1個(gè)節(jié)點(diǎn)。（3）高度為h的m叉樹(shù)至多有(mh-1)/(m-1)個(gè)節(jié)點(diǎn)。（4）具有n個(gè)節(jié)點(diǎn)的m叉樹(shù)的最小高度為logm(n(m-1)+1)v性質(zhì)1的證明：v證明：根據(jù)樹(shù)的定義，在一棵樹(shù)中，除樹(shù)根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有

2、且僅有一個(gè)前驅(qū)結(jié)點(diǎn)。也就是說(shuō)，每個(gè)結(jié)點(diǎn)與指向它的一個(gè)分支一一對(duì)應(yīng)，所以除樹(shù)根之外的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的分支數(shù)(度數(shù))，從而可得樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。 v性質(zhì)2證明（數(shù)學(xué)歸納法）： v（1）對(duì)于第一層，因?yàn)闃?shù)中的第一層上只有一個(gè)結(jié)點(diǎn)，即整個(gè)樹(shù)的根結(jié)點(diǎn)，而由i=l代入mi-1得mi-1 =1，也同樣得到只有一個(gè)結(jié)點(diǎn)，顯然結(jié)論成立。v（2）假設(shè)對(duì)于第(i-1)層(il)命題成立，即度為m的樹(shù)中第(i-1)層上至多有mi-2結(jié)點(diǎn)，則根據(jù)樹(shù)的度的定義，度為m的樹(shù)中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子，所以第i層上的結(jié)點(diǎn)數(shù)至多為第(i-1)層上結(jié)點(diǎn)數(shù)的m倍，即至多為mi-2 *m= mi-1個(gè)，這與命題相

3、同，故命題成立。 v性質(zhì)4的證明：5、樹(shù)的基本運(yùn)算 樹(shù)的運(yùn)算主要分為三大類：第一類：尋找滿足某種特定關(guān)系的的節(jié)點(diǎn)，如尋找當(dāng)前節(jié)點(diǎn)的雙親結(jié)點(diǎn)；第二類：插入和刪除某個(gè)節(jié)點(diǎn)；第三類：遍歷樹(shù)中的每一個(gè)節(jié)點(diǎn)。 樹(shù)的遍歷算法：按某種方式訪問(wèn)樹(shù)中每一個(gè)節(jié)點(diǎn)且每一個(gè)節(jié)點(diǎn)只被訪問(wèn)一次。 注意：樹(shù)的先根和后根遍歷算法是遞歸的。（1）先根遍歷。例如：對(duì)前述圖（a），先根遍歷得到的節(jié)點(diǎn)序列為：ABEFCGJDHIKLM。（2）后根遍歷。例如：對(duì)前述圖（a），后根遍歷得到的節(jié)點(diǎn)序列為：EFBJGCHKLMIDA6、樹(shù)的存儲(chǔ)結(jié)構(gòu) 既要求存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)元素，又要存儲(chǔ)節(jié)點(diǎn)之間的邏輯關(guān)系。常用的三種存儲(chǔ)結(jié)構(gòu)：（1）雙親存儲(chǔ)結(jié)構(gòu)

4、：需一偽指針指示雙親結(jié)點(diǎn)的位置。（2）孩子存儲(chǔ)結(jié)構(gòu)：按樹(shù)的度設(shè)計(jì)節(jié)點(diǎn)的孩子節(jié)點(diǎn)的指針域的個(gè)數(shù)。（3）孩子兄弟存儲(chǔ)結(jié)構(gòu)：為每個(gè)節(jié)點(diǎn)設(shè)計(jì)三個(gè)域：數(shù)據(jù)元素域、該節(jié)點(diǎn)的第一個(gè)孩子域、該節(jié)點(diǎn)的下一個(gè)兄弟節(jié)點(diǎn)指針域。 由于樹(shù)的孩子兄弟存儲(chǔ)結(jié)構(gòu)有兩個(gè)指針域，并且這兩個(gè)指針是有序的，所以孩子兄弟存儲(chǔ)結(jié)構(gòu)是把樹(shù)轉(zhuǎn)換為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。我們?cè)诤竺鎸?huì)討論到，把樹(shù)轉(zhuǎn)換為二叉樹(shù)所對(duì)應(yīng)的結(jié)構(gòu)恰好就是這種孩子兄弟存儲(chǔ)結(jié)構(gòu)。所以，孩子兄弟存儲(chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是可方便地實(shí)現(xiàn)樹(shù)和二叉樹(shù)的相互轉(zhuǎn)換。 孩子兄弟存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)也和孩子表示法的缺點(diǎn)一樣：就是從前結(jié)點(diǎn)查找雙親結(jié)點(diǎn)比較麻煩，需要從樹(shù)的根結(jié)點(diǎn)開(kāi)始逐個(gè)結(jié)點(diǎn)比較查找。 樹(shù)的基礎(chǔ)要

5、點(diǎn)1、樹(shù)最適合表示元素之間具有分支層次關(guān)系的數(shù)據(jù)。2、一般樹(shù)可以轉(zhuǎn)換成二叉樹(shù)是基于樹(shù)的樹(shù)形表示法。3、樹(shù)在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式有三種方法：雙親、孩子和孩子兄弟存儲(chǔ)結(jié)構(gòu)。4、利用樹(shù)的孩子兄弟表示法，可以將一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)。5、高度為k的m（m=2）叉樹(shù)至少有（ ）個(gè)節(jié)點(diǎn)，最多有（ ）個(gè)節(jié)點(diǎn)。6、在線性表、m叉樹(shù)、棧和隊(duì)列中，不可以利用順序存儲(chǔ)結(jié)構(gòu)的是（ ）。7、高度為h的滿m叉樹(shù)的第k層有（ ）個(gè)節(jié)點(diǎn)。8、按后序遍歷樹(shù)或森林，等同于按（ ）遍歷對(duì)應(yīng)的二叉樹(shù)。9、在樹(shù)中，一個(gè)節(jié)點(diǎn)的直接孩子節(jié)點(diǎn)的個(gè)數(shù)稱為該節(jié)點(diǎn)的度。10、一棵有n個(gè)節(jié)點(diǎn)的樹(shù)，樹(shù)中的所有節(jié)點(diǎn)的度之和為（ ）。11、節(jié)點(diǎn)最少的樹(shù)為（ ）

6、，節(jié)點(diǎn)最少的二叉樹(shù)為（ ）。【例1】含有n個(gè)節(jié)點(diǎn)和n個(gè)葉子節(jié)點(diǎn)的完全三叉樹(shù)的高度各是多少？【例2】以孩子兄弟鏈表為存儲(chǔ)結(jié)構(gòu)，請(qǐng)?jiān)O(shè)計(jì)遞歸和非遞歸算法求樹(shù)的高度。二、二叉樹(shù)的概念和性質(zhì)1、二叉樹(shù)的概念 二叉樹(shù)是有限的結(jié)點(diǎn)的集合，此集合或者為空，或者是由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。 特點(diǎn)：（1）每個(gè)節(jié)點(diǎn)至多有兩個(gè)子樹(shù)，任何結(jié)點(diǎn)的度數(shù)不能大于2。（2）二叉樹(shù)的結(jié)點(diǎn)有嚴(yán)格的左右之分，其次序不能任意顛倒。 二叉樹(shù)的表示方法：與樹(shù)的表示方法一樣，有：樹(shù)形表示法、文氏圖表示法、凹入表示法和嵌套括號(hào)表示法。 滿二叉樹(shù)的概念。 完全二叉樹(shù)的概念。 滿二叉樹(shù)是完全二叉樹(shù)的一種特例，并且

7、完全二叉樹(shù)與同高度的滿二叉樹(shù)對(duì)應(yīng)位置結(jié)點(diǎn)有同一編號(hào)。2、二叉樹(shù)的性質(zhì)（1）非空二叉樹(shù)上葉節(jié)點(diǎn)數(shù)等于雙分支節(jié)點(diǎn)數(shù)加1。（會(huì)證明）（2）非空二叉樹(shù)上第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i=1）。（3）高度為h的二叉樹(shù)至多有2h-1個(gè)結(jié)點(diǎn)（h=1）。（4）對(duì)完全二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)（1i n ,n1,n為結(jié)點(diǎn)數(shù) ）有： 若2in,則編號(hào)為i的結(jié)點(diǎn)為分支節(jié)點(diǎn)，否則為葉子節(jié)點(diǎn)。 若n為奇數(shù)，則每個(gè)分支節(jié)點(diǎn)都既有左孩子，又有右孩子；若n為偶數(shù)，則編號(hào)最大的分支節(jié)點(diǎn)（編號(hào)為n/2）只有左孩子，沒(méi)有右孩子，其余分支節(jié)點(diǎn)左、右孩子都有。 若編號(hào)為i的結(jié)點(diǎn)有左孩子，則左孩子結(jié)點(diǎn)的編號(hào)為2i；若編號(hào)為i的結(jié)點(diǎn)有右孩子，

8、則左孩子結(jié)點(diǎn)的編號(hào)為2i+1。 除根節(jié)點(diǎn)以外，若一個(gè)結(jié)點(diǎn)的編號(hào)為i，則其雙親結(jié)點(diǎn)的編號(hào)為i/2，即當(dāng)i為偶數(shù)時(shí)，其雙親結(jié)點(diǎn)的編號(hào)為i/2，它是雙親結(jié)點(diǎn)的左孩子；當(dāng)i為奇數(shù)時(shí)，其雙親結(jié)點(diǎn)的編號(hào)為(i-1)/2，它是雙親結(jié)點(diǎn)的右孩子。 該性質(zhì)可用數(shù)學(xué)歸納法來(lái)證明。（5）具有n個(gè)（n0）結(jié)點(diǎn)的完全二叉樹(shù)的高度為log2n+1（取上整）或log2n+1（log2n取下整）。 注意：二叉樹(shù)的上述性質(zhì)是計(jì)算和證明二叉樹(shù)中某類結(jié)點(diǎn)個(gè)數(shù)或高度的基礎(chǔ)。【例3】對(duì)于任何非空二叉樹(shù)，假設(shè)葉子結(jié)點(diǎn)的個(gè)數(shù)為n0，而度數(shù)為2的結(jié)點(diǎn)個(gè)數(shù)為n2，請(qǐng)給出和之間所滿足的關(guān)系式n0=f(n2)。要求給出推導(dǎo)過(guò)程。3、二叉樹(shù)、樹(shù)、森

9、林之間的轉(zhuǎn)換 可以把在樹(shù)的處理中的問(wèn)題對(duì)應(yīng)到二叉樹(shù)中進(jìn)行處理。 轉(zhuǎn)換時(shí)的約定：把一般的樹(shù)作為有序樹(shù)來(lái)處理。（1）森林、樹(shù)轉(zhuǎn)換為二叉樹(shù)【例4】將下圖所示的森林轉(zhuǎn)換成二叉樹(shù)表示。（2）二叉樹(shù)還原為森林、樹(shù)【例5】將下圖所示的二叉樹(shù)轉(zhuǎn)換為一般的樹(shù)。三、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1、二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu) 用一組地址連續(xù)的存儲(chǔ)單元來(lái)存放二叉樹(shù)的存儲(chǔ)元素。 二叉樹(shù)順序存儲(chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的存放次序：結(jié)點(diǎn)從小到大編號(hào)，編號(hào)順序就是結(jié)點(diǎn)存放在連續(xù)存儲(chǔ)單元的先后次序。 該存儲(chǔ)結(jié)構(gòu)對(duì)于完全二叉樹(shù)來(lái)說(shuō)是合適的，但對(duì)于一般的二叉樹(shù)，特別是那些單分支的二叉樹(shù)來(lái)說(shuō)很不合適。 順序存儲(chǔ)結(jié)構(gòu)的固有缺陷使得二叉樹(shù)的插入、刪除等運(yùn)算十分不方便。

10、【例6】給出下圖所示的二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)。2、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（二叉鏈） 二叉樹(shù)中，標(biāo)準(zhǔn)方式的節(jié)點(diǎn)結(jié)構(gòu)如下：【例】給出如下圖所示的二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。四、二叉樹(shù)的基本運(yùn)算及其實(shí)現(xiàn)1、二叉樹(shù)基本運(yùn)算概述（1）創(chuàng)建二叉樹(shù)：creatree(*b,*str)；（2）找結(jié)點(diǎn)：find(*b,x)；（3）找孩子結(jié)點(diǎn)：lchhild(p)和rchild(p)（4）求高度：treedepth(*b)（5）輸出二叉樹(shù)：disptree(*b)五、二叉樹(shù)的遍歷v二叉樹(shù)的遍歷二叉樹(shù)的遍歷是指按照一定次序訪問(wèn)樹(shù)中所有結(jié)點(diǎn)，井且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次的過(guò)程，它是最基本的運(yùn)算，是二叉樹(shù)中所有其他運(yùn)算的基礎(chǔ)。v六種

11、遍歷方法先序遍歷二叉樹(shù)中序遍歷二叉樹(shù)后序遍歷二叉樹(shù)v二叉樹(shù)遍歷算法的實(shí)現(xiàn)二叉樹(shù)的基礎(chǔ)要點(diǎn)1、具有64個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為（ ）。2、具有n個(gè)結(jié)點(diǎn)的互不相似的二叉樹(shù)共有（ ）。3、高度為h的完全二叉樹(shù)至少有（ ）個(gè)結(jié)點(diǎn)，至多有（ ）個(gè)結(jié)點(diǎn)。H與結(jié)點(diǎn)數(shù)n之間的關(guān)系是（ ）。4、具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，采用二叉鏈表存儲(chǔ)，共有（ ）個(gè)空鏈域。5、由二叉樹(shù)的先序序列和后序序列不能唯一確定一棵二叉樹(shù)。6、具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)是一棵路徑長(zhǎng)度最短的二叉樹(shù)。7、對(duì)于先序序列和中序序列結(jié)果相同的二叉樹(shù)為（ ）二叉樹(shù)。對(duì)于中序序列和后序序列結(jié)果相同的二叉樹(shù)為（ ）二叉樹(shù)。對(duì)于先序序列和后序序列結(jié)果相同的二叉

12、樹(shù)為（ ）二叉樹(shù)。8、具有10個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)中有（）個(gè)度為2的結(jié)點(diǎn)。9、設(shè)只包含根節(jié)點(diǎn)的二叉樹(shù)的高度為0，則高度為k的二叉樹(shù)的最大節(jié)點(diǎn)數(shù)是（ ），最小節(jié)點(diǎn)數(shù)為（ ）。10、具有n個(gè)葉子節(jié)點(diǎn)的完全二叉樹(shù)的高度為（ ）。具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為（ ）。11、某二叉樹(shù)結(jié)點(diǎn)的中序序列為ABCDEFG，后序序列為BDCAFGE，則該二叉樹(shù)結(jié)點(diǎn)的先序序列是（ ）。該二叉樹(shù)對(duì)應(yīng)的森林包括（ ）棵樹(shù)。12、下列敘述中正確的是：（1）在二叉樹(shù)中，任何一個(gè)結(jié)點(diǎn)的度都為2；（2）二叉樹(shù)的度為2；（3）在二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2。（4）一棵二叉樹(shù)的度可以小于2。13、樹(shù)的基本遍歷策略可分為先根和后根

13、遍歷；二叉樹(shù)的遍歷策略可分為先序、中序和后序遍歷。這里，把由樹(shù)轉(zhuǎn)化得到的二叉樹(shù)叫做該樹(shù)對(duì)應(yīng)的二叉樹(shù)，則在以下敘述中，正確的是：（1）樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先序遍歷序列相同。（2）樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的后序遍歷序列相同。（3）樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的中序遍歷序列相同。（4）樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的中序遍歷序列相同。14、一棵非空二叉樹(shù)的中序序列中，根節(jié)點(diǎn)的右邊只有右子樹(shù)的所有節(jié)點(diǎn)。15、一棵滿二叉樹(shù)共有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉子結(jié)點(diǎn)，m和n的關(guān)系是（ ）。16、設(shè)森林F中有三棵樹(shù)，第一、第二和第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為m1，m2和m3，則森林F對(duì)應(yīng)的二叉樹(shù)

14、根節(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)為（ ） 。17、二叉樹(shù)的先序序列中，任意一個(gè)結(jié)點(diǎn)均在其孩子節(jié)點(diǎn)的前面。18、若一棵二叉樹(shù)中只有葉子結(jié)點(diǎn)和左右子樹(shù)皆非空的結(jié)點(diǎn)，設(shè)葉子結(jié)點(diǎn)的個(gè)數(shù)為k，則左右子樹(shù)皆非空的結(jié)點(diǎn)個(gè)數(shù)是k-1。19、對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)它為一棵（ ）時(shí)，具有最小高度；當(dāng)它為（ ）具有最大高度，即為n。20、從概念上來(lái)講，樹(shù)與二叉樹(shù)是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹(shù)轉(zhuǎn)化為二叉樹(shù)的基本目的是樹(shù)可以采用二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)并利用二叉樹(shù)已有的算法來(lái)解決樹(shù)的有關(guān)問(wèn)題。【例8】設(shè)計(jì)二叉樹(shù)先序遍歷的非遞歸算法。 使用一個(gè)棧保存二叉樹(shù)中結(jié)點(diǎn)的指針。有兩種實(shí)現(xiàn)二叉樹(shù)先序遍歷的非遞歸算法。六、線索化二叉樹(shù)v概念

15、：線索、線索二叉樹(shù)、【例9】給出下圖所示的二叉樹(shù)的先序、中序和后序線索二叉樹(shù)。v對(duì)同一棵二叉樹(shù)的遍歷方式不同，所得到的線索樹(shù)也不同，二叉樹(shù)有先序、中序和后序三種遍歷方式，所以線索樹(shù)也有先序線索二叉樹(shù)、中序線索二叉樹(shù)和后序線索二叉樹(shù)三種。v以中序線索二叉樹(shù)為例，討論建立線索二叉樹(shù)的算法。 v建立線索二叉樹(shù)，或者說(shuō)，對(duì)二叉樹(shù)線索化，實(shí)質(zhì)上就是遍歷一棵二叉樹(shù)，在遍歷的過(guò)程中，檢查當(dāng)時(shí)結(jié)點(diǎn)的左、右指計(jì)域是否為空。如果為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索。另外，在對(duì)一棵二叉樹(shù)加線索時(shí)，必須首先創(chuàng)建一個(gè)頭結(jié)點(diǎn)，建立頭結(jié)點(diǎn)與二叉樹(shù)的根結(jié)點(diǎn)的線索。對(duì)二叉樹(shù)線索化后，還須建立最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的線

16、索。v為了實(shí)現(xiàn)線索化二叉樹(shù)，將前面二叉樹(shù)結(jié)點(diǎn)的類型定義修改如下 ：typedef struct node ElemType data; int Itag, rtag; /增加的線索標(biāo)記 struct node *lchiid; struct node *rchild;)BTree; 線索二叉樹(shù)基礎(chǔ)要點(diǎn)1、線索二叉樹(shù)的左線索指向其前驅(qū)結(jié)點(diǎn)，右線索指向其后繼結(jié)點(diǎn)。2、后序線索樹(shù)的遍歷仍需要棧的支持。3、二叉樹(shù)按某種順序線索化后，任一結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線索。（對(duì)/錯(cuò)）4、在線索化二叉樹(shù)中，結(jié)點(diǎn)*t沒(méi)有左子樹(shù)的充分條件是：（ ）。【例10】設(shè)計(jì)一個(gè)算法在中序線索二叉樹(shù)上尋找一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。

17、七、哈夫曼樹(shù)1、路徑長(zhǎng)度及哈夫曼樹(shù) 結(jié)點(diǎn)的權(quán) 結(jié)點(diǎn)的帶權(quán)路徑的長(zhǎng)度 樹(shù)的帶權(quán)路徑長(zhǎng)度 哈夫曼樹(shù)（最優(yōu)二叉樹(shù)）v在許多應(yīng)用中，常常將樹(shù)中的結(jié)點(diǎn)賦上一個(gè)有著某種意義的實(shí)數(shù)，稱此實(shí)數(shù)為該結(jié)點(diǎn)的權(quán)。v從樹(shù)根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積稱為結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。v樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和稱為該樹(shù)的帶權(quán)路徑長(zhǎng)度，通常記為： 其中，n表示葉子結(jié)點(diǎn)的數(shù)目，Wi和分別表示葉子結(jié)點(diǎn)ki的權(quán)值和根到ki之間的路徑長(zhǎng)度。v在n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中,帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)稱為哈夫曼樹(shù)(或最優(yōu)二叉樹(shù)因?yàn)闃?gòu)造這種樹(shù)的算法是最早由哈夫曼于1952年提出的，所以被稱為哈夫曼樹(shù)（最優(yōu)二

18、叉樹(shù)）。【例】給定4個(gè)葉子結(jié)點(diǎn)，設(shè)其權(quán)值分別為1，3，5，7，可構(gòu)造出形狀不同的4棵二叉樹(shù)：2、哈夫曼樹(shù)的構(gòu)造方法哈夫曼算法：哈夫曼算法：3、哈夫曼編碼v在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換為二進(jìn)制字符0和1組成的二進(jìn)制字符串，我們稱這個(gè)過(guò)程為編碼。顯然，希望電文編碼的代碼長(zhǎng)度最短。哈夫曼樹(shù)可用于構(gòu)造使電文編碼的代碼長(zhǎng)度最短的編碼方案。v具體構(gòu)造方法如下：設(shè)需要編碼的字符集合為d0,d1,dn-1,各個(gè)字符在電文中出現(xiàn)的次數(shù)集合為W0,W1,Wn-l，以d0,d1,dn-1作為葉結(jié)點(diǎn)，以w0, W0,W1,Wn-l作為各根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的權(quán)值構(gòu)造一棵二叉樹(shù)，規(guī)定哈夫曼樹(shù)中的左分支為0，右分

19、支為1，則從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)所經(jīng)過(guò)的分支對(duì)應(yīng)的0和1組成的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼。這樣的編碼稱為哈夫曼編碼。 v實(shí)質(zhì)：就是利用使用頻率越高的采用越短的編碼。哈夫曼樹(shù)的基礎(chǔ)要點(diǎn)1、求具有最小帶權(quán)外部路徑的擴(kuò)充二叉樹(shù)的算法成為哈夫曼算法。對(duì)于給定的一組權(quán)w=10,12,16,21,30，通過(guò)該算法求出擴(kuò)充二叉樹(shù)的帶權(quán)外部路徑長(zhǎng)度為（ ）。2、在葉子數(shù)目和權(quán)值相同的所有二叉樹(shù)中，最優(yōu)二叉樹(shù)一定是完全二叉樹(shù)。（對(duì)/錯(cuò)）【例11】假定用于通訊的電文僅有a，b，c，d，e，f，g，h8個(gè)字母組成，字母在電文中出現(xiàn)的頻率為：0.07,0.19,0,02,0.06,0.32,0.03,0.21和0.1

20、0。試為這些字母設(shè)計(jì)哈夫曼編碼。練習(xí)1、一棵左、右子樹(shù)均不空的二叉樹(shù)在先序線索化后，其空指針域是多少？2、有n個(gè)結(jié)點(diǎn)并且高度為n的二叉樹(shù)的數(shù)目是多少？3、已知完全二叉樹(shù)的第七層有10個(gè)葉子結(jié)點(diǎn)，則整個(gè)二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多是多少？4、一棵二叉樹(shù)的先序、中序和后序序列分別如下，其中一部分未顯示出來(lái)。試求出空格處的內(nèi)容，并畫(huà)出該二叉樹(shù)。先序序列：（）B（）F（）ICEH（）G中序序列：D（）KFIA（）EJC（）后序序列：（）K（）FBHJ（）G（）A5.對(duì)于如圖所示的二叉樹(shù)：(1)請(qǐng)畫(huà)出它的順序存儲(chǔ)結(jié)構(gòu)圖；(2)請(qǐng)將它轉(zhuǎn)換成森林。 6.設(shè)F=T1,T2,T3是森林，試畫(huà)出所對(duì)應(yīng)的二叉樹(shù)，森林如下圖

21、所示。 7.如果一棵哈夫曼樹(shù)T有n0個(gè)葉子結(jié)點(diǎn)，那么，樹(shù)T有多少個(gè)結(jié)點(diǎn)，要求給出求解過(guò)程。8.下表所列的數(shù)據(jù)表給出了在一篇有19710個(gè)詞的英文文章中出現(xiàn)最普通的15個(gè)單詞的出現(xiàn)頻度。假定一篇正文僅由上述字符數(shù)據(jù)表中的詞組成，那么它們的最佳編碼是什么？平均長(zhǎng)度是多少? v9.用一維數(shù)組存放一棵完全二叉樹(shù)：ABCDEFGHIJKL。請(qǐng)寫(xiě)出后序遍歷該二叉樹(shù)的訪問(wèn)結(jié)點(diǎn)序列。 v10.從概念上講，樹(shù)、森林和二叉樹(shù)是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹(shù)、森林轉(zhuǎn)化為二叉樹(shù)的基本目的是什么，并指出樹(shù)和二叉樹(shù)的主要區(qū)別。 【解】 其目的是：樹(shù)和森林采用二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)并利用二叉樹(shù)的已有算法解決樹(shù)和森林的有關(guān)問(wèn)題。主要區(qū)別是：樹(shù)中結(jié)點(diǎn)的最大度數(shù)沒(méi)有限制，而二叉樹(shù)結(jié)