6￥-six(天津科技大學(xué))

第六章樹和二叉樹6.1

樹的定義和基本概念6.2二叉樹6.3遍歷二叉樹6.4樹和森林6.6哈夫曼樹及其應(yīng)用

10/8/20241第六章樹和二叉樹樹型結(jié)構(gòu)的簡(jiǎn)單描述樹型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)是結(jié)點(diǎn)之間有分支，并且具有層次關(guān)系的結(jié)構(gòu)，它非常類似于自然界中的樹。樹結(jié)構(gòu)在客觀世界中是大量存在的，例如家譜、行政組織機(jī)構(gòu)都可用樹形象地表示。樹在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)；在數(shù)據(jù)庫(kù)系統(tǒng)中，可用樹來(lái)組織信息；在分析算法的行為時(shí)，可用樹來(lái)描述其執(zhí)行過(guò)程等等。10/8/20242第六章樹和二叉樹

6.1樹的定義和基本術(shù)語(yǔ)遞歸定義：樹(Tree)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱為空樹，否則它滿足如下兩個(gè)條件：（1）有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；（2）其余的結(jié)點(diǎn)可分為m(m>=0)個(gè)互不相交的子集T1,T2,T3…Tm，其中每個(gè)子集又是一棵樹，并稱其為子樹(Subtree)。注：樹的遞歸定義將為實(shí)現(xiàn)樹的各種運(yùn)算提供方便10/8/20243第六章樹和二叉樹樹的示例及分析AACBEDFGHJILKM只有根結(jié)點(diǎn)的樹一般的樹10/8/20244第六章樹和二叉樹樹的其它定義樹是包含n個(gè)結(jié)點(diǎn)的有限集合，在這個(gè)集合上定義了一個(gè)唯一的關(guān)系，它滿足下列條件：集合中存在唯一的一個(gè)結(jié)點(diǎn)，它沒有前驅(qū)，稱為樹的根除根以外，集合中的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)集合中包括樹根結(jié)點(diǎn)的每個(gè)結(jié)點(diǎn)可以有任意多個(gè)（含0個(gè)）后繼樹的抽象數(shù)據(jù)類型定義見教材P118在不同的軟件系統(tǒng)中樹的基本操作可能不同10/8/20245第六章樹和二叉樹樹的表示樹形表示法:最常用的一種表示法。結(jié)點(diǎn)之間的關(guān)系通過(guò)連線表示，方向隱含為從上向下二元組表示法:Tree=(D,R)集合圖表示法:每棵樹對(duì)應(yīng)一個(gè)圓形廣義表表示法:類似廣義表的形式凹入表表示法:類似書的編目注：(1)樹表示方法的多樣性，說(shuō)明樹結(jié)構(gòu)在日常生活中及在計(jì)算機(jī)程序設(shè)計(jì)中的重要性；(2)分等級(jí)的分類方案都可用層次結(jié)構(gòu)表示，也就是可通過(guò)樹形結(jié)構(gòu)描述。10/8/20246第六章樹和二叉樹樹的基本術(shù)語(yǔ)根—樹中唯一沒有前驅(qū)的結(jié)點(diǎn)。度(結(jié)點(diǎn)的度和樹的度)—一個(gè)結(jié)點(diǎn)的子樹的數(shù)目，稱為結(jié)點(diǎn)的度。樹中結(jié)點(diǎn)的度的最大值，稱為樹的度。葉—度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分枝結(jié)點(diǎn)—度大于0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)（分為單分支結(jié)點(diǎn)、雙分支結(jié)點(diǎn)等等）。10/8/20247第六章樹和二叉樹樹的基本術(shù)語(yǔ)（續(xù)）雙親、孩子、祖先、子孫結(jié)點(diǎn)的子樹的根，稱為結(jié)點(diǎn)的孩子，而該結(jié)點(diǎn)則稱為它的孩子的雙親。某結(jié)點(diǎn)的祖先指從根到該結(jié)點(diǎn)的一條路徑上的全部結(jié)點(diǎn)，而結(jié)點(diǎn)的子孫是指該結(jié)點(diǎn)的子樹中的全部結(jié)點(diǎn)。兄弟、堂兄弟—同一個(gè)結(jié)點(diǎn)的孩子，互為兄弟，其雙親為兄弟的結(jié)點(diǎn)稱為堂兄弟。10/8/20248第六章樹和二叉樹樹的基本術(shù)語(yǔ)（續(xù)）結(jié)點(diǎn)的層次、樹的深度(高度)—根的層次為第一層，根的孩子為第二層，一個(gè)結(jié)點(diǎn)的層次為L(zhǎng)，則它的孩子的層次為L(zhǎng)+1。一棵樹中結(jié)點(diǎn)的最大層次，稱為樹的深度或高度。有序樹、無(wú)序樹--若樹中各結(jié)點(diǎn)的子樹是按照一定的次序從左向右安排的，稱為有序樹。否則稱為無(wú)序樹。森林—m(m>=0)棵互不相交的樹的集合。10/8/20249第六章樹和二叉樹6.2二叉樹二叉樹是另一種樹形結(jié)構(gòu)，它的特點(diǎn)是，每個(gè)結(jié)點(diǎn)至多只有兩棵子樹，而且其子樹有左右之分，不能任意顛倒。二叉樹在樹結(jié)構(gòu)的應(yīng)用中起著非常重要的作用，因?yàn)閷?duì)二叉樹的許多操作算法簡(jiǎn)單，而任何樹都可以與二叉樹相互轉(zhuǎn)換，這樣就解決了樹的存儲(chǔ)結(jié)構(gòu)及其運(yùn)算中存在的復(fù)雜性。10/8/202410第六章樹和二叉樹二叉樹的定義定義：二叉樹是由n(n>=0)個(gè)結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。這也是一個(gè)遞歸定義。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。二叉樹不是樹的特殊情況，它們是兩個(gè)概念。二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使只有一棵子樹也要說(shuō)明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差別。二叉樹抽象數(shù)據(jù)類型定義見教材P12110/8/202411第六章樹和二叉樹二叉樹的五種基本形態(tài)

(a)空二叉樹AABABACB

(b)根和空的左右子樹

(c)根和左子樹(d)根和右子樹

(e)根和左右子樹10/8/202412第六章樹和二叉樹二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i>=1)。證明:當(dāng)i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，2i-1=20=1,命題成立。假定第i－1層上至多有2i-2個(gè)結(jié)點(diǎn)。由于二叉樹每個(gè)結(jié)點(diǎn)的度最大為2，故在第i層上最大結(jié)點(diǎn)數(shù)為第i－1層上最大結(jié)點(diǎn)數(shù)的二倍，即2×2i-2＝2i-1。10/8/202413第六章樹和二叉樹二叉樹的性質(zhì)(續(xù))性質(zhì)2：深度為k的二叉樹至多有2k－1個(gè)結(jié)點(diǎn)（k>=1).事實(shí)上，深度為k的二叉樹的最大的結(jié)點(diǎn)數(shù)為二叉樹中每層上的最大結(jié)點(diǎn)數(shù)之和，由性質(zhì)1得到每層上的最大結(jié)點(diǎn)數(shù)，

(第i層上的最大結(jié)點(diǎn)數(shù)）=

2i-1=2k–1

10/8/202414第六章樹和二叉樹二叉樹的性質(zhì)(續(xù))性質(zhì)3：對(duì)任何一棵二叉樹，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0＝n2＋1。事實(shí)上，設(shè)二叉樹中度為1的結(jié)點(diǎn)數(shù)為n1，二叉樹中總結(jié)點(diǎn)數(shù)為N，因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于2，所以有N＝n0＋n1＋n2

另外，除根結(jié)點(diǎn)外,其余結(jié)點(diǎn)都有一個(gè)進(jìn)入分支，設(shè)B為二叉樹中的分支總數(shù),則有

N＝B＋1。由于這些分支都是由度為1和2的結(jié)點(diǎn)射出的,所以有B＝n1+2*n2

從而

N＝B＋1＝n1＋2*n2＋1總之n0+n1+n2=n1+2*n2+1故n0＝n2＋110/8/202415第六章樹和二叉樹滿二叉樹和完全二叉樹一棵深度為k且由2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。其特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。如果深度為k、由n個(gè)結(jié)點(diǎn)的二叉樹中個(gè)結(jié)點(diǎn)能夠與深度為k的順序編號(hào)的滿二叉樹從1到n標(biāo)號(hào)的結(jié)點(diǎn)相對(duì)應(yīng)，則稱這樣的二叉樹為完全二叉樹。在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)，則為完全二叉樹。10/8/202416第六章樹和二叉樹滿二叉樹舉例24536718910111213141510/8/202417第六章樹和二叉樹12345612345712367(a)完全二叉樹(b)非完全二叉樹(c)非完全二叉樹完全二叉樹舉例

10/8/202418第六章樹和二叉樹完全二叉樹的特點(diǎn)及性質(zhì)特點(diǎn)：（1)所有的葉結(jié)點(diǎn)都出現(xiàn)在第k層或k－1層；（2）對(duì)任一結(jié)點(diǎn)，如果其右子樹的最大層次為1，則其左子樹的最大層次為1或l＋1。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

log2n

＋1。假設(shè)此二叉樹的深度為k，則根據(jù)性質(zhì)2及完全二叉樹的定義得到：2k-1－1<n<=2k-1或2k-1<=n<2k取對(duì)數(shù)得到：k－1<log2n<k因?yàn)閗是整數(shù)。所以有：k＝

log2n

＋1。10/8/202419第六章樹和二叉樹完全二叉樹的性質(zhì)性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)（從第1層到第

log2n

+1層，每層從左到右),則對(duì)任一結(jié)點(diǎn)i（1

i

n),有：（1）如果i＝1，則結(jié)點(diǎn)i無(wú)雙親，是二叉樹的根；如果i>1，則其雙親是結(jié)點(diǎn)

i/2

。（2）如果2i>n，則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無(wú)左孩子；否則，其左孩子是結(jié)點(diǎn)2i。（3）如果2i＋1>n，則結(jié)點(diǎn)i無(wú)右孩子；否則，其右孩子是結(jié)點(diǎn)2i＋1。10/8/202420第六章樹和二叉樹完全二叉樹上結(jié)點(diǎn)之間的關(guān)系

[I/2]iI+12i2i+12(I+1)2i+3I+12(I+1)2i+3i2i2i+1(a)I和i+1結(jié)點(diǎn)在同一層(b)I和i+1結(jié)點(diǎn)不在同一層10/8/202421第六章樹和二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)（一）順序存儲(chǔ)結(jié)構(gòu)：用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)元素。把二叉樹的所有結(jié)點(diǎn)安排成為一個(gè)恰當(dāng)?shù)男蛄?，結(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系，用編號(hào)的方法：#definemax-tree-size100Typedef

telemtype

sqbitree[max-tree-size];Sqbitree

bt

10/8/202422第六章樹和二叉樹

順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)從樹根起，自上層至下層，每層自左至右的給所有結(jié)點(diǎn)編號(hào)缺點(diǎn)是有可能對(duì)存儲(chǔ)空間造成極大的浪費(fèi)，在最壞的情況下，一個(gè)深度為H且只有H個(gè)結(jié)點(diǎn)的右單支樹確需要2h-1個(gè)結(jié)點(diǎn)存儲(chǔ)空間。若經(jīng)常需要插入與刪除樹中結(jié)點(diǎn)時(shí)，則不宜采用順序存儲(chǔ)結(jié)構(gòu)。10/8/202423第六章樹和二叉樹二叉樹的順序存儲(chǔ)結(jié)構(gòu)示例

123456完全二叉樹12367非完全二叉樹123456123006710/8/202424第六章樹和二叉樹二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)—二叉鏈表

lchildDatarchildA^BC^D^E^F^^G^^H^頭指針二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)10/8/202425第六章樹和二叉樹

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(續(xù))

二叉樹的二叉鏈表存儲(chǔ)表示

Typedef

struct

BiTNode{

TelemTypedata;

struct

BiTNode*lchild,*rchild;}BiTNode,*BiTree;基本操作的函數(shù)原型說(shuō)明見教材P127三叉鏈表--結(jié)點(diǎn)結(jié)構(gòu)lchilddataparentrchild10/8/202426第六章樹和二叉樹6.3遍歷二叉樹和線索二叉樹1遍歷二叉樹在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點(diǎn)，或者對(duì)樹中全部結(jié)點(diǎn)逐一進(jìn)行某種處理。遍歷二叉樹即按某條搜索路徑巡訪樹中的每一個(gè)結(jié)點(diǎn)，使得每一個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次?！霸L問(wèn)”可以是對(duì)結(jié)點(diǎn)作各種處理，如輸出結(jié)點(diǎn)的信息等。遍歷二叉樹是二叉樹中所有其它運(yùn)算的基礎(chǔ)。10/8/202427第六章樹和二叉樹如何遍歷二叉樹遍歷對(duì)線性結(jié)構(gòu)是容易解決的，而二叉樹是非線性的，因而需要尋找一種規(guī)律，以便使二叉樹上的結(jié)點(diǎn)能排列在一個(gè)線性隊(duì)列上，從而便于遍歷。由二叉樹的遞歸定義，二叉樹的三個(gè)基本組成單元是：根結(jié)點(diǎn)、左子樹和右子樹。A(根結(jié)點(diǎn))(右子樹)(左子樹)10/8/202428第六章樹和二叉樹如何遍歷二叉樹（續(xù)）假如以L、D、R分別表示遍歷左子樹、遍歷根結(jié)點(diǎn)和遍歷右子樹，遍歷整個(gè)二叉樹則有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。若規(guī)定先左后右，則只有前三種情況，分別規(guī)定為：

DLR——先（根）序遍歷，

LDR——中（根）序遍歷，

LRD——后（根）序遍歷。按層次順序?qū)Χ鏄溥M(jìn)行遍歷。10/8/202429第六章樹和二叉樹遍歷二叉樹的遞歸算法先序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）訪問(wèn)根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。中序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）中序遍歷左子樹；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷右子樹。10/8/202430第六章樹和二叉樹如何遍歷二叉樹（續(xù)）后序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問(wèn)根結(jié)點(diǎn)。10/8/202431第六章樹和二叉樹先序遍歷二叉樹的遞歸算法Voidpreorder(BiTreeroot){if(root!=NULL){printf(“%5d”,root->data);preorder(root->lchild);preorder(root->rchild);}}10/8/202432第六章樹和二叉樹中序遍歷二叉樹的遞歸算法Voidinorder(BiTreeroot){if(root!=NULL){inorder(root->lchild);printf(“%5d”,root->data);

inorder(root->rchild);}}10/8/202433第六章樹和二叉樹后序遍歷二叉樹的遞歸算法Voidpostorder(BiTreeroot){if(root!=NULL){postorder(root->lchild);

postorder(root->rchild);printf(“%5d”,root->data);}}10/8/202434第六章樹和二叉樹三種遍歷舉例對(duì)右圖所示的二叉樹，三種遍歷的結(jié)果為：先序：1,2,4,5,3,6中序：4,2,5,1,6,3后序：4,5,2,6,3,112345610/8/202435第六章樹和二叉樹三種遍歷舉例（續(xù)）如右圖所示的二叉樹表達(dá)式

a+b*(c-d)-e/f先序：-+a*b-cd/ef中序：a+b*c-d-e/f后序：abcd-*+ef/-人工處理用中綴形式的算術(shù)表達(dá)式；計(jì)算機(jī)處理使用后綴表達(dá)式易于求值－＋*a/b-dcfe10/8/202436第六章樹和二叉樹三種遞歸算法比較三種遍歷算法不同之處在于訪問(wèn)根結(jié)點(diǎn)和遍歷左、右子樹的先后關(guān)系。若在算法中去掉和遞歸無(wú)關(guān)的輸出語(yǔ)句，則三個(gè)遍歷算法完全相同。從遞歸執(zhí)行過(guò)程的角度看三種遍歷也是完全相同的，參見三種遞歸過(guò)程示意圖P13010/8/202437第六章樹和二叉樹先序遍歷的非遞歸算法Voidpreorder(BiTreeroot){BiTreep,s[N];inttop=0;p=root;while(1){while(p!=NULL){printf(“%5d”,p->data);/*先訪問(wèn)*/top++;s[top]=p;/*進(jìn)棧，保留信息，以便稍后去遍歷右子樹*/p=p->lchild;/*遞歸，一直向左，直到最左點(diǎn)*/}10/8/202438第六章樹和二叉樹先序遍歷的非遞歸算法（續(xù)）

if(top!=0/*如果棧不空*/{p=s[top];top--;p=p->rchild;}/*出棧，找到棧頂結(jié)點(diǎn)的右孩子，轉(zhuǎn)去遞歸*/elsereturn;}}10/8/202439第六章樹和二叉樹二叉樹遍歷算法效率分析在先序遍歷中，每個(gè)結(jié)點(diǎn)只經(jīng)過(guò)一次，中序遍歷中，有左、右孩子的結(jié)點(diǎn)要經(jīng)過(guò)兩次（先去中序遍歷它的左子樹，從左子樹返回時(shí)才訪問(wèn)它），而后序中，有左、右孩子的結(jié)點(diǎn)要經(jīng)過(guò)三次。三種遍歷算法的時(shí)間復(fù)雜度都是O(n)。所需輔助空間為?？臻g，棧的容量為樹的高度，最多不超過(guò)n，所以空間復(fù)雜度也為O(n)。10/8/202440第六章樹和二叉樹二叉樹的層次遍歷層次遍歷的形式有多種，最為常用的是第一種自上而下，自左而右的方式其它層次遍歷形式包括：第二種自底向上，自左向右；第三種自上而下，從第二層開始的各層交替地按自左向右的順序和自右向左的順序；第四種自下而上，各層交替地按自右向左的順序和自左向右的順序。10/8/202441第六章樹和二叉樹二叉樹遍歷算法的應(yīng)用“遍歷”是二叉樹各種操作的基礎(chǔ)，可以在遍歷過(guò)程中對(duì)結(jié)點(diǎn)進(jìn)行各種操作，如：對(duì)于一棵已知樹可求結(jié)點(diǎn)的雙親，求結(jié)點(diǎn)的孩子結(jié)點(diǎn)，判定結(jié)點(diǎn)所在層次，求二叉樹的深度，求二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)等?？稍诒闅v過(guò)程中生成結(jié)點(diǎn)，建立二叉樹的存儲(chǔ)結(jié)構(gòu)。10/8/202442第六章樹和二叉樹利用先序序列建立二叉樹二叉樹及二叉鏈表存儲(chǔ)結(jié)構(gòu)ABCDEFGABDCGEF^^^^^^^^順序讀入字符ABC##DE#G##F###10/8/202443第六章樹和二叉樹利用先序序列建立二叉樹的算法VoidCreateBiTree(BiTNode*t)//構(gòu)造二叉鏈表表示的二叉樹{charc;

c=getchar();if(c==‘#’)return(NULL);else{t=(BiTNode)malloc(sizeof(BiTNode))t–>data=c;//生成根結(jié)點(diǎn)

CreateBiTree(t–>lchild);//構(gòu)造左子樹

CreateBiTree(t–>rchild);}//構(gòu)造右子樹

returnOK;}10/8/202444第六章樹和二叉樹求二叉樹深度的算法int

depth(BiTNodet){inthl,hr;if(!t)return0;else{hl=depth(t->lchild);hr=depth(t->rchild);if(hl>=hr)returnhl+1;elsereturnhr+1;}}10/8/202445第六章樹和二叉樹線索二叉樹遍歷二叉樹實(shí)質(zhì)上是對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化操作。當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí),只能找到結(jié)點(diǎn)的左右孩子的信息,而不能直接得到結(jié)點(diǎn)在任一序列中的前驅(qū)與后繼信息,這種信息只有在遍歷的動(dòng)態(tài)過(guò)程中才能得到。為了能保存遍歷過(guò)程中得到的信息，可為每個(gè)結(jié)點(diǎn)增加兩個(gè)指針域fwd和bkwd，分別指示結(jié)點(diǎn)在任一次序遍歷是得到的前驅(qū)和后繼信息，但這樣做使得結(jié)構(gòu)的存儲(chǔ)密度大大降低。10/8/202446第六章樹和二叉樹線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)有n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域，可利用這些空鏈域來(lái)存放結(jié)點(diǎn)的前驅(qū)和后繼的信息。規(guī)定：若結(jié)點(diǎn)有左子樹，則其lchild域指示其左孩子，否則令lchild指示其前驅(qū)；若結(jié)點(diǎn)有右子樹，則其rchild域指示其右孩子，否則令rchild指示其后繼。為了避免混淆，其結(jié)點(diǎn)結(jié)構(gòu)可增加標(biāo)志域lchildltagdatartagrchild10/8/202447第六章樹和二叉樹線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)（續(xù)）其中:0lchild

域指示結(jié)點(diǎn)的左孩子

ltag={1lchild

域指示結(jié)點(diǎn)的前驅(qū)

0rchild

域指示結(jié)點(diǎn)的右孩子

rtag={1rchild

域指示結(jié)點(diǎn)的后驅(qū)以這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu),叫做線索鏈表,其中指向結(jié)點(diǎn)前驅(qū)與后繼的指針叫做線索.加上線索的二叉樹稱之為線索二叉樹。對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過(guò)程稱為線索化。10/8/202448第六章樹和二叉樹6.4樹和森林主要內(nèi)容：樹的表示及其遍歷操作；森林與二叉樹的對(duì)應(yīng)關(guān)系。樹的三種存儲(chǔ)結(jié)構(gòu)

1、雙親表示法

2、孩子表示法

3、孩子兄弟表示法

10/8/202449第六章樹和二叉樹雙親表示法以一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)種附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在鏈表中的位置,見圖6.13形式說(shuō)明如下：

#defineMAX_TREE_SIZE100

typedef

struct

PTNode

{//結(jié)點(diǎn)結(jié)構(gòu)

ElemTypedata;

intparent;//雙親位置域

}

PTNode;:

typedef

struct{//樹結(jié)構(gòu)

PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}

PTree;缺點(diǎn)：求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)結(jié)構(gòu)10/8/202450第六章樹和二叉樹孩子表示法把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，看作一個(gè)線性鏈表，且以單鏈表作存儲(chǔ)結(jié)構(gòu)，則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表（葉子的孩子鏈表為空表）n個(gè)頭指針又組成一個(gè)線性表，采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)形式說(shuō)明見P136孩子表示法便于那些涉及孩子的操作的實(shí)現(xiàn)，卻不適用于對(duì)雙親的操作?？梢园央p親表示法和孩子表示法結(jié)合起來(lái)，即把雙親表示和孩子鏈表合在一起。10/8/202451第六章樹和二叉樹孩子兄弟表示法以二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)，又稱二叉樹表示法或二叉鏈表表示法。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)，分別命名為firstchild域和nextsibling域樹的二叉鏈表(孩子-兄弟)存儲(chǔ)表示

typedef

struct

CSNode{

ElemTypedata;

struct

CSNode*firstchild,*nextsibling;}CSNode,*CSTree10/8/202452第六章樹和二叉樹孩子兄弟表示法舉例

RBCDEFGABDGEC^^^^^HKAH^K^^F^R^^^注：這種存儲(chǔ)結(jié)構(gòu)便于實(shí)現(xiàn)各種樹的操作10/8/202453第六章樹和二叉樹6.4樹和森林主要內(nèi)容：樹的表示及其遍歷操作；森林與二叉樹的對(duì)應(yīng)關(guān)系。樹的三種存儲(chǔ)結(jié)構(gòu)

1、雙親表示法

2、孩子表示法

3、孩子兄弟表示法

10/8/202454第六章樹和二叉樹孩子兄弟表示法以二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)，又稱二叉樹表示法或二叉鏈表表示法。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)，分別命名為firstchild域和nextsibling域樹的二叉鏈表(孩子-兄弟)存儲(chǔ)表示

typedef

struct

CSNode{

ElemTypedata;

struct

CSNode*firstchild,*nextsibling;}CSNode,*CSTree10/8/202455第六章樹和二叉樹孩子兄弟表示法舉例

RBCDEFGABDGEC^^^^^HKAH^K^^F^R^^^注：這種存儲(chǔ)結(jié)構(gòu)便于實(shí)現(xiàn)各種樹的操作10/8/202456第六章樹和二叉樹森林與二叉樹的轉(zhuǎn)換

由于二叉樹和樹都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則通過(guò)二叉鏈表可導(dǎo)出樹與二叉樹之間的一個(gè)對(duì)應(yīng)關(guān)系。給定一棵樹，可以找到唯一的一棵二叉樹與之對(duì)應(yīng)。從物理結(jié)構(gòu)看，它們的二叉鏈表是相同的，只是解釋不同。10/8/202457第六章樹和二叉樹樹與二叉樹的對(duì)應(yīng)關(guān)系示例ABCEDABCEDABCDE^^^^^^任何一棵和樹對(duì)應(yīng)的二叉樹，其右子樹必空10/8/202458第六章樹和二叉樹森林與二叉樹的轉(zhuǎn)換（續(xù)）若把森林中第二棵樹的根結(jié)點(diǎn)看成是第一棵樹的根結(jié)點(diǎn)的兄弟，則可導(dǎo)出森林和二叉樹的對(duì)應(yīng)關(guān)系森林與二叉樹之間的對(duì)應(yīng)關(guān)系示例見P138森林或樹與二叉樹相互轉(zhuǎn)換的形式定義見P138將樹轉(zhuǎn)換為二叉樹的轉(zhuǎn)換規(guī)則：將樹中每個(gè)結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)轉(zhuǎn)換為二叉樹中對(duì)應(yīng)結(jié)點(diǎn)的左孩子，將第二個(gè)孩子結(jié)點(diǎn)轉(zhuǎn)換為左孩子的右孩子，將第三個(gè)結(jié)點(diǎn)轉(zhuǎn)換為右孩子的右孩子10/8/202459第六章樹和二叉樹樹和森林的遍歷樹的遍歷可有三條搜索路徑先根次序遍歷：若樹不空，則先訪問(wèn)根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。后根次序遍歷：若樹不空，則先依次后根遍歷各棵子樹，然后訪問(wèn)根結(jié)點(diǎn)。按層次遍歷：若樹不空，則自上而下自左至右訪問(wèn)樹中每個(gè)結(jié)點(diǎn)。

樹的遍歷舉例P13910/8/202460第六章樹和二叉樹森林的遍歷先序遍歷(對(duì)森林中的每一棵樹進(jìn)行先根遍歷)

若森林不空，則

訪問(wèn)森林中第一棵樹的根結(jié)點(diǎn);

先序遍歷森林中第一棵樹的子樹森林;

先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。中序遍歷(對(duì)森林中的每一棵樹進(jìn)行后根遍歷)

若森林不空，則中序遍歷森林中第一棵樹的子樹森林;

訪問(wèn)森林中第一棵樹的根結(jié)點(diǎn);

中序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。10/8/202461第六章樹和二叉樹森林的遍歷（續(xù)）森林的遍歷示例見P139當(dāng)森林轉(zhuǎn)換成二叉樹時(shí)，其第一棵樹的子樹森林轉(zhuǎn)換成左子樹，剩余樹的森林轉(zhuǎn)換成右子樹，則上述森林的先序和中序遍歷即為對(duì)應(yīng)的二叉樹的先序和中序遍歷序列。若以二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)時(shí)，樹的先根遍歷和后根遍歷可借用二叉樹的先序和中序遍歷的算法實(shí)現(xiàn)10/8/202462第六章樹和二叉樹6.8哈夫曼樹與哈夫曼編碼

哈夫曼(Huffman)樹，又稱最優(yōu)樹，是一類帶權(quán)路徑長(zhǎng)度最短的樹。從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間路徑上的分支數(shù)稱做路徑長(zhǎng)度。樹根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和稱為樹的路徑長(zhǎng)度。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為從該結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。樹的帶權(quán)路徑長(zhǎng)度為從樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記作WPL(T)=

wklk

(對(duì)所有葉子結(jié)點(diǎn))

。10/8/202463第六章樹和二叉樹最優(yōu)二叉樹(哈夫曼樹)假設(shè)有n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造一棵有

n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi

，則其中帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱做最優(yōu)二叉樹或哈夫曼樹。具有不同帶權(quán)路徑長(zhǎng)度的二叉樹示例見P144，權(quán)值越大的結(jié)點(diǎn)離根越近的二叉樹才是最優(yōu)二叉樹。在解某些判定問(wèn)題時(shí)，利用哈夫曼樹可以得到最佳判定算法，如：編制一個(gè)將百分制轉(zhuǎn)換成五分制的程序。10/8/202464第六章樹和二叉樹哈夫曼算法根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn),其左、右子樹為空樹;在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和;

從F中刪去這兩棵樹，同時(shí)加入剛生成的新樹;

重復(fù)(2)和(3)兩步，直至F中只含一棵樹為止。10/8/202465第六章樹和二叉樹哈夫曼樹的構(gòu)造過(guò)程

abcd7524(a)a7b5cd6(b)a7bcd11(c)abcd18(d)10/8/202466第六章樹和二叉樹哈夫曼編碼哈夫曼樹的應(yīng)用很廣，哈夫曼編碼就是其中的一種。在電報(bào)通訊中，電文是以二進(jìn)制的0,1序列傳送的。發(fā)送端需編碼,接受端需譯碼。等長(zhǎng)編碼是最簡(jiǎn)單的二進(jìn)制編碼方式。但電文中每個(gè)字符的出現(xiàn)頻率不同，采用等長(zhǎng)編碼，傳送電文的總長(zhǎng)度較大。舉例:電文為‘ABACCDA’,設(shè)A,B,C,D的編碼分別為00,01,10,11,則電文為‘00010010101101’總長(zhǎng)為14位。10/8/202467第六章樹和二叉樹哈夫曼編碼（續(xù)）解決辦法之一是采用不等長(zhǎng)編碼，讓出現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長(zhǎng)的編碼，從而可縮短傳送電文的總長(zhǎng)度。若設(shè)A,B,C,D的編碼分別為0,00,1和01，則電文‘ABACCDA’可轉(zhuǎn)換成長(zhǎng)度為9的字符串‘000011010’,此時(shí)電文無(wú)法譯碼。要設(shè)計(jì)長(zhǎng)短不等的編碼，必須是任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴，這種編碼稱為前綴編碼。顯然等長(zhǎng)編碼是前綴編碼。10/8/202468第六章樹和二叉樹哈夫曼編碼（續(xù)）為了使不等長(zhǎng)編碼為前綴編碼，可用該字符集中的每個(gè)字符作為葉子結(jié)點(diǎn)生成一棵編碼二叉樹。如圖所示的二叉樹有4個(gè)葉子結(jié)點(diǎn)A,B,C,D，其二進(jìn)制前綴編碼分別為0,10,110,111。ABCD00011110/8/202469第六章樹和二叉樹哈夫曼編碼（續(xù)）設(shè)每種字符在電文中出現(xiàn)的次數(shù)為wi,其編碼長(zhǎng)度為li,電文中只有n種字符，則電文總長(zhǎng)為

wili.對(duì)應(yīng)二叉樹，若置wi為葉子結(jié)點(diǎn)的權(quán)，li恰為從根到葉子結(jié)點(diǎn)的路徑長(zhǎng)度，則

wili恰為二叉樹上帶權(quán)路徑長(zhǎng)度。為了獲得傳送電文的最短長(zhǎng)度，可將每個(gè)字符的出現(xiàn)頻率作為字符結(jié)點(diǎn)的權(quán)賦予該結(jié)點(diǎn)上，設(shè)計(jì)一棵哈夫曼樹的問(wèn)題，求出此樹的最小帶權(quán)路徑長(zhǎng)度就等于求出了傳送電文的最短長(zhǎng)度。由此得到的二進(jìn)制前綴編碼稱為哈夫曼編碼。10/8/202470第六章樹和二叉樹哈夫曼編碼（續(xù)）以電文中每個(gè)字符出現(xiàn)的頻率作為葉子結(jié)點(diǎn)的權(quán)值來(lái)設(shè)計(jì)哈夫曼樹。求每個(gè)葉結(jié)點(diǎn)的編碼。從葉到根通過(guò)依次找雙親來(lái)進(jìn)行，但編碼串是從根開始的。對(duì)每個(gè)編碼進(jìn)行譯碼。譯碼就是要對(duì)一個(gè)二進(jìn)制串所代表的字符給出它唯一的解釋，需從根到葉進(jìn)行查找。注：哈夫曼樹沒有度為1的結(jié)點(diǎn)，一棵有n個(gè)葉子結(jié)點(diǎn)的二叉哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)。10/8/202471第六章樹和二叉樹哈夫曼編碼舉例例：已知某系統(tǒng)在通信聯(lián)絡(luò)中可能出現(xiàn)8種字符，其概率為0.05,0.29,0.07,0.08,0.l4,0.23,0.03,0.11,試設(shè)計(jì)哈夫曼編碼。解：設(shè)權(quán)w=(5,29,7,8,14,23,3,11),根據(jù)哈夫曼算法可構(gòu)造哈夫曼樹。5311237814290000000111111110/8/202472第六章樹和二叉樹樹的計(jì)數(shù)具有n個(gè)結(jié)點(diǎn)的不同形態(tài)的樹有多少棵？二叉樹T和T’相似是指：二者都為空樹或者二者均不為空樹，且它們的左右子樹分別相似。二叉樹T和T’等價(jià)是指：二者不僅相似，而且所有對(duì)應(yīng)結(jié)點(diǎn)上的數(shù)據(jù)元素均相同。二叉樹的計(jì)數(shù)問(wèn)題就是求具有n個(gè)結(jié)點(diǎn)、互不相似的二叉樹的數(shù)目？含有n個(gè)結(jié)點(diǎn)、互不相似的二叉樹有10/8/202473第六章樹和二叉樹二叉樹的確定任意一棵二叉樹結(jié)點(diǎn)的先序序列和中序序列是唯一的。問(wèn)題：給定結(jié)點(diǎn)的先序序列和中序序列，能否確定一棵二叉樹？是否唯一？分析：二叉樹的先序遍歷是先訪問(wèn)根結(jié)點(diǎn)D；其次遍歷左子樹L，最后遍歷右子樹R。在結(jié)點(diǎn)的先序序列中，第一個(gè)結(jié)點(diǎn)必是根D。10/8/202474第六章樹和二叉樹二叉樹的確定（續(xù)）另一方面，由于中序遍歷是先遍歷左子樹L，然后訪問(wèn)根D，最后遍歷右子樹R，則根結(jié)點(diǎn)D將中序序列分割成兩部分：在D之前是左子樹結(jié)點(diǎn)的