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

第六章樹和二叉樹6.1

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

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

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

(a)空二叉樹AABABACB

(b)根和空的左右子樹

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

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

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

2i-1=2k–1

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

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

N＝B＋1。由于這些分支都是由度為1和2的結(jié)點射出的,所以有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個結(jié)點的二叉樹稱為滿二叉樹。其特點是每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)。如果深度為k、由n個結(jié)點的二叉樹中個結(jié)點能夠與深度為k的順序編號的滿二叉樹從1到n標(biāo)號的結(jié)點相對應(yīng)，則稱這樣的二叉樹為完全二叉樹。在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續(xù)若干個結(jié)點，則為完全二叉樹。10/8/202416第六章樹和二叉樹滿二叉樹舉例24536718910111213141510/8/202417第六章樹和二叉樹12345612345712367(a)完全二叉樹(b)非完全二叉樹(c)非完全二叉樹完全二叉樹舉例

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

log2n

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

log2n

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

log2n

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

i

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

i/2

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

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

telemtype

sqbitree[max-tree-size];Sqbitree

bt

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

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

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

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

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

二叉樹的二叉鏈表存儲表示

Typedef

struct

BiTNode{

TelemTypedata;

struct

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

DLR——先（根）序遍歷，

LDR——中（根）序遍歷，

LRD——后（根）序遍歷。按層次順序?qū)Χ鏄溥M(jìn)行遍歷。10/8/202429第六章樹和二叉樹遍歷二叉樹的遞歸算法先序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。中序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。10/8/202430第六章樹和二叉樹如何遍歷二叉樹（續(xù)）后序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。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第六章樹和二叉樹三種遍歷舉例對右圖所示的二叉樹，三種遍歷的結(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ī)處理使用后綴表達(dá)式易于求值－＋*a/b-dcfe10/8/202436第六章樹和二叉樹三種遞歸算法比較三種遍歷算法不同之處在于訪問根結(jié)點和遍歷左、右子樹的先后關(guān)系。若在算法中去掉和遞歸無關(guān)的輸出語句，則三個遍歷算法完全相同。從遞歸執(zhí)行過程的角度看三種遍歷也是完全相同的，參見三種遞歸過程示意圖P13010/8/202437第六章樹和二叉樹先序遍歷的非遞歸算法Voidpreorder(BiTreeroot){BiTreep,s[N];inttop=0;p=root;while(1){while(p!=NULL){printf(“%5d”,p->data);/*先訪問*/top++;s[top]=p;/*進(jìn)棧，保留信息，以便稍后去遍歷右子樹*/p=p->lchild;/*遞歸，一直向左，直到最左點*/}10/8/202438第六章樹和二叉樹先序遍歷的非遞歸算法（續(xù)）

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

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

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

ltag={1lchild

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

0rchild

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

rtag={1rchild

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

1、雙親表示法

2、孩子表示法

3、孩子兄弟表示法

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

#defineMAX_TREE_SIZE100

typedef

struct

PTNode

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

ElemTypedata;

intparent;//雙親位置域

}

PTNode;:

typedef

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

PTNodenodes[MAX_TREE_SIZE];

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

}

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

typedef

struct

CSNode{

ElemTypedata;

struct

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

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

1、雙親表示法

2、孩子表示法

3、孩子兄弟表示法

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

typedef

struct

CSNode{

ElemTypedata;

struct

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

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

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

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

若森林不空，則

訪問森林中第一棵樹的根結(jié)點;

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

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

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

訪問森林中第一棵樹的根結(jié)點;

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

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

wklk

(對所有葉子結(jié)點)

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

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

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

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

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

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

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

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