數(shù)據(jù)結(jié)構(gòu)與算法-第五章 Trees

數(shù)據(jù)結(jié)構(gòu)與算法DataStructuresandAlgorithmAnalysis信息工程學(xué)院SchoolofInformationEngineering第5章樹(shù)形結(jié)構(gòu)(Trees)5.1樹(shù)的基本概念(Basicconceptoftree)

5.2二叉樹(shù)概念和性質(zhì)(Propertyandconceptofbinarytree)5.3二叉樹(shù)存儲(chǔ)結(jié)構(gòu)(Physicalstoragestructureofbinarytree)5.4二叉樹(shù)的遍歷(Binarytreetraversals)5.5二叉樹(shù)的基本運(yùn)算及其實(shí)現(xiàn)(Algorithmimplementationandbasicoperationsofbinarytree)5.6二叉樹(shù)的構(gòu)造(Constructionofbinarytree)5.8哈夫曼樹(shù)(Huffmantree)

Summary5.7線(xiàn)索二叉樹(shù)(Threadedbinarytree)5.1.1樹(shù)的定義(Definition)

5.1.3樹(shù)的基本術(shù)語(yǔ)(Basicterminology)5.1.2樹(shù)的表示(Representation)5.1.4樹(shù)的性質(zhì)(Property)5.1.5樹(shù)的基本運(yùn)算(Basicoperation)5.1.6樹(shù)的存儲(chǔ)結(jié)構(gòu)(Physicalstructure)5.1樹(shù)的基本概念(Basicconceptoftree)

5.1.1樹(shù)的定義(Definition)形式化定義：

樹(shù)：T＝{K,R}。K是包含n個(gè)結(jié)點(diǎn)的有窮集合(n>0),關(guān)系R滿(mǎn)足以下條件:

(1)有且僅有一個(gè)結(jié)點(diǎn)k0∈K,它對(duì)于關(guān)系R來(lái)說(shuō)沒(méi)有前驅(qū)結(jié)點(diǎn),結(jié)點(diǎn)k0稱(chēng)作樹(shù)的根。(2)除結(jié)點(diǎn)k0外,K中的每個(gè)結(jié)點(diǎn)對(duì)于關(guān)系R來(lái)說(shuō)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)。(3)K中每個(gè)結(jié)點(diǎn)對(duì)于關(guān)系R來(lái)說(shuō)可以有多個(gè)后繼結(jié)點(diǎn)。遞歸定義：樹(shù)是由n(n≥0)個(gè)結(jié)點(diǎn)組成的有限集合(記為T(mén))。其中,

如果n=0,它是一棵空樹(shù),這是樹(shù)的特例；如果n>0,這n個(gè)結(jié)點(diǎn)中存在(有僅存在)一個(gè)結(jié)點(diǎn)作為樹(shù)的根結(jié)點(diǎn),簡(jiǎn)稱(chēng)為根(root),其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,,T2,…,Tm,其中每一棵子集本身又是一棵符合本定義的樹(shù),稱(chēng)為根root的子樹(shù)。A只有根結(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM有子樹(shù)的樹(shù)根子樹(shù)5.1.2樹(shù)的表示(Representation)(1)樹(shù)形表示法。這是樹(shù)的最基本的表示,使用一棵倒置的樹(shù)表示樹(shù)結(jié)構(gòu),非常直觀(guān)和形象。下圖就是采用這種表示法。(2)文氏圖表示法。使用集合以及集合的包含關(guān)系描述樹(shù)結(jié)構(gòu)。下圖就是樹(shù)的文氏圖表示法。(3)凹入表示法。使用線(xiàn)段的伸縮描述樹(shù)結(jié)構(gòu)。下圖是樹(shù)的凹入表示法。(4)括號(hào)表示法。

將樹(shù)的根結(jié)點(diǎn)寫(xiě)在括號(hào)的左邊,除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)寫(xiě)在括號(hào)中并用逗號(hào)間隔來(lái)描述樹(shù)結(jié)構(gòu)。下圖是樹(shù)的括號(hào)表示法。5.1.3樹(shù)的基本術(shù)語(yǔ)(Basicterminology)結(jié)點(diǎn)(node)——度不為零的結(jié)點(diǎn)稱(chēng)為非終端結(jié)點(diǎn)，又叫分支結(jié)點(diǎn)。度為零的結(jié)點(diǎn)稱(chēng)為終端結(jié)點(diǎn)或葉結(jié)點(diǎn)。結(jié)點(diǎn)的度(degree)——結(jié)點(diǎn)擁有的子樹(shù)數(shù)葉子(leaf)——度為0的結(jié)點(diǎn)孩子(child)——在一棵樹(shù)中，每個(gè)結(jié)點(diǎn)的后繼雙親(parents)——孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的~兄弟(sibling)——同一雙親的孩子樹(shù)的度(degree)——一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù)結(jié)點(diǎn)的層次(level)——從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……深度(depth)——樹(shù)中結(jié)點(diǎn)的最大層次數(shù)祖先(ancestor)----從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)堂兄弟(cousin)——雙親在同一層次的結(jié)點(diǎn)有序樹(shù)(orderedtree)——將樹(shù)中結(jié)點(diǎn)的各個(gè)子樹(shù)看成從左至右是有次序的第一孩子(firstchild)----有序樹(shù)中最左邊的子樹(shù)的根森林(forest)——m(m0)棵互不相交的樹(shù)的集合對(duì)樹(shù)中各個(gè)結(jié)點(diǎn)而言，其子樹(shù)的集合即為森林ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹(shù)的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹(shù)的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先5.1.4樹(shù)的性質(zhì)(Property)Property1樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。Prove：根據(jù)樹(shù)的定義,在一棵樹(shù)中,除樹(shù)根結(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)有且僅有一個(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。Property2度為m的樹(shù)中第i層上至多有mi-1個(gè)結(jié)點(diǎn),這里應(yīng)有i≥1。

Prove(采用數(shù)學(xué)歸納法)

對(duì)于第一層,因?yàn)闃?shù)中的第一層上只有一個(gè)結(jié)點(diǎn),即整個(gè)樹(shù)的根結(jié)點(diǎn),而由i=1代入mi-1,得mi-1=m1-1=1,也同樣得到只有一個(gè)結(jié)點(diǎn),顯然結(jié)論成立。

假設(shè)對(duì)于第(i-1)層(i＞1)命題成立,即度為m的樹(shù)中第(i-1)層上至多有mi-2個(gè)結(jié)點(diǎn),則根據(jù)樹(shù)的度的定義,度為m的樹(shù)中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子結(jié)點(diǎn),所以第i層上的結(jié)點(diǎn)數(shù)至多為第(i-1)層上結(jié)點(diǎn)數(shù)的m倍,即至多為mi-2×m=mi-1個(gè),這與命題相同,故命題成立。Property3高度為h的m次樹(shù)至多有個(gè)結(jié)點(diǎn)。Prove：由樹(shù)的性質(zhì)2可知,第i層上最多結(jié)點(diǎn)數(shù)為mi-1(i=1,2,…,h),顯然當(dāng)高度為h的m次樹(shù)(即度為m的樹(shù))上每一層都達(dá)到最多結(jié)點(diǎn)數(shù)時(shí),整個(gè)m次樹(shù)具有最多結(jié)點(diǎn)數(shù),因此有：整個(gè)樹(shù)的最多結(jié)點(diǎn)數(shù)=每一層最多結(jié)點(diǎn)數(shù)之和=m0+m1+m2+…+mh-1=。Property4具有n個(gè)結(jié)點(diǎn)的m次樹(shù)的最小高度為logm(n(m-1)+1)。Prove：設(shè)具有n個(gè)結(jié)點(diǎn)的m次樹(shù)的高度為h,若在該樹(shù)中前h-1層都是滿(mǎn)的,即每一層的結(jié)點(diǎn)數(shù)都等于mi-1個(gè)(1≤i≤h-1),第h層(即最后一層)的結(jié)點(diǎn)數(shù)可能滿(mǎn),也可能不滿(mǎn),則該樹(shù)具有最小的高度。其高度h可計(jì)算如下：根據(jù)樹(shù)的性質(zhì)3可得： ＜n≤乘(m-1)后得： mh-1＜n(m-1)+1≤mh以m為底取對(duì)數(shù)后得：h-1＜logm(n(m-1)+1)≤h即 logm(n(m-1)+1)≤h＜logm(n(m-1)+1)+1因h只能取整數(shù),所以 h=logm(n(m-1)+1)結(jié)論得證。5.1.5樹(shù)的基本運(yùn)算(Basicoperation)Treeoperationcanbeclassfiedintothreetypes:

First,尋找滿(mǎn)足某種特定關(guān)系的結(jié)點(diǎn),如尋找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等；Second,插入或刪除某個(gè)結(jié)點(diǎn),如在樹(shù)的當(dāng)前結(jié)點(diǎn)上插入一個(gè)新結(jié)點(diǎn)或刪除當(dāng)前結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)等；Third,遍歷樹(shù)中每個(gè)結(jié)點(diǎn),這里著重介紹。樹(shù)的遍歷(traversal)運(yùn)算是指按某種方式訪(fǎng)問(wèn)樹(shù)中的每一個(gè)結(jié)點(diǎn)且每一個(gè)結(jié)點(diǎn)只被訪(fǎng)問(wèn)一次。樹(shù)的遍歷運(yùn)算的算法主要有先根遍歷和后根遍歷兩種。注意,下面的先根遍歷和后根遍歷算法都是遞歸的。1.先根遍歷(PreorderTraversal)

先根遍歷過(guò)程為：(1)訪(fǎng)問(wèn)根結(jié)點(diǎn)；(2)按照從左到右的次序先根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。2.后根遍歷(PostorderTraversal)后根遍歷過(guò)程為：(1)按照從左到右的次序后根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)；(2)訪(fǎng)問(wèn)根結(jié)點(diǎn)。ABCDEFGHIJKLMNO先根遍歷：后根遍歷：層次遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO5.1.6樹(shù)的存儲(chǔ)結(jié)構(gòu)(Physicalstructure)1.雙親存儲(chǔ)結(jié)構(gòu)

這種存儲(chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)結(jié)構(gòu),用一組連續(xù)空間存儲(chǔ)樹(shù)的所有結(jié)點(diǎn),同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)偽指針指示其雙親結(jié)點(diǎn)的位置。樹(shù)的雙親存儲(chǔ)結(jié)構(gòu)示意圖2.孩子鏈存儲(chǔ)結(jié)構(gòu)孩子鏈存儲(chǔ)結(jié)構(gòu)可按樹(shù)的度(即樹(shù)中所有結(jié)點(diǎn)度的最大值)設(shè)計(jì)結(jié)點(diǎn)的孩子結(jié)點(diǎn)指針域個(gè)數(shù)。下圖(a)的樹(shù)對(duì)應(yīng)的孩子鏈存儲(chǔ)結(jié)構(gòu)如圖(b)所示。樹(shù)的孩子鏈存儲(chǔ)結(jié)構(gòu)示意圖3.孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)

孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)是為每個(gè)結(jié)點(diǎn)設(shè)計(jì)三個(gè)域：一個(gè)數(shù)據(jù)元素域,一個(gè)該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)指針域,一個(gè)該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)指針域。下圖(a)的樹(shù)對(duì)應(yīng)的孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)如圖(b)所示。樹(shù)的孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)示意圖5.2.1二叉樹(shù)概念(Concept)5.2.2二叉樹(shù)性質(zhì)(Property)5.2.3二叉樹(shù)與樹(shù)、森林之間的轉(zhuǎn)換(Transformationbetweenbinarytreeandtree,binarytreeandforest)5.2二叉樹(shù)概念和性質(zhì)(Propertyandconceptofbinarytree)5.2.1二叉樹(shù)的概念(Binarytree)另一種樹(shù)型結(jié)構(gòu)。Characteristic每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)(即不存在度大于2的結(jié)點(diǎn))二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能任意顛倒BasicformsA只有根結(jié)點(diǎn)的二叉樹(shù)空二叉樹(shù)AB右子樹(shù)為空AB左子樹(shù)為空ABC左、右子樹(shù)均非空在一棵二叉樹(shù)中,如果所有分支結(jié)點(diǎn)都有左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn),并且葉結(jié)點(diǎn)都集中在二叉樹(shù)的最下一層,稱(chēng)為滿(mǎn)二叉樹(shù)(FullBinaryTree)?？梢詫?duì)滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào),約定編號(hào)從樹(shù)根為1開(kāi)始,按照層數(shù)從小到大、同一層從左到右的次序進(jìn)行。若二叉樹(shù)中最多只有最下面兩層的結(jié)點(diǎn)的度數(shù)可以小于2,并且最下面一層的葉結(jié)點(diǎn)都依次排列在該層最左邊的位置上,稱(chēng)為完全二叉樹(shù)(CompleteBinaryTree)。

深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)為~

12311458912136710141512311458912671012345671234565.2.2二叉樹(shù)性質(zhì)(Property)Property1非空二叉樹(shù)上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1。

證明：設(shè)二叉樹(shù)上葉結(jié)點(diǎn)數(shù)為n0,單分支結(jié)點(diǎn)數(shù)為n1,雙分支結(jié)點(diǎn)數(shù)為n2,則總結(jié)點(diǎn)數(shù)=n0+n1+n2。

在一棵二叉樹(shù)中,所有結(jié)點(diǎn)的分支數(shù)(即度數(shù))應(yīng)等于單分支結(jié)點(diǎn)數(shù)加上雙分支結(jié)點(diǎn)數(shù)的2倍,即總的分支數(shù)=n1+2n2。由于二叉樹(shù)中除根結(jié)點(diǎn)以外,每個(gè)結(jié)點(diǎn)都有惟一的一個(gè)分支指向它,因此二叉樹(shù)中有：

總的分支數(shù)=總結(jié)點(diǎn)數(shù)-1。由上述三個(gè)等式可得：n1+2n2=n0+n1+n2-1即：n0=n2+1Property2非空二叉樹(shù)上第i層上至多有2i-1個(gè)結(jié)點(diǎn),這里應(yīng)有i≥1。證明：用歸納法證明之

i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，是對(duì)的假設(shè)對(duì)所有j(1j<i)命題成立，即第j層上至多有個(gè)結(jié)點(diǎn)那么，第i-1層至多有個(gè)結(jié)點(diǎn)又二叉樹(shù)每個(gè)結(jié)點(diǎn)的度至多為2第i層上最大結(jié)點(diǎn)數(shù)是第i-1層的2倍，即故命題得證Property3高度為h的二叉樹(shù)至多有2h-1個(gè)結(jié)點(diǎn)(h≥1)證明：由性質(zhì)2，可得深度為k的二叉樹(shù)最大結(jié)點(diǎn)數(shù)是Property4對(duì)完全二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)(1≤i≤n,n≥1,n為結(jié)點(diǎn)數(shù))有：

(1)若i≤n/2,即2i≤n,則編號(hào)為i的結(jié)點(diǎn)為分支結(jié)點(diǎn),否則為葉子結(jié)點(diǎn)。(2)若n為奇數(shù),則每個(gè)分支結(jié)點(diǎn)都既有左孩子結(jié)點(diǎn),也有右孩子結(jié)點(diǎn)；若n為偶數(shù),則編號(hào)最大的分支結(jié)點(diǎn)(編號(hào)為)只有左孩子結(jié)點(diǎn),沒(méi)有右孩子結(jié)點(diǎn),其余分支結(jié)點(diǎn)都有左、右孩子結(jié)點(diǎn)。

(3)若編號(hào)為i的結(jié)點(diǎn)有左孩子結(jié)點(diǎn),則左孩子結(jié)點(diǎn)的編號(hào)為2i；若編號(hào)為i的結(jié)點(diǎn)有右孩子結(jié)點(diǎn),則右孩子結(jié)點(diǎn)的編號(hào)為(2i+1)。(4)除樹(shù)根結(jié)點(diǎn)外,若一個(gè)結(jié)點(diǎn)的編號(hào)為i,則它的雙親結(jié)點(diǎn)的編號(hào)為i/2,也就是說(shuō),當(dāng)i為偶數(shù)時(shí),其雙親結(jié)點(diǎn)的編號(hào)為i/2,它是雙親結(jié)點(diǎn)的左孩子結(jié)點(diǎn),當(dāng)i為奇數(shù)時(shí),其雙親結(jié)點(diǎn)的編號(hào)為(i-1)/2,它是雙親結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。Property5具有n個(gè)(n＞0)結(jié)點(diǎn)的完全二叉樹(shù)的高度為log2n+1或log2n+1。

由完全二叉樹(shù)的定義和二叉樹(shù)的性質(zhì)3可推出。5.2.3二叉樹(shù)與樹(shù)、森林之間的轉(zhuǎn)換(Transformation)1、將樹(shù)轉(zhuǎn)換成二叉樹(shù)(TreetoBinaryTree)加線(xiàn)：在兄弟之間加一連線(xiàn)抹線(xiàn)：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系旋轉(zhuǎn)：以樹(shù)的根結(jié)點(diǎn)為軸心，將整樹(shù)順時(shí)針轉(zhuǎn)45°ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹(shù)轉(zhuǎn)換成的二叉樹(shù)其右子樹(shù)一定為空2、將二叉樹(shù)轉(zhuǎn)換成樹(shù)(BinaryTreetoTree)加線(xiàn)：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線(xiàn)連起抹線(xiàn)：抹掉原二叉樹(shù)中雙親與右孩子之間的連線(xiàn)調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI3、森林轉(zhuǎn)換成二叉樹(shù)(ForesttoBinaryTree)將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù)將每棵樹(shù)的根結(jié)點(diǎn)用線(xiàn)相連以第一棵樹(shù)根結(jié)點(diǎn)為二叉樹(shù)的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹(shù)型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ4、二叉樹(shù)轉(zhuǎn)換成森林(BinaryTreetoForest)抹線(xiàn)：將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線(xiàn)，及沿右分支搜索到的所有右孩子間連線(xiàn)全部抹掉，使之變成孤立的二叉樹(shù)還原：將孤立的二叉樹(shù)還原成樹(shù)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ5.3.1二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)

(Sequentstorageofbinarytree)5.3.2二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(Linkedstorageofbinarytree)5.3二叉樹(shù)存儲(chǔ)結(jié)構(gòu)(Physicalstoragestructureofbinarytree)

二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的存放次序是：對(duì)該樹(shù)中每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào),其編號(hào)從小到大的順序就是結(jié)點(diǎn)存放在連續(xù)存儲(chǔ)單元的先后次序。若把二叉樹(shù)存儲(chǔ)到一維數(shù)組中,則完全二叉樹(shù)上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中下標(biāo)為i-1的分量中。

樹(shù)中各結(jié)點(diǎn)的編號(hào)與等高度的完全二叉樹(shù)中對(duì)應(yīng)位置上結(jié)點(diǎn)的編號(hào)相同。

5.3.1二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)

(Sequentstorageofbinarytree)ABCDEFGHIJK123456789101112131415順序存儲(chǔ)結(jié)構(gòu)

在二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)中,結(jié)點(diǎn)的結(jié)構(gòu)如下:

typedefstructnode{ ElemTypedata; structnode*lchild,*rchild;}BTNode;

其中,data表示值域,用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素,lchild和rchild分別表示左指針域和右指針域,用于分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)(即左、右子樹(shù)的根結(jié)點(diǎn))的存儲(chǔ)位置。5.3.2二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(Linkedstorageofbinarytree)Binarytreeanditslinkedstorage5.4.1二叉樹(shù)遍歷的概念(Conceptofbinarytreetraversal)5.4.2二叉樹(shù)遍歷遞歸算法(Recursivealgorithmof

binarytreetraversal)5.4.3二叉樹(shù)遍歷非遞歸算法(Non-recursivealgorithmof

binarytreetraversal)

5.4二叉樹(shù)的遍歷(Binarytreetraversal)5.4.1ConceptofBinaryTreeTraversal

BinaryTreeTraversal:

按照一定次序訪(fǎng)問(wèn)樹(shù)中所有結(jié)點(diǎn),并且每個(gè)結(jié)點(diǎn)僅被訪(fǎng)問(wèn)一次的過(guò)程。它是最基本的運(yùn)算,是二叉樹(shù)中所有其他運(yùn)算的基礎(chǔ)。二叉樹(shù)遍歷方法先序遍歷(preordertraversal)：先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后分別先序遍歷左子樹(shù)、右子樹(shù)。中序遍歷(inordertraversal)：先中序遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù)。后序遍歷(postordertraversal)：先后序遍歷左、右子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)。按層次遍歷(level-ordertravesal)：從上到下、從左到右訪(fǎng)問(wèn)各結(jié)點(diǎn)。DLRLDR、LRD、DLRRDL、RLD、DRLThreeRecursiveAlgorithms：

voidPreOrder(BTNode*b) /*先序遍歷的遞歸算法*/{

if(b!=NULL){printf("%c",b->data);/*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/ PreOrder(b->lchild); PreOrder(b->rchild);}}先序遍歷序列：ABDGCEF5.4.2二叉樹(shù)遍歷遞歸算法(Recursivealgorithmof

binarytreetraversal)

voidInOrder(BTNode*b) /*中序遍歷的遞歸算法*/{

if(b!=NULL){InOrder(b->lchild); printf("%c",b->data);/*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/ InOrder(b->rchild); }}中序遍歷序列：DGBAECF

voidPostOrder(BTNode*b)/*后序遍歷遞歸算法*/{

if(b!=NULL){PostOrder(b->lchild); PostOrder(b->rchild); printf("%c",b->data);/*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/ }}后序遍歷序列：GDBEFCALevelOrderTraversal其過(guò)程是：

若二叉樹(shù)非空（假設(shè)其高度為h），則：（1）訪(fǎng)問(wèn)根結(jié)點(diǎn)（第1層）；（2）從左到右訪(fǎng)問(wèn)第2層的所有結(jié)點(diǎn)；（3）從左到右訪(fǎng)問(wèn)第3層的所有結(jié)點(diǎn)、…、第h層的所有結(jié)點(diǎn)。層次遍歷序列：ABCDEFGvoidLevelOrder(BTNode*b){BTNode*p;BTNode*qu[MaxSize]; /*定義環(huán)形隊(duì)列,存放結(jié)點(diǎn)指針*/intfront,rear; /*定義隊(duì)頭和隊(duì)尾指針*/front=rear=-1; /*置隊(duì)列為空隊(duì)列*/rear++;qu[rear]=b; /*根結(jié)點(diǎn)指針進(jìn)入隊(duì)列*/while(front!=rear) /*隊(duì)列不為空*/{front=(front+1)%MaxSize; p=qu[front]; /*隊(duì)頭出隊(duì)列*/ printf("%c",p->data); /*訪(fǎng)問(wèn)結(jié)點(diǎn)*/

if(p->lchild!=NULL) /*有左孩子時(shí)將其進(jìn)隊(duì)*/ {rear=(rear+1)%MaxSize; qu[rear]=p->lchild; } if(p->rchild!=NULL) /*有右孩子時(shí)將其進(jìn)隊(duì)*/ {rear=(rear+1)%MaxSize; qu[rear]=p->rchild; }}}

Example5.2假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ),試設(shè)計(jì)一個(gè)算法,輸出一棵給定二叉樹(shù)的所有葉子結(jié)點(diǎn)。Solution：輸出一棵二叉樹(shù)的所有葉子結(jié)點(diǎn)的遞歸模型f()如下：f(b)：不做任何事件 若b=NULLf(b)：輸出*b結(jié)點(diǎn)的data域若*b為葉子結(jié)點(diǎn)f(b)：f(b->lchild);f(b->rchild) 其他情況

voidDispLeaf(BTNode*b){

if(b!=NULL){ if(b->lchild==NULL&&b->rchild==NULL) printf("%c",b->data); else {DispLeaf(b->lchild); DispLeaf(b->rchild);}}}先序遍歷非遞歸算法

先將根結(jié)點(diǎn)進(jìn)棧，在棧不空時(shí)循環(huán)：出棧p，訪(fǎng)問(wèn)*p結(jié)點(diǎn)，若右孩子不空將該右孩子結(jié)點(diǎn)進(jìn)棧，若左孩子不空再將該左孩子結(jié)點(diǎn)進(jìn)棧。5.4.3二叉樹(shù)遍歷非遞歸算法

(Non-recursivealgorithmof

binarytreetraversal)

voidPreOrder2(BTNode*b){ BTNode*St[MaxSize],*p;inttop=-1; top++;St[top]=b;//根結(jié)點(diǎn)入棧 while(top>-1) //棧不為空時(shí)循環(huán) {p=St[top];top--;//退棧并訪(fǎng)問(wèn)該結(jié)點(diǎn) printf("%c",p->data);if(p->rchild!=NULL)//右孩子結(jié)點(diǎn)入棧 {top++;St[top]=p->rchild;}if(p->lchild!=NULL)//左孩子結(jié)點(diǎn)入棧 {top++;St[top]=p->lchild;}}}2.中序遍歷非遞歸算法由中序遍歷過(guò)程可知，采用一個(gè)棧保存需要返回的結(jié)點(diǎn)指針，先掃描（并非訪(fǎng)問(wèn)）根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并將它們一一進(jìn)棧。

然后出棧一個(gè)結(jié)點(diǎn)，顯然該結(jié)點(diǎn)沒(méi)有左孩子結(jié)點(diǎn)或者左孩子結(jié)點(diǎn)已訪(fǎng)問(wèn)過(guò)（進(jìn)一步說(shuō)明該結(jié)點(diǎn)的左子樹(shù)均已訪(fǎng)問(wèn)），則訪(fǎng)問(wèn)它。然后掃描該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，將其進(jìn)棧，再掃描該右孩子結(jié)點(diǎn)的所有左結(jié)點(diǎn)并一一進(jìn)棧，如此這樣，直到?？諡橹?。voidInOrder2(BTNode*b){ BTNode*St[MaxSize],*p;inttop=-1; p=b; while(top>-1||p!=NULL) {while(p!=NULL)//掃描*p的所有左結(jié)點(diǎn)并進(jìn)棧 {top++;St[top]=p; p=p->lchild; } if(top>-1) {p=St[top];top--; //出棧*p結(jié)點(diǎn) printf("%c",p->data);//訪(fǎng)問(wèn)之 p=p->rchild; //掃描*p的右孩子結(jié)點(diǎn) }}//endofwhile(top>-1||p!=NULL)}找*b的最左下結(jié)點(diǎn)3.后序遍歷非遞歸算法

由后序遍歷過(guò)程可知，采用一個(gè)棧保存需要返回的結(jié)點(diǎn)指針，先掃描根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并一一進(jìn)棧，出棧一個(gè)結(jié)點(diǎn)*b即當(dāng)前結(jié)點(diǎn)，然后掃描該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)并入棧，再掃描該右孩子結(jié)點(diǎn)的所有左結(jié)點(diǎn)并入棧。當(dāng)一個(gè)結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)均訪(fǎng)問(wèn)后再訪(fǎng)問(wèn)該結(jié)點(diǎn)，如此這樣，直到?？諡橹?。難點(diǎn)：如何判斷一個(gè)結(jié)點(diǎn)*b的右孩子結(jié)點(diǎn)已訪(fǎng)問(wèn)過(guò)，為此用p保存剛剛訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)（初值為NULL），若b->rchild==p成立（在后序遍歷中，*b的右孩子結(jié)點(diǎn)一定剛好在*b之前訪(fǎng)問(wèn)），說(shuō)明*b的左右子樹(shù)均已訪(fǎng)問(wèn)，現(xiàn)在應(yīng)訪(fǎng)問(wèn)*b。voidPostOrder2(BTNode*b){ BTNode*St[MaxSize];BTNode*p; intflag,top=-1; //棧指針置初值 do {while(b!=NULL) //將*b的所有左結(jié)點(diǎn)進(jìn)棧 { top++;St[top]=b; b=b->lchild; } p=NULL; //p指向棧頂結(jié)點(diǎn)的前一個(gè)已訪(fǎng)問(wèn)的結(jié)點(diǎn) flag=1; //設(shè)置b的訪(fǎng)問(wèn)標(biāo)記為已訪(fǎng)問(wèn)過(guò)找最左下結(jié)點(diǎn)while(top!=-1&&flag==1){b=St[top];//取出當(dāng)前的棧頂元素 if(b->rchild==p)

{printf("%c",b->data); //訪(fǎng)問(wèn)*b結(jié)點(diǎn) top--;p=b; //p指向則被訪(fǎng)問(wèn)的結(jié)點(diǎn) } else {b=b->rchild; //b指向右孩子結(jié)點(diǎn) flag=0; //設(shè)置未被訪(fǎng)問(wèn)的標(biāo)記 }}//endofwhile(top!=-1&&flag==1)}while(top!=-1);}b的右孩子不存在或已訪(fǎng)問(wèn)過(guò)從上述過(guò)程可知，棧中保存的是當(dāng)前結(jié)點(diǎn)*b的所有祖先結(jié)點(diǎn)（均未訪(fǎng)問(wèn)過(guò)）。

例如，書(shū)中例子求一個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)。5.5.1二叉樹(shù)的基本運(yùn)算概述（Basicoperationsofbinarytree)5.5.2二叉樹(shù)的基本運(yùn)算算法實(shí)現(xiàn)(Algorithmimplementationofbasicoperations)5.5二叉樹(shù)的基本運(yùn)算及其實(shí)現(xiàn)(Algorithmimplementationandbasicoperationsofbinarytree)歸納起來(lái),二叉樹(shù)有以下基本運(yùn)算：(1)創(chuàng)建二叉樹(shù)CreateBTNode(*b,*str)：根據(jù)二叉樹(shù)括號(hào)表示法的字符串*str生成對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(2)查找結(jié)點(diǎn)FindNode(*b,x)：在二叉樹(shù)b中尋找data域值為x的結(jié)點(diǎn),并返回指向該結(jié)點(diǎn)的指針。(3)找孩子結(jié)點(diǎn)LchildNode(p)和RchildNode(p)：分別求二叉樹(shù)中結(jié)點(diǎn)*p的左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)。5.5.1二叉樹(shù)的基本運(yùn)算概述（Basicoperationsofbinarytree)

(4)求高度BTNodeDepth(*b)：求二叉樹(shù)b的高度。若二叉樹(shù)為空,則其高度為0；否則,其高度等于左子樹(shù)與右子樹(shù)中的最大高度加l。(5)輸出二叉樹(shù)DispBTNode(*b)：以括號(hào)表示法輸出一棵二叉樹(shù)。(1)創(chuàng)建二叉樹(shù)CreateBTNode(*b,*str)

用ch掃描采用括號(hào)表示法表示二叉樹(shù)的字符串。分以下幾種情況：①若ch='('：則將前面剛創(chuàng)建的結(jié)點(diǎn)作為雙親結(jié)點(diǎn)進(jìn)棧,并置k=1,表示其后創(chuàng)建的結(jié)點(diǎn)將作為這個(gè)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)；②若ch=')'：表示棧中結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)處理完畢,退棧；③若ch=','：表示其后創(chuàng)建的結(jié)點(diǎn)為右孩子結(jié)點(diǎn)；5.5.2二叉樹(shù)的基本運(yùn)算算法實(shí)現(xiàn)(Algorithmimplementationofbasicoperations)

④其他情況,表示要?jiǎng)?chuàng)建一個(gè)結(jié)點(diǎn),并根據(jù)k值建立它與棧中結(jié)點(diǎn)之間的聯(lián)系,當(dāng)k=1時(shí),表示這個(gè)結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的左孩子結(jié)點(diǎn),當(dāng)k=2時(shí),表示這個(gè)結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。如此循環(huán)直到str處理完畢。算法中使用一個(gè)棧St保存雙親結(jié)點(diǎn),top為其棧指針,k指定其后處理的結(jié)點(diǎn)是雙親結(jié)點(diǎn)(保存在棧中)的左孩子結(jié)點(diǎn)(k=1)還是右孩子結(jié)點(diǎn)(k=2)。

voidCreateBTNode(BTNode*&b,char*str){BTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;b=NULL; /*建立的二叉樹(shù)初始時(shí)為空*/ch=str[j];while(ch!='\0') /*str未掃描完時(shí)循環(huán)*/{ switch(ch){ case'(':top++;St[top]=p;k=1;break; /*為左孩子結(jié)點(diǎn)*/ case')':top--;break; case',':k=2;break; /*為孩子結(jié)點(diǎn)右結(jié)點(diǎn)*/

default:p=(BTNode*)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL)/**p為二叉樹(shù)的根結(jié)點(diǎn)*/ b=p; else/*已建立二叉樹(shù)根結(jié)點(diǎn)*/{switch(k){ case1:St[top]->lchild=p;break; case2:St[top]->rchild=p;break; }}} j++;ch=str[j];}}

例如,對(duì)于括號(hào)表示串A(B(D(,G)),C(E,F)),建立二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過(guò)程如下表所示。ch算法執(zhí)行的操作St中元素A建立A結(jié)點(diǎn),b指向該結(jié)點(diǎn)(A為樹(shù)的根）空(A結(jié)點(diǎn)進(jìn)棧,k=1AB建立B結(jié)點(diǎn),因k=1,將其作為A結(jié)點(diǎn)的左孩子結(jié)點(diǎn)A(B結(jié)點(diǎn)進(jìn)棧,k=1ABD建立D結(jié)點(diǎn),因k=1,將其作為B結(jié)點(diǎn)的左孩子結(jié)點(diǎn)ABch算法執(zhí)行的操作St中元素(D結(jié)點(diǎn)進(jìn)棧,k=1ABD,k=2ABDG建立G結(jié)點(diǎn),因k=2,將其作為D結(jié)點(diǎn)的右孩子結(jié)點(diǎn)ABD)退棧一次AB)退棧一次A,k=2AC建立C結(jié)點(diǎn),因k=2,將其作為A結(jié)點(diǎn)的右孩子結(jié)點(diǎn)A(C結(jié)點(diǎn)進(jìn)棧,k=1ACE建立E結(jié)點(diǎn),因k=1,將其作為C結(jié)點(diǎn)的左孩子結(jié)點(diǎn)AC,k=2ACch算法執(zhí)行的操作St中元素F建立F結(jié)點(diǎn),因k=2,將其作為C結(jié)點(diǎn)的右孩子結(jié)點(diǎn)AC)退棧一次A)退棧一次空ch掃描完畢算法結(jié)束

生成的二叉樹(shù)＝＞(2)查找結(jié)點(diǎn)FindNode(*b,x)

采用先序遍歷遞歸算法查找值為x的結(jié)點(diǎn)。找到后返回其指針,否則返回NULL。算法如下：

BTNode*FindNode(BTNode*b,ElemTypex){BTNode*p;if(b==NULL)returnNULL;elseif(b->data==x)returnb;else{p=FindNode(b->lchild,x); if(p!=NULL)returnp; elsereturnFindNode(b->rchild,x);}}(3)找孩子結(jié)點(diǎn)LchildNode(p)和RchildNode(p)

直接返回*p結(jié)點(diǎn)的左孩子結(jié)點(diǎn)或右孩子結(jié)點(diǎn)的指針。算法如下：

BTNode*LchildNode(BTNode*p){

returnp->lchild;}BTNode*RchildNode(BTNode*p){

returnp->rchild;}(4)求高度BTNodeDepth(*b)求二叉樹(shù)的高度的遞歸模型f()如下：f(NULL)=0f(b)=MAX{f(b->lchild),f(b->rchild)}+1其他情況對(duì)應(yīng)的算法如下：intBTNodeDepth(BTNode*b){intlchilddep,rchilddep;if(b==NULL)return(0);/*空樹(shù)的高度為0*/else{lchilddep=BTNodeDepth(b->lchild); /*求左子樹(shù)的高度為lchilddep*/ rchilddep=BTNodeDepth(b->rchild); /*求右子樹(shù)的高度為rchilddep*/ return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);}}(5)輸出二叉樹(shù)DispBTNode(*b)其過(guò)程是：對(duì)于非空二叉樹(shù)b,先輸出其元素值,當(dāng)存在左孩子結(jié)點(diǎn)或右孩子結(jié)點(diǎn)時(shí),輸出一個(gè)“(”符號(hào),然后遞歸處理左子樹(shù),輸出一個(gè)“,”符號(hào),遞歸處理右子樹(shù),最后輸出一個(gè)“)”符號(hào)。

對(duì)應(yīng)的遞歸算法如下：voidDispBTNode(BTNode*b){ if(b!=NULL) {printf("%c",b->data); if(b->lchild!=NULL||b->rchild!=NULL) { printf("("); DispBTNode(b->lchild); /*遞歸處理左子樹(shù)*/ if(b->rchild!=NULL)printf(","); DispBTNode(b->rchild); /*遞歸處理右子樹(shù)*/ printf(")"); } }}

Example5.5假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu),設(shè)計(jì)一個(gè)算法輸出從每個(gè)葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。解：這里用層次遍歷方法,設(shè)計(jì)的隊(duì)列為非循環(huán)順序隊(duì)列(類(lèi)似于第3章3.2.4小節(jié)中求解迷宮問(wèn)題時(shí)使用的隊(duì)列),將所有已掃描過(guò)的結(jié)點(diǎn)指針進(jìn)隊(duì),并在隊(duì)列中保存雙親結(jié)點(diǎn)的位置。當(dāng)找到一個(gè)葉子結(jié)點(diǎn)時(shí),在隊(duì)列中通過(guò)雙親結(jié)點(diǎn)的位置輸出該葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。對(duì)應(yīng)的算法如下：voidAllPath(BTNode*b){

structsnode{BTNode*node; /*存放當(dāng)前結(jié)點(diǎn)指針*/ intparent; /*存放雙親結(jié)點(diǎn)在隊(duì)列中的位置*/}q[MaxSize]; /*定義順序隊(duì)列*/intfront,rear,p; /*定義隊(duì)頭和隊(duì)尾指針*/front=rear=-1; /*置隊(duì)列為空隊(duì)列*/rear++;q[rear].node=b;/*根結(jié)點(diǎn)指針進(jìn)入隊(duì)列*/q[rear].parent=-1; /*根結(jié)點(diǎn)沒(méi)有雙親結(jié)點(diǎn)*/

while(front<rear) /*隊(duì)列不為空*/{front++;b=q[front].node; /*隊(duì)頭出隊(duì)列*/if(b->lchild==NULL&&b->rchild==NULL) {printf("%c到根結(jié)點(diǎn)路徑:",b->data); p=front; while(q[p].parent!=-1) {printf("%c->",q[p].node->data); p=q[p].parent;} printf("%c\n",q[p].node->data); } if(b->lchild!=NULL) /*左孩子結(jié)點(diǎn)入隊(duì)列*/ {rear++; q[rear].node=b->lchild; q[rear].parent=front;}if(b->rchild!=NULL) /*右孩子結(jié)點(diǎn)入隊(duì)列*/ {rear++;q[rear].node=b->rchild; q[rear].parent=front;}}/*endofwhile*/}同一棵二叉樹(shù)具有惟一先序序列、中序序列和后序序列,但不同的二叉樹(shù)可能具有相同的先序序列、中序序列和后序序列。例如,教材中P176

如圖7.11所示的5棵二叉樹(shù),先序序列都為ABC。如圖7.12所示的5棵二叉樹(shù),中序序列都為ACB。如圖7.13所示的5棵二叉樹(shù),后序序列都為CBA。5.6二叉樹(shù)的構(gòu)造(Constructionofbinarytree)

顯然,僅由一個(gè)先序序列(或中序序列、后序序列),無(wú)法確定這棵二叉樹(shù)的樹(shù)形。如果同時(shí)知道一棵二叉樹(shù)的先序序列和中序序列,或者同時(shí)知道中序序列和后序序列,就能確定這棵二叉樹(shù)。但是，同時(shí)知道先序序列和后序序列仍不能確定二叉樹(shù)的樹(shù)形。如圖7.11和7.13中除第一棵外的4棵二叉樹(shù)先序序列都是ABC，后序序列都是CBA。

Theorem5.1：任何n(n≥0)個(gè)不同結(jié)點(diǎn)的二又樹(shù),都可由它的中序序列和先序序列惟一地確定。

采用數(shù)學(xué)歸納法證明。

當(dāng)n=0時(shí),二叉樹(shù)為空,結(jié)論正確。假設(shè)結(jié)點(diǎn)數(shù)小于n的任何二叉樹(shù),都可以由其先序序列和中序序列惟一地確定。已知某棵二叉樹(shù)具有n(n＞0)個(gè)不同結(jié)點(diǎn),其先序序列是a0a1…an-1；中序序列是b0b1…bk-1bkbk+1…bn-1。

因?yàn)樵谙刃虮闅v過(guò)程中,訪(fǎng)問(wèn)根結(jié)點(diǎn)后,緊跟著遍歷左子樹(shù),最后再遍歷右子樹(shù)。所以,a0必定是二叉樹(shù)的根結(jié)點(diǎn),而且a0必然在中序序列中出現(xiàn)。也就是說(shuō),在中序序列中必有某個(gè)bk(0≤k≤n-1)就是根結(jié)點(diǎn)a0。

由于bk是根結(jié)點(diǎn),而在中序遍歷過(guò)程中,先遍歷左子樹(shù),再訪(fǎng)問(wèn)根結(jié)點(diǎn),最后再遍歷右子樹(shù)。所以在中序序列中,b0b1…bk-1必是根結(jié)點(diǎn)bk(也就是a0)左子樹(shù)的中序序列,即bk的左子樹(shù)有k個(gè)結(jié)點(diǎn)(注意,k=0表示結(jié)點(diǎn)bk沒(méi)有左子樹(shù)。)而bk+1…bn-1必是根結(jié)點(diǎn)bk(也就是a0)右子樹(shù)的中序序列,即bk的右子樹(shù)有n-k-1個(gè)結(jié)點(diǎn)(注意,k=n-1表示結(jié)點(diǎn)bk沒(méi)有右子樹(shù)。)。另外,在先序序列中,緊跟在根結(jié)點(diǎn)a0之后的k個(gè)結(jié)點(diǎn)a1…ak就是左子樹(shù)的先序序列,ak+1…an-1這n-k-1就是右子樹(shù)的先序序列。根據(jù)歸納假設(shè),由于子先序序列a1…ak和子中序序列b0b1…bk-1可以惟一地確定根結(jié)點(diǎn)a0的左子樹(shù),而子先序序列ak+1…an-1和子中序序列bk+1…bn-1可以惟一地確定根結(jié)點(diǎn)a0的右子樹(shù)。綜上所述,這棵二叉樹(shù)的根結(jié)點(diǎn)己經(jīng)確定,而且其左、右子樹(shù)都惟一地確定了,所以整個(gè)二叉樹(shù)也就惟一地確定了。

Forexample,已知先序序列為ABDGCEF,中序序列為DGBAECF,則構(gòu)造二叉樹(shù)的過(guò)程如下所示。

根結(jié)點(diǎn)：A左先序:BDG左中序:DGB右先序:CEF右中序:ECF根結(jié)點(diǎn)：B左先序:DG左中序:DG右先序:空右中序:空根結(jié)點(diǎn)：D左先序:空左中序:空右先序:G右中序:G根結(jié)點(diǎn)：G左先序:空左中序:空右先序:空右中序:空根結(jié)點(diǎn)：C左先序:E左中序:E右先序:F右中序:F根結(jié)點(diǎn)：E左先序:空左中序:空右先序:空右中序:空根結(jié)點(diǎn)：F左先序:空左中序:空右先序:空右中序:空由上述定理得到以下構(gòu)造二叉樹(shù)的算法：BTNode*CreateBT1(char*pre,char*in,intn){BTNode*s;char*p;intk;if(n<=0)returnNULL;s=(BTNode*)malloc(sizeof(BTNode));/*創(chuàng)建結(jié)點(diǎn)*s*/s->data=*pre;for(p=in;p<in+n;p++)/*在中序中找為*ppos的位置k*/ if(*p==*pre) break;k=p-in;s->lchild=CreateBT1(pre+1,in,k); /*遞歸構(gòu)造左子樹(shù)*/s->rchild=CreateBT1(pre+k+1,p+1,n-k-1);/*構(gòu)造右子樹(shù)*/returns;}

Theorem5.2：任何n(n＞0)個(gè)不同結(jié)點(diǎn)的二又樹(shù),都可由它的中序序列和后序序列惟一地確定。

同樣采用數(shù)學(xué)歸納法證明。

實(shí)際上,對(duì)于根結(jié)點(diǎn)ak的左右子樹(shù),在確定左右子樹(shù)的子中序序列后,不需要確定左右子樹(shù)的整個(gè)子后序序列,只需確定子中序序列中全部字符在后序序列中最右邊的那個(gè)字符即可,因?yàn)檫@個(gè)字符就是子樹(shù)的根結(jié)點(diǎn)。

Forexample,已知中序序列為DGBAECF,后序序列為GDBEFCA。對(duì)應(yīng)的構(gòu)造二叉樹(shù)的過(guò)程如下所示。根結(jié)點(diǎn)：A左中序:DGB左根:B右中序:ECF右根:C根結(jié)點(diǎn)：B左中序:DG左根:D右中序:空右根:空根結(jié)點(diǎn)：D左中序:空左根:空右中序:G右根:G根結(jié)點(diǎn)：G左中序:空左根:空右中序:空右根:空根結(jié)點(diǎn)：C左中序:E左根:E右中序:F右根:F根結(jié)點(diǎn)：E左中序:空左根:空右中序:空右根:空根結(jié)點(diǎn)：F左中序:空左根:空右中序:空右根:空由上述定理得到以下構(gòu)造二叉樹(shù)的算法：BTNode*CreateBT2(char*post,char*in,intn){BTNode*s;charr，*p；intk;if(n<=0)returnNULL;r=*(post+n-1);//根結(jié)點(diǎn)s=(BTNode*)malloc(sizeof(BTNode));s->data=r;for(p=in;p<in+n;p++)if(*p==r)break;k=p-in;s->lchild=CreateBT2(post,in,k);s->rchild=CreateBT2(post+k,p+1,n-k-1);returns;}5.7.1線(xiàn)索二叉樹(shù)的概念(concept)

對(duì)于具有n個(gè)結(jié)點(diǎn)的二叉樹(shù),采用二叉鏈存儲(chǔ)結(jié)構(gòu)時(shí),每個(gè)結(jié)點(diǎn)有兩個(gè)指針域,總共有2n個(gè)指針域,又由于只有n-1個(gè)結(jié)點(diǎn)被有效指針?biāo)赶?n個(gè)結(jié)點(diǎn)中只有樹(shù)根結(jié)點(diǎn)沒(méi)有被有效指針域所指向),則共有2n-(n-1)=n+1個(gè)空鏈域,

我們知道,遍歷二叉樹(shù)的結(jié)果是一個(gè)結(jié)點(diǎn)的線(xiàn)性序列?？梢岳眠@些空鏈域存放指向結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)的指針。這樣的指向該線(xiàn)性序列中的“前驅(qū)”和“后繼”的指針,稱(chēng)作線(xiàn)索。5.7線(xiàn)索二叉樹(shù)(Threadedbinarytree)在結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)上增加兩個(gè)標(biāo)志位來(lái)區(qū)分這兩種情況：左標(biāo)志ltag:0表示lchild指向左孩子結(jié)點(diǎn)1表示lchild指向前驅(qū)結(jié)點(diǎn)右標(biāo)志rtag:0表示rchild指向右孩子結(jié)點(diǎn)1表示rchild指向后繼結(jié)點(diǎn)這樣,每個(gè)結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)如下：ltaglchilddatarchildrtag按上述原則在二叉樹(shù)的每個(gè)結(jié)點(diǎn)上加上線(xiàn)索的二叉樹(shù)稱(chēng)作線(xiàn)索二叉樹(shù)。

對(duì)二叉樹(shù)以某種方式遍歷使其變?yōu)榫€(xiàn)索二叉樹(shù)的過(guò)程稱(chēng)作按該方式對(duì)二叉樹(shù)進(jìn)行線(xiàn)索化。

為使算法設(shè)計(jì)方便,在線(xiàn)索二叉樹(shù)中再增加一個(gè)頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的data域?yàn)榭?；lchild指向無(wú)線(xiàn)索時(shí)的根結(jié)點(diǎn),ltag為0；rchild指向按某種方式遍歷二叉樹(shù)時(shí)的最后一個(gè)結(jié)點(diǎn),rtag為1。

(a)是中序線(xiàn)索二叉樹(shù)(中序序列為：DGBAECF).(b)是先序線(xiàn)索二叉樹(shù)(先序序列為：ABDGCEF).(c)是后序線(xiàn)索二叉樹(shù)(后序序列為：GDBEFCA)。圖中實(shí)線(xiàn)表示二叉樹(shù)原來(lái)指針?biāo)傅慕Y(jié)點(diǎn),虛線(xiàn)表示線(xiàn)索二叉樹(shù)所添加的線(xiàn)索。5.7.2線(xiàn)索化二叉樹(shù)(Threadingbinarytree)建立線(xiàn)索二叉樹(shù),或者說(shuō),對(duì)二叉樹(shù)線(xiàn)索化,實(shí)質(zhì)上就是遍歷一棵二叉樹(shù),在遍歷的過(guò)程中,檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空。如果為空,將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線(xiàn)索。另外,在對(duì)一棵二叉樹(shù)添加線(xiàn)索時(shí),我們創(chuàng)建一個(gè)頭結(jié)點(diǎn),并建立頭結(jié)點(diǎn)與二叉樹(shù)的根結(jié)點(diǎn)的線(xiàn)索。對(duì)二叉樹(shù)線(xiàn)索化后,還須建立最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的線(xiàn)索。下面以中序線(xiàn)索二叉樹(shù)為例,討論建立線(xiàn)索二叉樹(shù)的算法。

為了實(shí)現(xiàn)線(xiàn)索化二叉樹(shù),將前面二叉樹(shù)結(jié)點(diǎn)的類(lèi)型定義修改如下：typedefstructnode{ElemTypedata; /*結(jié)點(diǎn)數(shù)據(jù)域*/intltag,rtag; /*增加的線(xiàn)索標(biāo)記*/structnode*lchild; /*左孩子或線(xiàn)索指針*/structnode*rchild; /*右孩子或線(xiàn)索指針*/}TBTNode; /*線(xiàn)索樹(shù)結(jié)點(diǎn)類(lèi)型定義*/下面是建立中序線(xiàn)索二叉樹(shù)的算法。

CreaThread(b)算法是將以二叉鏈存儲(chǔ)的二叉樹(shù)b進(jìn)行中序線(xiàn)索化,并返回線(xiàn)索化后頭結(jié)點(diǎn)的指針root。Thread(p)算法用于對(duì)于以*p為根結(jié)點(diǎn)的二叉樹(shù)中序線(xiàn)索化。在整個(gè)算法中p總是指向當(dāng)前被線(xiàn)索化的結(jié)點(diǎn),而pre作為全局變量,指向剛剛訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn),*pre是*p的前驅(qū)結(jié)點(diǎn),*p是*pre的后繼結(jié)點(diǎn)。

CreaThread(b)算法思路是：

先創(chuàng)建頭結(jié)點(diǎn)*root,其lchild域?yàn)殒溨羔?rchild域?yàn)榫€(xiàn)索。將rchild指針指向*b,如果b二叉樹(shù)為空,則將其lchild指向自身。否則將*root的lchild指向*b結(jié)點(diǎn),p指向*b結(jié)點(diǎn),pre指向*root結(jié)點(diǎn)。再調(diào)用Thread(b)對(duì)整個(gè)二叉樹(shù)線(xiàn)索化。最后加入指向頭結(jié)點(diǎn)的線(xiàn)索,并將頭結(jié)點(diǎn)的rchild指針域線(xiàn)索化為指向最后一個(gè)結(jié)點(diǎn)(由于線(xiàn)索化直到p等于NULL為止,所以最后一個(gè)結(jié)點(diǎn)為*pre)。TBTNode*CreaThread(TBTNode*b)/*中序線(xiàn)索化二叉樹(shù)*/{TBTNode*root;root=(TBTNode*)malloc(sizeof(TBTNode));/*創(chuàng)建頭結(jié)點(diǎn)*/root->ltag=0;root->rtag=1;root->rchild=b;if(b==NULL)root->lchild=root; /*空二叉樹(shù)*/else{root->lchild=b; pre=root; /*pre是*p的前驅(qū)結(jié)點(diǎn),供加線(xiàn)索用*/ Thread(b); /*中序遍歷線(xiàn)索化二叉樹(shù)*/ pre->rchild=root; /*最后處理,加入指向頭結(jié)點(diǎn)的線(xiàn)索*/ pre->rtag=1; root->rchild=pre; /*頭結(jié)點(diǎn)右線(xiàn)索化*/}returnroot;}Thread(p)算法思路是：類(lèi)似于中序遍歷的遞歸算法,在p指針不為NULL時(shí),先對(duì)*p結(jié)點(diǎn)的左子樹(shù)線(xiàn)索化；若*p結(jié)點(diǎn)沒(méi)有左孩子結(jié)點(diǎn),則將其lchild指針線(xiàn)索化為指向其前驅(qū)結(jié)點(diǎn)*pre,否則表示lchild指向其左孩子結(jié)點(diǎn),將其ltag置為0；若*pre結(jié)點(diǎn)的rchild指針為NULL,將其rchild指針線(xiàn)索化為指向其后繼結(jié)點(diǎn)*p,否則rchild表示指向其右孩子結(jié)點(diǎn),將其rtag置為0,再將pre指向*p；最后對(duì)*p結(jié)點(diǎn)的右子樹(shù)線(xiàn)索化。TBTNode*pre; /*全局變量*/voidThread(TBTNode*&p)/*對(duì)二叉樹(shù)b進(jìn)行中序線(xiàn)索化*/{if(p!=NULL) {Thread(p->lchild); /*左子樹(shù)線(xiàn)索化*/ if(p->lchild==NULL)/*前驅(qū)線(xiàn)索*/ {p->lchild=pre;p->ltag=1;}/*建立當(dāng)前結(jié)點(diǎn)的前驅(qū)線(xiàn)索*/ elsep->ltag=0; if(pre->rchild==NULL) /*后繼線(xiàn)索*/ {pre->rchild=p;pre->rtag=1;}/*建立前驅(qū)結(jié)點(diǎn)的后繼線(xiàn)索*/ elsepre->rtag=0;pre=p; Thread(p->rchild); /*遞歸調(diào)用右子樹(shù)線(xiàn)索化*/}}中序遍歷(遞歸)遍歷某種次序的線(xiàn)索二叉樹(shù),就是從該次序下的開(kāi)始結(jié)點(diǎn)出發(fā),反復(fù)找到該結(jié)點(diǎn)在該次序下的后繼結(jié)點(diǎn),直到終端結(jié)點(diǎn)。

先序線(xiàn)索二叉樹(shù)和后序線(xiàn)索二叉樹(shù)較少用到。

在中序線(xiàn)索二叉樹(shù)中,開(kāi)始結(jié)點(diǎn)就是根結(jié)點(diǎn)的最左下結(jié)點(diǎn),而求當(dāng)前結(jié)點(diǎn)在中序序列下的后繼和前驅(qū)結(jié)點(diǎn)的方法如教材中表7.6所示,最后一個(gè)結(jié)點(diǎn)的rchild指針被線(xiàn)索化為指向頭結(jié)點(diǎn)。利用這些條件,在中序線(xiàn)索化二叉樹(shù)中實(shí)現(xiàn)中序遍歷的算法如下：5.7.3遍歷線(xiàn)索化二叉樹(shù)(Traversingthreadedbinarytree)voidThInOrder(TBTNode*tb){TBTNode*p=tb->lchild; /*p指向根結(jié)點(diǎn)*/while(p!=tb){while(p->ltag==0)p=p->lchild; /*找開(kāi)始結(jié)點(diǎn)*/ printf("%c",p->data); /*訪(fǎng)問(wèn)開(kāi)始結(jié)點(diǎn)*/ while(p->rtag==1&&p->rchild!=tb) {p=p->rchild;//后繼結(jié)點(diǎn) printf("%c",p->data); } p=p->rchild; }}5.8哈夫曼樹(shù)(Huffmantree)

5.8.1哈夫曼樹(shù)的定義(DefinitionofHuffmantree)5.8.2構(gòu)造哈夫曼樹(shù)(ConstructingHuffmantree)5.8.3哈夫曼編碼(Huffmancoding)

設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn),那么從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積的和,叫做二叉樹(shù)的帶權(quán)路徑長(zhǎng)度。

其中,n表示葉子結(jié)點(diǎn)的數(shù)目,wi和li分別表示葉子結(jié)點(diǎn)ki的權(quán)值和根到ki之間的路徑長(zhǎng)度(即從葉子結(jié)點(diǎn)到達(dá)根結(jié)點(diǎn)的分支數(shù))。具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù)稱(chēng)為哈夫曼樹(shù)。

5.8.1哈夫曼樹(shù)的定義(DefinitionofHuffmantree)例有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35

根據(jù)哈夫曼樹(shù)的定義,一棵二叉樹(shù)要使其WPL值最小,必須使權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn),而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。那么如何構(gòu)造一棵哈夫曼樹(shù)呢?其方法如下:(1)由給定的n個(gè)權(quán)值{W1,W2,...,Wn},

構(gòu)造n棵只有一個(gè)葉子結(jié)點(diǎn)的二叉樹(shù),從而得到一個(gè)二叉樹(shù)的集合F={T1,T2,...,Tn};5.8.2構(gòu)造哈夫曼樹(shù)(ConstructingHuffmantree)

(2)在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù),這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和;(3)在集合F中刪除作為左、右子樹(shù)的兩棵二叉樹(shù),并將新建立的二叉樹(shù)加入到集合F中;(4)重復(fù)(2)、(3)兩步,當(dāng)F中只剩下一棵二叉樹(shù)時(shí),這棵二叉樹(shù)便是所要建立的哈夫曼樹(shù)。例2w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100

為了實(shí)現(xiàn)構(gòu)造哈夫曼樹(shù)的算法,設(shè)計(jì)哈夫曼樹(shù)中每個(gè)結(jié)點(diǎn)類(lèi)型如下：typedefstruct{ chardata; /*結(jié)點(diǎn)值*/ floatweight; /*權(quán)重*/ intparent; /*雙親結(jié)點(diǎn)*/ intlchild; /*左孩子結(jié)點(diǎn)*/ intrchild; /*右孩子結(jié)點(diǎn)*/}HTNode;

用ht[]數(shù)組存放哈夫曼樹(shù),對(duì)于具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù),總共有2n-1個(gè)結(jié)點(diǎn)（定理7.3）。其算法思路是：n個(gè)葉子結(jié)點(diǎn)只有data和weight域值,先將所有2n-1個(gè)結(jié)點(diǎn)的parent、lchild和rchild