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

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

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

Summary5.7線索二叉樹(Threadedbinarytree)5.1.1樹的定義(Definition)

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

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

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

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

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

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

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

對于第一層,因?yàn)闃渲械牡谝粚由现挥幸粋€結(jié)點(diǎn),即整個樹的根結(jié)點(diǎn),而由i=1代入mi-1,得mi-1=m1-1=1,也同樣得到只有一個結(jié)點(diǎn),顯然結(jié)論成立。

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

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

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

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

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

深度為k，有n個結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng)時，稱為~

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

binarytreetraversal)

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

BinaryTreeTraversal:

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

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

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

binarytreetraversal)

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

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

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

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

若二叉樹非空（假設(shè)其高度為h），則：（1）訪問根結(jié)點(diǎn)（第1層）；（2）從左到右訪問第2層的所有結(jié)點(diǎn)；（3）從左到右訪問第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); /*訪問結(jié)點(diǎn)*/

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

Example5.2假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲,試設(shè)計(jì)一個算法,輸出一棵給定二叉樹的所有葉子結(jié)點(diǎn)。Solution：輸出一棵二叉樹的所有葉子結(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)棧，在棧不空時循環(huán)：出棧p，訪問*p結(jié)點(diǎn)，若右孩子不空將該右孩子結(jié)點(diǎn)進(jìn)棧，若左孩子不空再將該左孩子結(jié)點(diǎn)進(jìn)棧。5.4.3二叉樹遍歷非遞歸算法

(Non-recursivealgorithmof

binarytreetraversal)

voidPreOrder2(BTNode*b){ BTNode*St[MaxSize],*p;inttop=-1; top++;St[top]=b;//根結(jié)點(diǎn)入棧 while(top>-1) //棧不為空時循環(huán) {p=St[top];top--;//退棧并訪問該結(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.中序遍歷非遞歸算法由中序遍歷過程可知，采用一個棧保存需要返回的結(jié)點(diǎn)指針，先掃描（并非訪問）根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并將它們一一進(jìn)棧。

然后出棧一個結(jié)點(diǎn)，顯然該結(jié)點(diǎn)沒有左孩子結(jié)點(diǎn)或者左孩子結(jié)點(diǎn)已訪問過（進(jìn)一步說明該結(jié)點(diǎ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);//訪問之 p=p->rchild; //掃描*p的右孩子結(jié)點(diǎn) }}//endofwhile(top>-1||p!=NULL)}找*b的最左下結(jié)點(diǎn)3.后序遍歷非遞歸算法

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

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

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

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

用ch掃描采用括號表示法表示二叉樹的字符串。分以下幾種情況：①若ch='('：則將前面剛創(chuàng)建的結(jié)點(diǎn)作為雙親結(jié)點(diǎn)進(jìn)棧,并置k=1,表示其后創(chuàng)建的結(jié)點(diǎn)將作為這個結(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二叉樹的基本運(yùn)算算法實(shí)現(xiàn)(Algorithmimplementationofbasicoperations)

④其他情況,表示要創(chuàng)建一個結(jié)點(diǎn),并根據(jù)k值建立它與棧中結(jié)點(diǎn)之間的聯(lián)系,當(dāng)k=1時,表示這個結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的左孩子結(jié)點(diǎn),當(dāng)k=2時,表示這個結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。如此循環(huán)直到str處理完畢。算法中使用一個棧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; /*建立的二叉樹初始時為空*/ch=str[j];while(ch!='\0') /*str未掃描完時循環(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為二叉樹的根結(jié)點(diǎn)*/ b=p; else/*已建立二叉樹根結(jié)點(diǎn)*/{switch(k){ case1:St[top]->lchild=p;break; case2:St[top]->rchild=p;break; }}} j++;ch=str[j];}}

例如,對于括號表示串A(B(D(,G)),C(E,F)),建立二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)的過程如下表所示。ch算法執(zhí)行的操作St中元素A建立A結(jié)點(diǎn),b指向該結(jié)點(diǎn)(A為樹的根）空(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é)束

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

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

Example5.5假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu),設(shè)計(jì)一個算法輸出從每個葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。解：這里用層次遍歷方法,設(shè)計(jì)的隊(duì)列為非循環(huán)順序隊(duì)列(類似于第3章3.2.4小節(jié)中求解迷宮問題時使用的隊(duì)列),將所有已掃描過的結(jié)點(diǎn)指針進(jìn)隊(duì),并在隊(duì)列中保存雙親結(jié)點(diǎn)的位置。當(dāng)找到一個葉子結(jié)點(diǎn)時,在隊(duì)列中通過雙親結(jié)點(diǎn)的位置輸出該葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。對應(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)沒有雙親結(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*/}同一棵二叉樹具有惟一先序序列、中序序列和后序序列,但不同的二叉樹可能具有相同的先序序列、中序序列和后序序列。例如,教材中P176

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

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

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

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

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

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

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

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

根結(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)造二叉樹的算法：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)造左子樹*/s->rchild=CreateBT1(pre+k+1,p+1,n-k-1);/*構(gòu)造右子樹*/returns;}

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

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

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

Forexample,已知中序序列為DGBAECF,后序序列為GDBEFCA。對應(yīng)的構(gòu)造二叉樹的過程如下所示。根結(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)造二叉樹的算法：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線索二叉樹的概念(concept)

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

我們知道,遍歷二叉樹的結(jié)果是一個結(jié)點(diǎn)的線性序列?？梢岳眠@些空鏈域存放指向結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)的指針。這樣的指向該線性序列中的“前驅(qū)”和“后繼”的指針,稱作線索。5.7線索二叉樹(Threadedbinarytree)在結(jié)點(diǎn)的存儲結(jié)構(gòu)上增加兩個標(biāo)志位來區(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)這樣,每個結(jié)點(diǎn)的存儲結(jié)構(gòu)如下：ltaglchilddatarchildrtag按上述原則在二叉樹的每個結(jié)點(diǎn)上加上線索的二叉樹稱作線索二叉樹。

對二叉樹以某種方式遍歷使其變?yōu)榫€索二叉樹的過程稱作按該方式對二叉樹進(jìn)行線索化。

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

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

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

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

先序線索二叉樹和后序線索二叉樹較少用到。

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

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

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

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

5.8.1哈夫曼樹的定義(DefinitionofHuffmantree)例有4個結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點(diǎn)的二叉樹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ù)哈夫曼樹的定義,一棵二叉樹要使其WPL值最小,必須使權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn),而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。那么如何構(gòu)造一棵哈夫曼樹呢?其方法如下:(1)由給定的n個權(quán)值{W1,W2,...,Wn},

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

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

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

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