數(shù)據(jù)結(jié)構(gòu)(第6章)-清華大學(xué)

第六章二叉樹(shù)⒈教學(xué)內(nèi)容：6.1定義與性質(zhì)6.2存儲(chǔ)實(shí)現(xiàn)基本操作的實(shí)現(xiàn)6.3二叉樹(shù)的遍歷6.4線(xiàn)索二叉樹(shù)6.5二叉樹(shù)的應(yīng)用⒉教學(xué)目的：⑴深刻理解二叉樹(shù)的定義、性質(zhì)及其存儲(chǔ)方法；⑵熟練掌握二叉樹(shù)的二叉鏈表存儲(chǔ)方式、結(jié)點(diǎn)結(jié)構(gòu)和類(lèi)型定義；⑶理解并掌握二叉樹(shù)的三種遍歷算法；⑷掌握二叉樹(shù)的線(xiàn)索化方法；⑸靈活運(yùn)用二叉樹(shù)的遍歷方法解決相關(guān)的應(yīng)用問(wèn)題；

2/5/20231數(shù)據(jù)結(jié)構(gòu)講義⒊教學(xué)重點(diǎn)：⑴二叉樹(shù)的定義、邏輯特點(diǎn)及性質(zhì)，在二叉樹(shù)上定義的基本運(yùn)算；⑵二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其類(lèi)型說(shuō)明，二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)及其類(lèi)型說(shuō)明；⑶二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的組織方式；⑷二叉樹(shù)的三種遍歷方法及其算法；⑸以遍歷為基礎(chǔ)在二叉樹(shù)上實(shí)現(xiàn)的幾種運(yùn)算；⑹哈夫曼樹(shù)和哈夫曼算法；⒋教學(xué)難點(diǎn)：⑴二叉樹(shù)的遞歸定義；⑵二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的組織方式；⑶三種遍歷的主要區(qū)別；⑷二叉樹(shù)上的復(fù)雜運(yùn)算；⑸哈夫曼算法及其應(yīng)用；⒌學(xué)時(shí)安排：

10學(xué)時(shí)2/5/20232數(shù)據(jù)結(jié)構(gòu)講義6.1定義與性質(zhì)二叉樹(shù)的基本概念二叉樹(shù)的主要性質(zhì)2/5/20233數(shù)據(jù)結(jié)構(gòu)講義1．二叉樹(shù)

二叉樹(shù)（BinaryTree）是個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱(chēng)為根(root)的元素及兩個(gè)不相交的、被分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。當(dāng)集合為空時(shí)，稱(chēng)該二叉樹(shù)為空二叉樹(shù)。在二叉樹(shù)中，一個(gè)元素也稱(chēng)作一個(gè)結(jié)點(diǎn)。二叉樹(shù)是有序的，即若將其左、右子樹(shù)顛倒，就成為另一棵不同的二叉樹(shù)。即使樹(shù)中結(jié)點(diǎn)只有一棵子樹(shù)，也要區(qū)分它是左子樹(shù)還是右子樹(shù)。2/5/20234數(shù)據(jù)結(jié)構(gòu)講義因此二叉樹(shù)具有五種基本形態(tài)，如圖所示。2/5/20235數(shù)據(jù)結(jié)構(gòu)講義2．二叉樹(shù)的相關(guān)概念(1）結(jié)點(diǎn)的度。結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。（2）葉結(jié)點(diǎn)。度為0的結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn)，或者稱(chēng)為終端結(jié)點(diǎn)。（3）分枝結(jié)點(diǎn)。度不為0的結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn)，或者稱(chēng)為非終端結(jié)點(diǎn)。一棵樹(shù)的結(jié)點(diǎn)除葉結(jié)點(diǎn)外，其余的都是分支結(jié)點(diǎn)。（4）左孩子、右孩子、雙親、兄弟。樹(shù)中一個(gè)結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)稱(chēng)為這個(gè)結(jié)點(diǎn)的孩子。在二叉樹(shù)中，左子樹(shù)的根稱(chēng)為左孩子，右子樹(shù)的根稱(chēng)為右孩子。這個(gè)結(jié)點(diǎn)稱(chēng)為它孩子結(jié)點(diǎn)的雙親。具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱(chēng)為兄弟。2/5/20236數(shù)據(jù)結(jié)構(gòu)講義（5）路徑、路徑長(zhǎng)度。如果一棵樹(shù)的一串結(jié)點(diǎn)n1,n2,…,nk有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的父結(jié)點(diǎn)（1≤i<k）,就把n1,n2,…,nk稱(chēng)為一條由n1至nk的路徑。這條路徑的長(zhǎng)度是k-1。（6）祖先、子孫。在樹(shù)中，如果有一條路徑從結(jié)點(diǎn)M到結(jié)點(diǎn)N，那么M就稱(chēng)為N的祖先，而N稱(chēng)為M的子孫。（7）結(jié)點(diǎn)的層數(shù)。規(guī)定樹(shù)的根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于它的雙親結(jié)點(diǎn)的層數(shù)加1。（8）樹(shù)的深度。樹(shù)中所有結(jié)點(diǎn)的最大層數(shù)稱(chēng)為樹(shù)的深度。（9）樹(shù)的度。樹(shù)中各結(jié)點(diǎn)度的最大值稱(chēng)為該樹(shù)的度。2/5/20237數(shù)據(jù)結(jié)構(gòu)講義（10）滿(mǎn)二叉樹(shù)。在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的一棵二叉樹(shù)稱(chēng)作滿(mǎn)二叉樹(shù)。如圖所示，（a）圖就是一棵滿(mǎn)二叉樹(shù)，（b）圖則不是滿(mǎn)二叉樹(shù)，因?yàn)?，雖然其所有結(jié)點(diǎn)要么是含有左右子樹(shù)的分支結(jié)點(diǎn)，要么是葉子結(jié)點(diǎn)，但由于其葉子未在同一層上，故不是滿(mǎn)二叉樹(shù)。2/5/20238數(shù)據(jù)結(jié)構(gòu)講義(11)完全二叉樹(shù)。一棵深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，對(duì)樹(shù)中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)與滿(mǎn)二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置相同，則這棵二叉樹(shù)稱(chēng)為完全二叉樹(shù)。完全二叉樹(shù)的特點(diǎn)是：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹(shù)的左部。顯然，一棵滿(mǎn)二叉樹(shù)必定是一棵完全二叉樹(shù)，而完全二叉樹(shù)未必是滿(mǎn)二叉樹(shù)。如圖所示（a）為一棵完全二叉樹(shù)，（b）不是完全二叉樹(shù)。2/5/20239數(shù)據(jù)結(jié)構(gòu)講義6.1.2二叉樹(shù)的主要性質(zhì)

性質(zhì)1一棵非空二叉樹(shù)的第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。

該性質(zhì)可由數(shù)學(xué)歸納法證明。證明略。性質(zhì)2一棵深度為k的二叉樹(shù)中，最多具有2k－1個(gè)結(jié)點(diǎn)。證明設(shè)第i層的結(jié)點(diǎn)數(shù)為xi（1≤i≤k），深度為k的二叉樹(shù)的結(jié)點(diǎn)數(shù)為M，xi最多為2i-1，則有：2/5/202310數(shù)據(jù)結(jié)構(gòu)講義性質(zhì)3對(duì)于一棵非空的二叉樹(shù)，如果葉子結(jié)點(diǎn)數(shù)為n0，度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則有:

n0＝n2＋1。

證明設(shè)n為二叉樹(shù)的結(jié)點(diǎn)總數(shù)，n1為二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)，則有：

n＝n0＋n1＋n2（6-1）

在二叉樹(shù)中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有唯一的一個(gè)進(jìn)入分支。設(shè)B為二叉樹(shù)中的分支數(shù)，那么有：

B＝n－1（6-2）

這些分支是由度為1和度為2的結(jié)點(diǎn)發(fā)出的，一個(gè)度為1的結(jié)點(diǎn)發(fā)出一個(gè)分支，一個(gè)度為2的結(jié)點(diǎn)發(fā)出兩個(gè)分支，所以有：

B＝n1＋2n2（6-3）綜合（6-1）、（6-2）、（6-3）式可以得到：

n0＝n2＋12/5/202311數(shù)據(jù)結(jié)構(gòu)講義

性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度k為log2n+1。

證明根據(jù)完全二叉樹(shù)的定義和性質(zhì)2可知，當(dāng)一棵完全二叉樹(shù)的深度為k、結(jié)點(diǎn)個(gè)數(shù)為n時(shí)，有2k－1－1<n≤2k-1即2k－1≤n<2k對(duì)不等式取對(duì)數(shù)，有

k－1≤log2n<k由于k是整數(shù)，所以有

k＝log2n+1。2/5/202312數(shù)據(jù)結(jié)構(gòu)講義性質(zhì)5對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照從上至下和從左到右的順序?qū)Χ鏄?shù)中的所有結(jié)點(diǎn)從1開(kāi)始順序編號(hào)，則對(duì)于任意的序號(hào)為i的結(jié)點(diǎn)，有：⑴如果i>1，則序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為i/2(“/”表示整除)；如果i＝1，則序號(hào)為i的結(jié)點(diǎn)是根結(jié)點(diǎn)，無(wú)雙親結(jié)點(diǎn)。⑵如果2i≤n，則序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2i；如果2i>n，則序號(hào)為i的結(jié)點(diǎn)無(wú)左孩子。⑶如果2i＋1≤n，則序號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2i＋1；如果2i＋1>n，則序號(hào)為i的結(jié)點(diǎn)無(wú)右孩子。此外，若對(duì)二叉樹(shù)的根結(jié)點(diǎn)從0開(kāi)始編號(hào)，則相應(yīng)的i號(hào)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為（i－1）/2，左孩子的編號(hào)為2i＋1，右孩子的編號(hào)為2i＋2。

此性質(zhì)可采用數(shù)學(xué)歸納法證明。證明略。2/5/202313數(shù)據(jù)結(jié)構(gòu)講義6.2基本操作與存儲(chǔ)實(shí)現(xiàn)二叉樹(shù)的存儲(chǔ)二叉樹(shù)的基本操作及實(shí)現(xiàn)2/5/202314數(shù)據(jù)結(jié)構(gòu)講義6.2.1二叉樹(shù)的存儲(chǔ)1．順序存儲(chǔ)結(jié)構(gòu)所謂二叉樹(shù)的順序存儲(chǔ)，就是用一組連續(xù)的存儲(chǔ)單元存放二叉樹(shù)中的結(jié)點(diǎn)。一般是按照二叉樹(shù)結(jié)點(diǎn)從上至下、從左到右的順序存儲(chǔ)。這樣結(jié)點(diǎn)在存儲(chǔ)位置上的前驅(qū)后繼關(guān)系并不一定就是它們?cè)谶壿嬌系泥徑雨P(guān)系，然而只有通過(guò)一些方法確定某結(jié)點(diǎn)在邏輯上的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，這種存儲(chǔ)才有意義。因此，依據(jù)二叉樹(shù)的性質(zhì)，完全二叉樹(shù)和滿(mǎn)二叉樹(shù)采用順序存儲(chǔ)比較合適，樹(shù)中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系，這樣既能夠最大可能地節(jié)省存儲(chǔ)空間，又可以利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹(shù)中的位置，以及結(jié)點(diǎn)之間的關(guān)系。2/5/202315數(shù)據(jù)結(jié)構(gòu)講義下面給出一棵完全二叉樹(shù)的順序存儲(chǔ)示意。2/5/202316數(shù)據(jù)結(jié)構(gòu)講義對(duì)于一般的二叉樹(shù)，如果仍按從上至下和從左到右的順序?qū)?shù)中的結(jié)點(diǎn)順序存儲(chǔ)在一維數(shù)組中，則數(shù)組元素下標(biāo)之間的關(guān)系不能夠反映二叉樹(shù)中結(jié)點(diǎn)之間的邏輯關(guān)系，只有增添一些并不存在的空結(jié)點(diǎn)，使之成為一棵完全二叉樹(shù)的形式，然后再用一維數(shù)組順序存儲(chǔ)。2/5/202317數(shù)據(jù)結(jié)構(gòu)講義如圖給出了一棵一般二叉樹(shù)改造后的完全二叉樹(shù)形態(tài)和其順序存儲(chǔ)狀態(tài)示意圖。顯然，這種存儲(chǔ)對(duì)于需增加許多空結(jié)點(diǎn)才能將一棵二叉樹(shù)改造成為一棵完全二叉樹(shù)的存儲(chǔ)時(shí)，會(huì)造成空間的大量浪費(fèi)，不宜用順序存儲(chǔ)結(jié)構(gòu)。2/5/202318數(shù)據(jù)結(jié)構(gòu)講義最壞的情況是右單支樹(shù)，一棵深度為k的右單支樹(shù)，只有k個(gè)結(jié)點(diǎn)，卻需分配2k－1個(gè)存儲(chǔ)單元。2/5/202319數(shù)據(jù)結(jié)構(gòu)講義2．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（1）二叉鏈表存儲(chǔ)鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，分別用來(lái)給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。結(jié)點(diǎn)的存儲(chǔ)的結(jié)構(gòu)為：其中，data域存放某結(jié)點(diǎn)的數(shù)據(jù)信息；lchild與rchild分別存放指向左孩子和右孩子的指針，當(dāng)左孩子或右孩子不存在時(shí)，相應(yīng)指針域值為空（用符號(hào)∧或NULL表示）。2/5/202320數(shù)據(jù)結(jié)構(gòu)講義下圖(a)給出一棵二叉樹(shù)的二叉鏈表示。二叉鏈表也可以帶頭結(jié)點(diǎn)的方式存放，如圖(b)所示。2/5/202321數(shù)據(jù)結(jié)構(gòu)講義（2）三叉鏈表存儲(chǔ)每個(gè)結(jié)點(diǎn)由四個(gè)域組成，具體結(jié)構(gòu)為：其中，data、lchild以及rchild三個(gè)域的意義同二叉鏈表結(jié)構(gòu)；parent域?yàn)橹赶蛟摻Y(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。這種存儲(chǔ)結(jié)構(gòu)既便于查找孩子結(jié)點(diǎn)，又便于查找雙親結(jié)點(diǎn)；但是，相對(duì)于二叉鏈表存儲(chǔ)結(jié)構(gòu)而言，它增加了空間開(kāi)銷(xiāo)。2/5/202322數(shù)據(jù)結(jié)構(gòu)講義下圖給出一棵二叉樹(shù)的三叉鏈表示。2/5/202323數(shù)據(jù)結(jié)構(gòu)講義盡管在二叉鏈表中無(wú)法由結(jié)點(diǎn)直接找到其雙親，但由于二叉鏈表結(jié)構(gòu)靈活，操作方便，對(duì)于一般情況的二叉樹(shù)，甚至比順序存儲(chǔ)結(jié)構(gòu)還節(jié)省空間。因此，二叉鏈表是最常用的二叉樹(shù)存儲(chǔ)方式。本書(shū)后面所涉及到的二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不加特別說(shuō)明的都是指二叉鏈表結(jié)構(gòu)。二叉樹(shù)的二叉鏈表存儲(chǔ)表示可描述為：

typedefstructBiTNode{elemtypedata;structBiTNode*lchild;*rchild;/*左右孩子指針*/}BiTNode,*BiTree;即將BiTree定義為指向二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)的指針類(lèi)型。2/5/202324數(shù)據(jù)結(jié)構(gòu)講義6.2.2二叉樹(shù)的基本操作及實(shí)現(xiàn)二叉樹(shù)的基本操作通常有以下幾種：（1）Initiate（bt）建立一棵空二叉樹(shù)。（2）Create（x，lbt，rbt）生成一棵以x為根結(jié)點(diǎn)的數(shù)據(jù)域信息，以二叉樹(shù)lbt和rbt為左子樹(shù)和右子樹(shù)的二叉樹(shù)。（3）InsertL（bt，x，parent）將數(shù)據(jù)域信息為x的結(jié)點(diǎn)插入到二叉樹(shù)bt中作為結(jié)點(diǎn)parent的左孩子結(jié)點(diǎn)。如果結(jié)點(diǎn)parent原來(lái)有左孩子結(jié)點(diǎn)，則將結(jié)點(diǎn)parent原來(lái)的左孩子結(jié)點(diǎn)作為結(jié)點(diǎn)x的左孩子結(jié)點(diǎn)。2/5/202325數(shù)據(jù)結(jié)構(gòu)講義（4）InsertR（bt，x，parent）將數(shù)據(jù)域信息為x的結(jié)點(diǎn)插入到二叉樹(shù)bt中作為結(jié)點(diǎn)parent的右孩子結(jié)點(diǎn)。如果結(jié)點(diǎn)parent原來(lái)有右孩子結(jié)點(diǎn)，則將結(jié)點(diǎn)parent原來(lái)的右孩子結(jié)點(diǎn)作為結(jié)點(diǎn)x的右孩子結(jié)點(diǎn)。（5）DeleteL（bt，parent）在二叉樹(shù)bt中刪除結(jié)點(diǎn)parent的左子樹(shù)。（6）DeleteR（bt，parent）在二叉樹(shù)bt中刪除結(jié)點(diǎn)parent的右子樹(shù)。（7）Search（bt，x）在二叉樹(shù)bt中查找數(shù)據(jù)元素x。（8）Traverse（bt）按某種方式遍歷二叉樹(shù)bt的全部結(jié)點(diǎn)。2/5/202326數(shù)據(jù)結(jié)構(gòu)講義算法的實(shí)現(xiàn)依賴(lài)于具體的存儲(chǔ)結(jié)構(gòu)，當(dāng)二叉樹(shù)采用不同的存儲(chǔ)結(jié)構(gòu)時(shí)，上述各種操作的實(shí)現(xiàn)算法是不同的。下面討論基于二叉鏈表存儲(chǔ)結(jié)構(gòu)的上述操作的實(shí)現(xiàn)算法。2/5/202327數(shù)據(jù)結(jié)構(gòu)講義（1）Initiate（bt）初始建立二叉樹(shù)bt，并使bt指向頭結(jié)點(diǎn)。在二叉樹(shù)根結(jié)點(diǎn)前建立頭結(jié)點(diǎn)，就如同在單鏈表前建立的頭結(jié)點(diǎn)，可以方便后邊的一些操作實(shí)現(xiàn)。

intInitiate(BiTree*bt)/*初始化建立二叉樹(shù)*bt的頭結(jié)點(diǎn)*/{if((*bt=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)

return0;*bt->lchild=NULL;*bt->rchild=NULL;return1;}2/5/202328數(shù)據(jù)結(jié)構(gòu)講義（2）Create（x，lbt，rbt）建立一棵以x為根結(jié)點(diǎn)的數(shù)據(jù)域信息，以二叉樹(shù)lbt和rbt為左右子樹(shù)的二叉樹(shù)。建立成功時(shí)返回所建二叉樹(shù)結(jié)點(diǎn)的指針；建立失敗時(shí)返回空指針。

BiTreeCreate（elemtypex，BiTreelbt，BiTreerbt）

/*生成一棵以x為根結(jié)點(diǎn)的數(shù)據(jù)域值以lbt和rbt為左右子樹(shù)的二叉樹(shù)*/{BiTreep;if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)

returnNULL;p->data=x;p->lchild=lbt;p->rchild=rbt;returnp;}2/5/202329數(shù)據(jù)結(jié)構(gòu)講義（3）InsertL（bt，x，parent）BiTreeInsertL（BiTreebt，elemtypex，BiTreeparent）

/*在二叉樹(shù)bt的結(jié)點(diǎn)parent的左子樹(shù)插入結(jié)點(diǎn)數(shù)據(jù)元素x*/

{BiTreep;if(parent==NULL){

printf(“\n插入出錯(cuò)”)；

returnNULL;}

if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)returnNULL;p->data=x;p->lchild=NULL;p->rchild=NULL;if(parent->lchild==NULL)parent->lchild=p;else{p->lchild=parent->lchild;

parent->lchild=p;}returnbt;}2/5/202330數(shù)據(jù)結(jié)構(gòu)講義（4）DeleteL（bt，parent）在二叉樹(shù)bt中刪除結(jié)點(diǎn)parent的左子樹(shù)。當(dāng)parent或parent的左孩子結(jié)點(diǎn)為空時(shí)刪除失敗。刪除成功時(shí)返回根結(jié)點(diǎn)指針；刪除失敗時(shí)返回空指針。

BiTreeDeleteL（BiTreebt，BiTreeparent）/*在二叉樹(shù)bt中刪除結(jié)點(diǎn)parent的左子樹(shù)*/{BiTreep;if(parent==NULL||parent->lchild==NULL){printf(“\n刪除出錯(cuò)”)；

returnNULL;}p=parent->lchild;parent->lchild=NULL;free(p);/*當(dāng)p為非葉子結(jié)點(diǎn)時(shí)，這樣刪除僅釋放了所刪子樹(shù)根結(jié)點(diǎn)的空間，若要?jiǎng)h除子樹(shù)分支中的結(jié)點(diǎn)，需用后面介紹的遍歷操作來(lái)實(shí)現(xiàn)。*/

returnbt;}2/5/202331數(shù)據(jù)結(jié)構(gòu)講義6.3二叉樹(shù)的遍歷二叉樹(shù)的遍歷方法及遞歸實(shí)現(xiàn)二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn)由遍歷序列恢復(fù)二叉樹(shù)不用棧的二叉樹(shù)遍歷的非遞歸方法層次遍歷2/5/202332數(shù)據(jù)結(jié)構(gòu)講義6.3.1二叉樹(shù)的遍歷方法及遞歸實(shí)現(xiàn)

二叉樹(shù)的遍歷是指按照某種順序訪(fǎng)問(wèn)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪(fǎng)問(wèn)一次且僅被訪(fǎng)問(wèn)一次。遍歷是二叉樹(shù)中經(jīng)常要用到的一種操作。因?yàn)樵趯?shí)際應(yīng)用問(wèn)題中，常常需要按一定順序?qū)Χ鏄?shù)中的每個(gè)結(jié)點(diǎn)逐個(gè)進(jìn)行訪(fǎng)問(wèn)，查找具有某一特點(diǎn)的結(jié)點(diǎn)，然后對(duì)這些滿(mǎn)足條件的結(jié)點(diǎn)進(jìn)行處理。通過(guò)一次完整的遍歷，可使二叉樹(shù)中結(jié)點(diǎn)信息由非線(xiàn)性排列變?yōu)槟撤N意義上的線(xiàn)性序列。也就是說(shuō)，遍歷操作使非線(xiàn)性結(jié)構(gòu)線(xiàn)性化。2/5/202333數(shù)據(jù)結(jié)構(gòu)講義由二叉樹(shù)的定義可知，一棵由根結(jié)點(diǎn)、根結(jié)點(diǎn)的左子樹(shù)和根結(jié)點(diǎn)的右子樹(shù)三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個(gè)二叉樹(shù)。若以D、L、R分別表示訪(fǎng)問(wèn)根結(jié)點(diǎn)、遍歷根結(jié)點(diǎn)的左子樹(shù)、遍歷根結(jié)點(diǎn)的右子樹(shù)，則二叉樹(shù)的遍歷方式有六種：DLR、LDR、LRD、DRL、RDL和RLD。

如果限定先左后右，則只有前三種方式，即

DLR（稱(chēng)為先序遍歷）

LDR（稱(chēng)為中序遍歷）

LRD（稱(chēng)為后序遍歷）2/5/202334數(shù)據(jù)結(jié)構(gòu)講義1．先序遍歷（DLR）

先序遍歷的遞歸過(guò)程為：若二叉樹(shù)為空，遍歷結(jié)束。否則，⑴訪(fǎng)問(wèn)根結(jié)點(diǎn)；⑵先序遍歷根結(jié)點(diǎn)的左子樹(shù)；⑶先序遍歷根結(jié)點(diǎn)的右子樹(shù)。先序遍歷二叉樹(shù)的遞歸算法如下：voidPreOrder（BiTreebt）/*先序遍歷二叉樹(shù)bt*/{if(bt==NULL)return;/*遞歸調(diào)用的結(jié)束條件*/

Visite（bt->data）;/*訪(fǎng)問(wèn)結(jié)點(diǎn)的數(shù)據(jù)域*/

PreOrder（bt->lchild）;/*先序遞歸遍歷bt的左子樹(shù)*/

PreOrder（bt->rchild）;/*先序遞歸遍歷bt的右子樹(shù)*/

}2/5/202335數(shù)據(jù)結(jié)構(gòu)講義對(duì)于上圖所示的二叉樹(shù)，按先序遍歷所得到的結(jié)點(diǎn)序列為：

ABDGCEF2/5/202336數(shù)據(jù)結(jié)構(gòu)講義2．中序遍歷（LDR）

中序遍歷的遞歸過(guò)程為：若二叉樹(shù)為空，遍歷結(jié)束。否則，⑴中序遍歷根結(jié)點(diǎn)的左子樹(shù)；⑵訪(fǎng)問(wèn)根結(jié)點(diǎn)；⑶中序遍歷根結(jié)點(diǎn)的右子樹(shù)。中序遍歷二叉樹(shù)的遞歸算法如下：voidInOrder（BiTreebt）/*中序遍歷二叉樹(shù)bt*/{if(bt==NULL)return;/*遞歸調(diào)用的結(jié)束條件*/

InOrder（bt->lchild）;/*中序遞歸遍歷bt的左子樹(shù)*/

Visite（bt->data）;/*訪(fǎng)問(wèn)結(jié)點(diǎn)的數(shù)據(jù)域*/

InOrder（bt->rchild）;/*中序遞歸遍歷bt的右子樹(shù)*/

}2/5/202337數(shù)據(jù)結(jié)構(gòu)講義對(duì)于上圖所示的二叉樹(shù)，按中序遍歷所得到的結(jié)點(diǎn)序列為：

DGBAECF2/5/202338數(shù)據(jù)結(jié)構(gòu)講義3．后序遍歷（LRD）

后序遍歷的遞歸過(guò)程為：若二叉樹(shù)為空，遍歷結(jié)束。否則，⑴后序遍歷根結(jié)點(diǎn)的左子樹(shù)；⑵后序遍歷根結(jié)點(diǎn)的右子樹(shù)。⑶訪(fǎng)問(wèn)根結(jié)點(diǎn)；后序遍歷二叉樹(shù)的遞歸算法如下：voidPostOrder（BiTreebt）/*后序遍歷二叉樹(shù)bt*/{if(bt==NULL)return;/*遞歸調(diào)用的結(jié)束條件*/

PostOrder（bt->lchild）;/*后序遞歸遍歷bt的左子樹(shù)*/

PostOrder（bt->rchild）;/*后序遞歸遍歷bt的右子樹(shù)*/

Visite（bt->data）;/*訪(fǎng)問(wèn)結(jié)點(diǎn)的數(shù)據(jù)域*/}2/5/202339數(shù)據(jù)結(jié)構(gòu)講義對(duì)于上圖所示的二叉樹(shù)，按后序遍歷所得到的結(jié)點(diǎn)序列為：

GDBEFCA2/5/202340數(shù)據(jù)結(jié)構(gòu)講義6.3.2二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn)前面給出的二叉樹(shù)先序、中序和后序三種遍歷算法都是遞歸算法。當(dāng)給出二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以后，用具有遞歸功能的程序設(shè)計(jì)語(yǔ)言很方便就能實(shí)現(xiàn)上述算法。然而，并非所有程序設(shè)計(jì)語(yǔ)言都允許遞歸；另一方面，遞歸程序雖然簡(jiǎn)潔，但可讀性一般不好，執(zhí)行效率也不高。因此，就存在如何把一個(gè)遞歸算法轉(zhuǎn)化為非遞歸算法的問(wèn)題。解決這個(gè)問(wèn)題的方法可以通過(guò)對(duì)三種遍歷方法的實(shí)質(zhì)過(guò)程的分析得到。2/5/202341數(shù)據(jù)結(jié)構(gòu)講義如前圖所示的二叉樹(shù)，對(duì)其進(jìn)行先序、中序和后序遍歷都是從根結(jié)點(diǎn)A開(kāi)始的，且在遍歷過(guò)程中經(jīng)過(guò)結(jié)點(diǎn)的路線(xiàn)也是一樣的，只是訪(fǎng)問(wèn)的時(shí)機(jī)不同而已。下圖中所示的從根結(jié)點(diǎn)左外側(cè)開(kāi)始，由根結(jié)點(diǎn)右外側(cè)結(jié)束的曲線(xiàn)，為遍歷前圖的路線(xiàn)。沿著該路線(xiàn)按△標(biāo)記的結(jié)點(diǎn)讀得的序列為先序序列，按*標(biāo)記讀得的序列為中序序列，按⊕標(biāo)記讀得的序列為后序序列。2/5/202342數(shù)據(jù)結(jié)構(gòu)講義然而，這一路線(xiàn)正是從根結(jié)點(diǎn)開(kāi)始沿左子樹(shù)深入下去，當(dāng)深入到最左端，無(wú)法再深入下去時(shí)，則返回，再逐一進(jìn)入剛才深入時(shí)遇到結(jié)點(diǎn)的右子樹(shù)，再進(jìn)行如此的深入和返回，直到最后從根結(jié)點(diǎn)的右子樹(shù)返回到根結(jié)點(diǎn)為止。先序遍歷是在深入時(shí)遇到結(jié)點(diǎn)就訪(fǎng)問(wèn)，中序遍歷是在從左子樹(shù)返回時(shí)遇到結(jié)點(diǎn)訪(fǎng)問(wèn)，后序遍歷是在從右子樹(shù)返回時(shí)遇到結(jié)點(diǎn)訪(fǎng)問(wèn)。在這一過(guò)程中，返回結(jié)點(diǎn)的順序與深入結(jié)點(diǎn)的順序相反，即后深入先返回，可以用棧來(lái)幫助實(shí)現(xiàn)這一遍歷路線(xiàn)。其過(guò)程如下：在沿左子樹(shù)深入時(shí)，深入一個(gè)結(jié)點(diǎn)入棧一個(gè)結(jié)點(diǎn)，若為先序遍歷，則在入棧之前訪(fǎng)問(wèn)之；當(dāng)沿左分支深入不下去時(shí)，則返回，即從堆棧中彈出前面壓入的結(jié)點(diǎn)，若為中序遍歷，則此時(shí)訪(fǎng)問(wèn)該結(jié)點(diǎn)，然后從該結(jié)點(diǎn)的右子樹(shù)繼續(xù)深入；若為后序遍歷，則將此結(jié)點(diǎn)再次入棧，然后從該結(jié)點(diǎn)的右子樹(shù)繼續(xù)深入，與前面類(lèi)同，仍為深入一個(gè)結(jié)點(diǎn)入棧一個(gè)結(jié)點(diǎn)，深入不下去再返回，直到第二次從棧里彈出該結(jié)點(diǎn)，即從右子樹(shù)返回時(shí)，才訪(fǎng)問(wèn)之。2/5/202343數(shù)據(jù)結(jié)構(gòu)講義（1）先序遍歷的非遞歸實(shí)現(xiàn)在下面算法中，二叉樹(shù)以二叉鏈表存放，一維數(shù)組stack[MAXNODE]用以實(shí)現(xiàn)棧，變量top用來(lái)表示當(dāng)前棧頂?shù)奈恢?。voidNRPreOrder（BiTreebt）

/*非遞歸先序遍歷二叉樹(shù)*/{BiTreestack[MAXNODE],p;inttop;if(bt==NULL)return;top=0;p=bt;

2/5/202344數(shù)據(jù)結(jié)構(gòu)講義

while(!(p==NULL&&top==0)){while(p!=NULL){Visite(p->data);/*訪(fǎng)問(wèn)結(jié)點(diǎn)的數(shù)據(jù)域*/

if(top<MAXNODE-1)/*將當(dāng)前指針p壓棧*/{stack[top]=p;top++;}else{printf(“棧溢出”)；return；}p=p->lchild；/*指針指向p的左孩子*/}

if(top<=0)return;/*?？諘r(shí)結(jié)束*/

else{top--;p=stack[top];/*從棧中彈出棧頂元素*/

p=p->rchild;/*指針指向p的右孩子結(jié)點(diǎn)*/}}}2/5/202345數(shù)據(jù)結(jié)構(gòu)講義對(duì)于下圖所示的二叉樹(shù)，用該算法進(jìn)行遍歷過(guò)程中，棧stack和當(dāng)前指針p的變化情況以及樹(shù)中各結(jié)點(diǎn)的訪(fǎng)問(wèn)次序如下表所示。2/5/202346數(shù)據(jù)結(jié)構(gòu)講義（2）中序遍歷的非遞歸實(shí)現(xiàn)中序遍歷的非遞歸算法的實(shí)現(xiàn)，只需將先序遍歷的非遞歸算法中的Visite(p->data)移到p=stack[top]和p=p->rchild之間即可。2/5/202347數(shù)據(jù)結(jié)構(gòu)講義（3）后序遍歷的非遞歸實(shí)現(xiàn)由前面的討論可知，后序遍歷與先序遍歷和中序遍歷不同，在后序遍歷過(guò)程中，結(jié)點(diǎn)在第一次出棧后，還需再次入棧，也就是說(shuō)，結(jié)點(diǎn)要入兩次棧，出兩次棧，而訪(fǎng)問(wèn)結(jié)點(diǎn)是在第二次出棧時(shí)訪(fǎng)問(wèn)。因此，為了區(qū)別同一個(gè)結(jié)點(diǎn)指針的兩次出棧，設(shè)置一標(biāo)志flag，令：

flag＝當(dāng)結(jié)點(diǎn)指針進(jìn)、出棧時(shí)，其標(biāo)志flag也同時(shí)進(jìn)、出棧。因此，可將棧中元素的數(shù)據(jù)類(lèi)型定義為指針和標(biāo)志flag合并的結(jié)構(gòu)體類(lèi)型。定義如下：

typedefstruct{BiTreelink;intflag;

}stacktype;2/5/202348數(shù)據(jù)結(jié)構(gòu)講義后序遍歷二叉樹(shù)的非遞歸算法如下。在算法中，一維數(shù)組stack[MAXNODE]用于實(shí)現(xiàn)棧的結(jié)構(gòu)，指針變量p指向當(dāng)前要處理的結(jié)點(diǎn)，整型變量top用來(lái)表示當(dāng)前棧頂?shù)奈恢?，整型變量sign為結(jié)點(diǎn)p的標(biāo)志量。voidNRPostOrder(BiTreebt)/*非遞歸后序遍歷二叉樹(shù)bt*/{stacktypestack[MAXNODE];BiTreep;inttop,sign;if(bt==NULL)return;top=-1/*棧頂位置初始化*/

p=bt;2/5/202349數(shù)據(jù)結(jié)構(gòu)講義while(!(p==NULL&&top==-1)){if(p!=NULL)

/*結(jié)點(diǎn)第一次進(jìn)棧*/{top++;stack[top].link=p;stack[top].flag=1;p=p->lchild;/*找該結(jié)點(diǎn)的左孩子*/}

else{p=stack[top].link;sign=stack[top].flag;top--;if(sign==1)

/*結(jié)點(diǎn)第二次進(jìn)棧*/{top++;stack[top].link=p;stack[top].flag=2;/*標(biāo)記第二次出棧*/

p=p->rchild;}else{Visite(p->data);/*訪(fǎng)問(wèn)該結(jié)點(diǎn)數(shù)據(jù)域值*/

p=NULL;}}}}2/5/202350數(shù)據(jù)結(jié)構(gòu)講義6.3.3由遍歷序列恢復(fù)二叉樹(shù)從前面討論的二叉樹(shù)的遍歷知道，任意一棵二叉樹(shù)結(jié)點(diǎn)的先序序列和中序序列都是唯一的。反過(guò)來(lái)，若已知結(jié)點(diǎn)的先序序列和中序序列，能否確定這棵二叉樹(shù)呢？這樣確定的二叉樹(shù)是否是唯一的呢？2/5/202351數(shù)據(jù)結(jié)構(gòu)講義根據(jù)定義，二叉樹(shù)的先序遍歷是先訪(fǎng)問(wèn)根結(jié)點(diǎn)，其次再按先序遍歷方式遍歷根結(jié)點(diǎn)的左子樹(shù)，最后按先序遍歷方式遍歷根結(jié)點(diǎn)的右子樹(shù)。這就是說(shuō)，在先序序列中，第一個(gè)結(jié)點(diǎn)一定是二叉樹(shù)的根結(jié)點(diǎn)。另一方面，中序遍歷是先遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)，最后再遍歷右子樹(shù)。這樣，根結(jié)點(diǎn)在中序序列中必然將中序序列分割成兩個(gè)子序列，前一個(gè)子序列是根結(jié)點(diǎn)的左子樹(shù)的中序序列，而后一個(gè)子序列是根結(jié)點(diǎn)的右子樹(shù)的中序序列。根據(jù)這兩個(gè)子序列，在先序序列中找到對(duì)應(yīng)的左子序列和右子序列。在先序序列中，左子序列的第一個(gè)結(jié)點(diǎn)是左子樹(shù)的根結(jié)點(diǎn)，右子序列的第一個(gè)結(jié)點(diǎn)是右子樹(shù)的根結(jié)點(diǎn)。這樣，就確定了二叉樹(shù)的三個(gè)結(jié)點(diǎn)。同時(shí)，左子樹(shù)和右子樹(shù)的根結(jié)點(diǎn)又可以分別把左子序列和右子序列劃分成兩個(gè)子序列，如此遞歸下去，當(dāng)取盡先序序列中的結(jié)點(diǎn)時(shí)，便可以得到一棵二叉樹(shù)。2/5/202352數(shù)據(jù)結(jié)構(gòu)講義同樣的道理，由二叉樹(shù)的后序序列和中序序列也可唯一地確定一棵二叉樹(shù)。因?yàn)?，依?jù)后序遍歷和中序遍歷的定義，后序序列的最后一個(gè)結(jié)點(diǎn)，就如同先序序列的第一個(gè)結(jié)點(diǎn)一樣，可將中序序列分成兩個(gè)子序列，分別為這個(gè)結(jié)點(diǎn)的左子樹(shù)的中序序列和右子樹(shù)的中序序列，再拿出后序序列的倒數(shù)第二個(gè)結(jié)點(diǎn)，并繼續(xù)分割中序序列，如此遞歸下去，當(dāng)?shù)怪”M后序序列中的結(jié)點(diǎn)時(shí)，便可以得到一棵二叉樹(shù)。2/5/202353數(shù)據(jù)結(jié)構(gòu)講義下面通過(guò)一個(gè)例子，來(lái)給出由二叉樹(shù)的先序序列和中序序列構(gòu)造唯一的一棵二叉樹(shù)的實(shí)現(xiàn)算法。已知一棵二叉樹(shù)的先序序列與中序序列分別為：

ABCDEFGHI

BCAEDGHFI試恢復(fù)該二叉樹(shù)。2/5/202354數(shù)據(jù)結(jié)構(gòu)講義上述過(guò)程是一個(gè)遞歸過(guò)程，其遞歸算法的思想是：先根據(jù)先序序列的第一個(gè)元素建立根結(jié)點(diǎn)；然后在中序序列中找到該元素，確定根結(jié)點(diǎn)的左、右子樹(shù)的中序序列；再在先序序列中確定左、右子樹(shù)的先序序列；最后由左子樹(shù)的先序序列與中序序列建立左子樹(shù)，由右子樹(shù)的先序序列與中序序列建立右子樹(shù)。2/5/202355數(shù)據(jù)結(jié)構(gòu)講義下面給出用C語(yǔ)言描述的該算法。假設(shè)二叉樹(shù)的先序序列和中序序列分別存放在一維數(shù)組preod[]與inod[]中，并假設(shè)二叉樹(shù)各結(jié)點(diǎn)的數(shù)據(jù)值均不相同。voidReBiTree（charpreod[],charinod[],intn,BiTreeroot）/*n為二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)，root為二叉樹(shù)根結(jié)點(diǎn)的存儲(chǔ)地址*/{if(n≤0)root=NULL;elsePreInOd(preod,inod,1,n,1,n,&root);}2/5/202356數(shù)據(jù)結(jié)構(gòu)講義voidPreInOd（charpreod[],charinod[],inti,j,k,h,BiTree*t）{*t=(BiTNode*)malloc(sizeof(BiTNode));*t->data=preod[i];m=k;while(inod[m]!=preod[i])

m++;if(m==k)*t->lchild=NULLelsePreInOd(preod,inod,i+1,i+m-k,k,m-1,&t->lchild);if(m==h)*t->rchild=NULLelsePreInOd(preod,inod,i+m-k+1,j,m+1,h,&t->rchild);}2/5/202357數(shù)據(jù)結(jié)構(gòu)講義6.3.4不用棧的二叉樹(shù)遍歷的非遞歸方法前面介紹的二叉樹(shù)的遍歷算法可分為兩類(lèi)，一類(lèi)是依據(jù)二叉樹(shù)結(jié)構(gòu)的遞歸性，采用遞歸調(diào)用的方式來(lái)實(shí)現(xiàn)；另一類(lèi)則是通過(guò)堆?；蜿?duì)列來(lái)輔助實(shí)現(xiàn)。采用這兩類(lèi)方法對(duì)二叉樹(shù)進(jìn)行遍歷時(shí)，遞歸調(diào)用和棧或隊(duì)列的使用都帶來(lái)額外空間增加，遞歸調(diào)用的深度和棧的大小是動(dòng)態(tài)變化的，都與二叉樹(shù)的高度有關(guān)。因此，在最壞的情況下，即二叉樹(shù)退化為單支樹(shù)的情況下，遞歸的深度或棧需要的存儲(chǔ)空間等于二叉樹(shù)中的結(jié)點(diǎn)數(shù)。2/5/202358數(shù)據(jù)結(jié)構(gòu)講義還有一類(lèi)二叉樹(shù)的遍歷算法，就是不用棧也不用遞歸來(lái)實(shí)現(xiàn)。常用的不用棧的二叉樹(shù)遍歷的非遞歸方法有以下三種：⑴對(duì)二叉樹(shù)采用三叉鏈表存放，即在二叉樹(shù)的每個(gè)結(jié)點(diǎn)中增加一個(gè)雙親域parent，這樣，在遍歷深入到不能再深入時(shí)，可沿著走過(guò)的路徑回退到任何一棵子樹(shù)的根結(jié)點(diǎn)，并再向另一方向走。⑵采用逆轉(zhuǎn)鏈的方法，即在遍歷深入時(shí)，每深入一層，就將其再深入的孩子結(jié)點(diǎn)的地址取出，并將其雙親結(jié)點(diǎn)的地址存入。當(dāng)深入不下去而需返回時(shí)，可逐級(jí)取出雙親結(jié)點(diǎn)的地址，沿原路返回。⑶在線(xiàn)索二叉樹(shù)上的遍歷，即利用具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中的葉子結(jié)點(diǎn)和一度結(jié)點(diǎn)的n＋1個(gè)空指針域，來(lái)存放線(xiàn)索，然后在這種具有線(xiàn)索的二叉樹(shù)上遍歷時(shí)，就可不需要棧，也不需要遞歸了。2/5/202359數(shù)據(jù)結(jié)構(gòu)講義6.3.5層次遍歷所謂二叉樹(shù)的層次遍歷，是指從二叉樹(shù)的第一層（根結(jié)點(diǎn)）開(kāi)始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪(fǎng)問(wèn)。對(duì)于下圖所示的二叉樹(shù)，按層次遍歷所得到的結(jié)果序列為：

ABCDEFG2/5/202360數(shù)據(jù)結(jié)構(gòu)講義由層次遍歷的定義可以推知，在進(jìn)行層次遍歷時(shí)，對(duì)一層結(jié)點(diǎn)訪(fǎng)問(wèn)完后，再按照它們的訪(fǎng)問(wèn)次序?qū)Ω鱾€(gè)結(jié)點(diǎn)的左孩子和右孩子順序訪(fǎng)問(wèn)，這樣一層一層進(jìn)行，先遇到的結(jié)點(diǎn)先訪(fǎng)問(wèn)，這與隊(duì)列的操作原則比較吻合。因此，在進(jìn)行層次遍歷時(shí)，可設(shè)置一個(gè)隊(duì)列結(jié)構(gòu)，遍歷從二叉樹(shù)的根結(jié)點(diǎn)開(kāi)始，首先將根結(jié)點(diǎn)指針入隊(duì)列，然后從對(duì)頭取出一個(gè)元素，每取一個(gè)元素，執(zhí)行下面兩個(gè)操作：⑴訪(fǎng)問(wèn)該元素所指結(jié)點(diǎn)；⑵若該元素所指結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)非空，則將該元素所指結(jié)點(diǎn)的左孩子指針和右孩子指針順序入隊(duì)。此過(guò)程不斷進(jìn)行，當(dāng)隊(duì)列為空時(shí)，二叉樹(shù)的層次遍歷結(jié)束。2/5/202361數(shù)據(jù)結(jié)構(gòu)講義在下面的層次遍歷算法中，二叉樹(shù)以二叉鏈表存放，一維數(shù)組Queue[MAXNODE]用以實(shí)現(xiàn)隊(duì)列，變量front和rear分別表示當(dāng)前對(duì)首元素和隊(duì)尾元素在數(shù)組中的位置。

voidLevelOrder（BiTreebt）/*層次遍歷二叉樹(shù)bt*/{BiTreeQueue[MAXNODE];intfront,rear;if(bt==NULL)return;front=-1;rear=0;queue[rear]=bt;2/5/202362數(shù)據(jù)結(jié)構(gòu)講義

while(front!=rear){front++;Visite(queue[front]->data);/*訪(fǎng)問(wèn)隊(duì)首結(jié)點(diǎn)的數(shù)據(jù)域*/

if(queue[front]->lchild!=NULL)

/*將隊(duì)首結(jié)點(diǎn)的左孩子結(jié)點(diǎn)入隊(duì)列*/{rear++;queue[rear]=queue[front]->lchild;}if(queue[front]->rchild!=NULL)

/*將隊(duì)首結(jié)點(diǎn)的右孩子結(jié)點(diǎn)入隊(duì)列*/{rear++;queue[rear]=queue[front]->rchild;}}}2/5/202363數(shù)據(jù)結(jié)構(gòu)講義6.4線(xiàn)索二叉樹(shù)線(xiàn)索二叉樹(shù)的定義及結(jié)構(gòu)線(xiàn)索二叉樹(shù)的基本操作實(shí)現(xiàn)2/5/202364數(shù)據(jù)結(jié)構(gòu)講義6.4.1線(xiàn)索二叉樹(shù)的定義及結(jié)構(gòu)1．線(xiàn)索二叉樹(shù)的定義按照某種遍歷方式對(duì)二叉樹(shù)進(jìn)行遍歷，可以把二叉樹(shù)中所有結(jié)點(diǎn)排列為一個(gè)線(xiàn)性序列。在該序列中，除第一個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)；除最后一個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接后繼結(jié)點(diǎn)。但是，二叉樹(shù)中每個(gè)結(jié)點(diǎn)在這個(gè)序列中的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)是什么，二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)中并沒(méi)有反映出來(lái)，只能在對(duì)二叉樹(shù)遍歷的動(dòng)態(tài)過(guò)程中得到這些信息。為了保留結(jié)點(diǎn)在某種遍歷序列中直接前驅(qū)和直接后繼的位置信息，利用二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)中的那些空指針域來(lái)指示。這些指向直接前驅(qū)結(jié)點(diǎn)和指向直接后繼結(jié)點(diǎn)的指針被稱(chēng)為線(xiàn)索（thread），加了線(xiàn)索的二叉樹(shù)稱(chēng)為線(xiàn)索二叉樹(shù)。線(xiàn)索二叉樹(shù)將為二叉樹(shù)的遍歷提供許多遍歷。2/5/202365數(shù)據(jù)結(jié)構(gòu)講義2．線(xiàn)索二叉樹(shù)的結(jié)構(gòu)由于序列可由不同的遍歷方法得到，因此，線(xiàn)索樹(shù)有先序線(xiàn)索二叉樹(shù)、中序線(xiàn)索二叉樹(shù)和后序線(xiàn)索二叉樹(shù)三種。把二叉樹(shù)改造成線(xiàn)索二叉樹(shù)的過(guò)程稱(chēng)為線(xiàn)索化。對(duì)前圖所示的二叉樹(shù)進(jìn)行線(xiàn)索化，得到先序線(xiàn)索二叉樹(shù)、中序線(xiàn)索二叉樹(shù)和后序線(xiàn)索二叉樹(shù)分別如圖(a)、(b)、(c)所示。圖中實(shí)線(xiàn)表示指針，虛線(xiàn)表示線(xiàn)索。2/5/202366數(shù)據(jù)結(jié)構(gòu)講義那么，下面的問(wèn)題是在存儲(chǔ)中，如何區(qū)別某結(jié)點(diǎn)的指針域內(nèi)存放的是指針還是線(xiàn)索？通?？梢圆捎孟旅鎯煞N方法來(lái)實(shí)現(xiàn)。⑴為每個(gè)結(jié)點(diǎn)增設(shè)兩個(gè)標(biāo)志位域ltag和rtag，令：

ltag＝

rtag＝

每個(gè)標(biāo)志位令其只占一個(gè)bit，這樣就只需增加很少的存儲(chǔ)空間。這樣結(jié)點(diǎn)的結(jié)構(gòu)為：⑵不改變結(jié)點(diǎn)結(jié)構(gòu)，僅在作為線(xiàn)索的地址前加一個(gè)負(fù)號(hào)，即負(fù)的地址表示線(xiàn)索，正的地址表示指針。2/5/202367數(shù)據(jù)結(jié)構(gòu)講義6.4.2線(xiàn)索二叉樹(shù)的基本操作實(shí)現(xiàn)在線(xiàn)索二叉樹(shù)中，結(jié)點(diǎn)的結(jié)構(gòu)可以定義為如下形式：

typedefcharelemtype;

typedefstructBiThrNode{elemtypedata;structBiThrNode*lchild;structBiThrNode*rchild;unsignedltag;unsignedrtag;}BiThrNodeType,*BiThrTree;2/5/202368數(shù)據(jù)結(jié)構(gòu)講義1．建立一棵中序線(xiàn)索二叉樹(shù)建立線(xiàn)索二叉樹(shù)，或者說(shuō)對(duì)二叉樹(shù)線(xiàn)索化，實(shí)質(zhì)上就是遍歷一棵二叉樹(shù)。在遍歷過(guò)程中，訪(fǎng)問(wèn)結(jié)點(diǎn)的操作是檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空，如果為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線(xiàn)索。為實(shí)現(xiàn)這一過(guò)程，設(shè)指針pre始終指向剛剛訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)，即若指針p指向當(dāng)前結(jié)點(diǎn)，則pre指向它的前驅(qū)，以便增設(shè)線(xiàn)索。另外，在對(duì)一棵二叉樹(shù)加線(xiàn)索時(shí)，必須首先申請(qǐng)一個(gè)頭結(jié)點(diǎn)，建立頭結(jié)點(diǎn)與二叉樹(shù)的根結(jié)點(diǎn)的指向關(guān)系，對(duì)二叉樹(shù)線(xiàn)索化后，還需建立最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的線(xiàn)索。2/5/202369數(shù)據(jù)結(jié)構(gòu)講義下面是建立中序線(xiàn)索二叉樹(shù)的遞歸算法，其中pre為全局變量。intInOrderThr(BiThrTree*head,BiThrTreeT)/*中序遍歷二叉樹(shù)T，并將其中序線(xiàn)索化，*head指向頭結(jié)點(diǎn)，pre為全局變量。*/{if(!(*head=(BiThrNodeType*)malloc(sizeof(BiThrNodeType))))

return0;(*head)->ltag=0;(*head)->rtag=1;/*建立頭結(jié)點(diǎn)*/(*head)->rchild=*head;/*右指針回指*/

if(!T)(*head)->lchild=*head;/*若二叉樹(shù)為空，則左指針回指*/

else{(*head)->lchild=T;pre=head;InThreading(T);/*中序遍歷進(jìn)行中序線(xiàn)索化*/

pre->rchild=*head;pre->rtag=1;/*最后一個(gè)結(jié)點(diǎn)線(xiàn)索化*/(*head)->rchild=pre;}return1;}2/5/202370數(shù)據(jù)結(jié)構(gòu)講義voidInTreading(BiThrTreep)/*中序遍歷進(jìn)行中序線(xiàn)索化*/{if(p){InThreading(p->lchild);/*左子樹(shù)線(xiàn)索化*/

if(!p->lchild)/*前驅(qū)線(xiàn)索*/{p->ltag=1;p->lchild=pre;}

if(!pre->rchild)/*后繼線(xiàn)索*/{pre->rtag=1;pre->rchild=p;}pre=p;InThreading(p->rchild);/*右子樹(shù)線(xiàn)索化*/}}2/5/202371數(shù)據(jù)結(jié)構(gòu)講義2．在中序線(xiàn)索二叉樹(shù)上查找任意結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)對(duì)于中序線(xiàn)索二叉樹(shù)上的任一結(jié)點(diǎn)，尋找其中序的前驅(qū)結(jié)點(diǎn)，有以下兩種情況：⑴如果該結(jié)點(diǎn)的左標(biāo)志為1，那么其左指針域所指向的結(jié)點(diǎn)便是它的前驅(qū)結(jié)點(diǎn)；⑵如果該結(jié)點(diǎn)的左標(biāo)志為0，表明該結(jié)點(diǎn)有左孩子，根據(jù)中序遍歷的定義，它的前驅(qū)結(jié)點(diǎn)是以該結(jié)點(diǎn)的左孩子為根結(jié)點(diǎn)的子樹(shù)的最右結(jié)點(diǎn)，即沿著其左子樹(shù)的右指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的右標(biāo)志為1時(shí)，它就是所要找的前驅(qū)結(jié)點(diǎn)。2/5/202372數(shù)據(jù)結(jié)構(gòu)講義在中序線(xiàn)索二叉樹(shù)上尋找結(jié)點(diǎn)p的中序前驅(qū)結(jié)點(diǎn)的算法如下：BiThrTreeInPreNode（BiThrTreep）/*在中序線(xiàn)索二叉樹(shù)上尋找結(jié)點(diǎn)p的中序前驅(qū)結(jié)點(diǎn)*/{BiThrTreepre;pre=p->lchild;if(p->ltag!=1)while(pre->rtag==0)pre=pre->rchild;return(pre);}2/5/202373數(shù)據(jù)結(jié)構(gòu)講義3．在中序線(xiàn)索二叉樹(shù)上查找任意結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)對(duì)于中序線(xiàn)索二叉樹(shù)上的任一結(jié)點(diǎn)，尋找其中序的后繼結(jié)點(diǎn)，有以下兩種情況：⑴如果該結(jié)點(diǎn)的右標(biāo)志為1，那么其右指針域所指向的結(jié)點(diǎn)便是它的后繼結(jié)點(diǎn)；⑵如果該結(jié)點(diǎn)的右標(biāo)志為0，表明該結(jié)點(diǎn)有右孩子，根據(jù)中序遍歷的定義，它的后繼結(jié)點(diǎn)是以該結(jié)點(diǎn)的右孩子為根結(jié)點(diǎn)的子樹(shù)的最左結(jié)點(diǎn)，即沿著其右子樹(shù)的左指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的左標(biāo)志為1時(shí)，它就是所要找的后繼結(jié)點(diǎn)。2/5/202374數(shù)據(jù)結(jié)構(gòu)講義在中序線(xiàn)索二叉樹(shù)上尋找結(jié)點(diǎn)p的中序后繼結(jié)點(diǎn)的算法如下：BiThrTreeInPostNode（BiThrTreep）/*在中序線(xiàn)索二叉樹(shù)上尋找結(jié)點(diǎn)p的中序后繼結(jié)點(diǎn)*/{BiThrTreepost;post=p->rchild;if(p->ltag!=1)while(post->rtag==0)post=post->lchild;return(post);}2/5/202375數(shù)據(jù)結(jié)構(gòu)講義4．在中序線(xiàn)索二叉樹(shù)上查找任意結(jié)點(diǎn)在先序下的后繼

這一操作的實(shí)現(xiàn)依據(jù)是：若一個(gè)結(jié)點(diǎn)是某子樹(shù)在中序下的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)在先序下的最后一個(gè)結(jié)點(diǎn)。該結(jié)論可以用反證法證明。

2/5/202376數(shù)據(jù)結(jié)構(gòu)講義下面就依據(jù)這一結(jié)論，討論在中序線(xiàn)索二叉樹(shù)上查找某結(jié)點(diǎn)在先序下后繼結(jié)點(diǎn)的情況。設(shè)開(kāi)始時(shí)，指向此某結(jié)點(diǎn)的指針為p。

⑴若待確定先序后繼的結(jié)點(diǎn)為分支結(jié)點(diǎn)，則又有兩種情況：

①當(dāng)p->ltag=0時(shí)，p->lchild為p在先序下的后繼；②當(dāng)p->ltag=1時(shí)，p->rchild為p在先序下的后繼。⑵若待確定先序后繼的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，則也有兩種情況：

①若p->rchild是頭結(jié)點(diǎn)，則遍歷結(jié)束；②若p->rchild不是頭結(jié)點(diǎn)，則p結(jié)點(diǎn)一定是以p->rchild結(jié)點(diǎn)為根的左子樹(shù)中在中序遍歷下的最后一個(gè)結(jié)點(diǎn)，因此p結(jié)點(diǎn)也是在該子樹(shù)中按先序遍歷的最后一個(gè)結(jié)點(diǎn)。此時(shí)，若p->rchild結(jié)點(diǎn)有右子樹(shù)，則所找結(jié)點(diǎn)在先序下的后繼結(jié)點(diǎn)的地址為p->rchild->rchild；若p->rchild為線(xiàn)索，則讓p＝p->rchild，反復(fù)情況（2）的判定。2/5/202377數(shù)據(jù)結(jié)構(gòu)講義在中序線(xiàn)索二叉樹(shù)上尋找結(jié)點(diǎn)p的先序后繼結(jié)點(diǎn)的算法如下：BiThrTreeIPrePostNode（BiThrTreehead,BiThrTreep）/*在中序線(xiàn)索二叉樹(shù)上尋找結(jié)點(diǎn)p的先序的后繼結(jié)點(diǎn),head為線(xiàn)索樹(shù)的頭結(jié)點(diǎn)*/{BiThrTreepost;if(p->ltag==0)

post=p->lchild;else{post=p;

while(post->rtag==1&&post->rchild!=head)post=post->rchild;post=post->rchild;}return(post);}2/5/202378數(shù)據(jù)結(jié)構(gòu)講義5．在中序線(xiàn)索二叉樹(shù)上查找任意結(jié)點(diǎn)在后序下的前驅(qū)

這一操作的實(shí)現(xiàn)依據(jù)是：若一個(gè)結(jié)點(diǎn)是某子樹(shù)在中序下的第一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)在后序下的第一個(gè)結(jié)點(diǎn)。該結(jié)論可以用反證法證明。2/5/202379數(shù)據(jù)結(jié)構(gòu)講義下面就依據(jù)這一結(jié)論，討論在中序線(xiàn)索二叉樹(shù)上查找某結(jié)點(diǎn)在后序下前驅(qū)結(jié)點(diǎn)的情況。設(shè)開(kāi)始時(shí)，指向此某結(jié)點(diǎn)的指針為p。⑴若待確定后序前驅(qū)的結(jié)點(diǎn)為分支結(jié)點(diǎn)，則又有兩種情況：①當(dāng)p->rtag=0時(shí)，p->rchild為p在后序下的前驅(qū)；②當(dāng)p->rtag=1時(shí)，p->lchild為p在后序下的前驅(qū)。⑵若待確定后序前驅(qū)的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，則也有兩種情況：①若p->lchild是頭結(jié)點(diǎn)，則遍歷結(jié)束；②若p->lchild不是頭結(jié)點(diǎn)，則p結(jié)點(diǎn)一定是以p->lchild結(jié)點(diǎn)為根的右子樹(shù)中在中中序遍歷下的第一個(gè)結(jié)點(diǎn)，因此p結(jié)點(diǎn)也是在該子樹(shù)中按后序遍歷的第一個(gè)結(jié)點(diǎn)。此時(shí)，若p->lchild結(jié)點(diǎn)有左子樹(shù)，則所找結(jié)點(diǎn)在后序下的前驅(qū)結(jié)點(diǎn)的地址為p->lchild->lchild；若p->lchild為線(xiàn)索，則讓p＝p->lchild，反復(fù)情況（2）的判定。2/5/202380數(shù)據(jù)結(jié)構(gòu)講義在中序線(xiàn)索二叉樹(shù)上尋找結(jié)點(diǎn)p的后序前驅(qū)結(jié)點(diǎn)的算法如下：BiThrTreeIPostPretNode（BiThrTreehead,BiThrTreep）/*在中序線(xiàn)索二叉樹(shù)上尋找結(jié)點(diǎn)p的先序的后繼結(jié)點(diǎn)，head為線(xiàn)索樹(shù)的頭結(jié)點(diǎn)*/{BiThrTreepre;if(p->rtag==0)pre=p->rchild;else{pre=p;while(pre->ltag==1&&pre->lchild!=head)pre=pre->lchild;pre=pre->lchild;}return(pre);}2/5/202381數(shù)據(jù)結(jié)構(gòu)講義6．在中序線(xiàn)索二叉樹(shù)上查找值為x的結(jié)點(diǎn)利用在中序線(xiàn)索二叉樹(shù)上尋找后繼結(jié)點(diǎn)和前驅(qū)結(jié)點(diǎn)的算法，就可以遍歷到二叉樹(shù)的所有結(jié)點(diǎn)。比如，先找到按某序遍歷的第一個(gè)結(jié)點(diǎn)，然后再依次查詢(xún)其后繼；或先找到按某序遍歷的最后一個(gè)結(jié)點(diǎn)，然后再依次查詢(xún)其前驅(qū)。這樣，既不用棧也不用遞歸就可以訪(fǎng)問(wèn)到二叉樹(shù)的所有結(jié)點(diǎn)。在中序線(xiàn)索二叉樹(shù)上查找值為x的結(jié)點(diǎn)，實(shí)質(zhì)上就是在線(xiàn)索二叉樹(shù)上進(jìn)行遍歷，將訪(fǎng)問(wèn)結(jié)點(diǎn)的操作具體寫(xiě)為那結(jié)點(diǎn)的值與x比較的語(yǔ)句。2/5/202382數(shù)據(jù)結(jié)構(gòu)講義BiThrTreeSearch(BiThrTreehead,elemtypex)/*在以head為頭結(jié)點(diǎn)的中序線(xiàn)索二叉樹(shù)中查找值為x的結(jié)點(diǎn)*/{BiThrTreep;p=head->lchild;while(p->ltag==0&&p!=head)p=p->lchild;while(p!=head&&p->data!=x)p=InPostNode(p);if(p==head){printf(“NotFoundthedata!\n”);return(0);}elsereturn(p);}2/5/202383數(shù)據(jù)結(jié)構(gòu)講義7．在中序線(xiàn)索二叉樹(shù)上的更新線(xiàn)索二叉樹(shù)的更新是指，在線(xiàn)索二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)或者刪除一個(gè)結(jié)點(diǎn)。一般情況下，這些操作有可能破壞原來(lái)已有的線(xiàn)索，因此，在修改指針時(shí)，還需要對(duì)線(xiàn)索做相應(yīng)的修改。一般來(lái)說(shuō)，這個(gè)過(guò)程的代價(jià)幾乎與重新進(jìn)行線(xiàn)索化相同。這里僅討論一種比較簡(jiǎn)單的情況，即在中序線(xiàn)索二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)p，使它成為結(jié)點(diǎn)s的右孩子。2/5/202384數(shù)據(jù)結(jié)構(gòu)講義下面分兩種情況來(lái)分析：⑴若s的右子樹(shù)為空，如圖(a)所示，則插入結(jié)點(diǎn)p之后成為圖(b)所示的情形。在這種情況中，s的后繼將成為p的中序后繼，s成為p的中序前驅(qū)，而p成為s的右孩子。二叉樹(shù)中其它部分的指針和線(xiàn)索不發(fā)生變化。

2/5/202385數(shù)據(jù)結(jié)構(gòu)講義⑵若s的右子樹(shù)非空，如圖(a)所示，插入結(jié)點(diǎn)p之后如圖(b)所示。s原來(lái)的右子樹(shù)變成p的右子樹(shù)，由于p沒(méi)有左子樹(shù)，故s成為p的中序前驅(qū)，p成為s的右孩子；又由于s原來(lái)的后繼成為p的后繼，因此還要將本來(lái)指向s的前驅(qū)左線(xiàn)索，改為指向p。2/5/202386數(shù)據(jù)結(jié)構(gòu)講義下面給出上述操作的算法。

voidInsertThrRight(BiThrTrees,BiThrTreep)

/*在中序線(xiàn)索二叉樹(shù)中插入結(jié)點(diǎn)p使其成為結(jié)點(diǎn)s的右孩子*/{BiThrTreew;p->rchild=s->rchild;p->rtag=s->rtag;p->lchild=s;p->ltag=1;/*將s變?yōu)閜的中序前驅(qū)*/

s->rchild=p;s->rtag=0;/*p成為s的右孩子*/

if(p->rtag==0)

/*當(dāng)s原來(lái)右子樹(shù)不空時(shí)，找到s的后繼w，變w為p的后繼，p為w的前驅(qū)*/{w=InPostNode(p);

/*在以p為根結(jié)點(diǎn)的子樹(shù)上找中序遍歷下的第一個(gè)結(jié)點(diǎn)*/

w->lchild=p;}}2/5/202387數(shù)據(jù)結(jié)構(gòu)講義6.5二叉樹(shù)的應(yīng)用二叉樹(shù)遍歷的應(yīng)用最優(yōu)二叉樹(shù)――哈夫曼樹(shù)2/5/202388數(shù)據(jù)結(jié)構(gòu)講義6.5.1二叉樹(shù)遍歷的應(yīng)用1．查找數(shù)據(jù)元素BiTreeSearch（BiTreebt，elemtypex）/*在bt為根結(jié)點(diǎn)指針的二叉樹(shù)中查找數(shù)據(jù)元素x*/{BiTreep;if(bt->data==x)returnbt;/*查找成功返回*/

if(bt->lchild!=NULL)return(Search(bt->lchild,x));

/*在bt->lchild為根結(jié)點(diǎn)指針的二叉樹(shù)中查找數(shù)據(jù)元素x*/if(bt->rchild!=NULL)return(Search(bt->rchild,x));

/*在bt->rchild為根結(jié)點(diǎn)指針的二叉樹(shù)中查找數(shù)據(jù)元素x*/returnNULL;/*查找失敗返回*/}2/5/202389數(shù)據(jù)結(jié)構(gòu)講義2．統(tǒng)計(jì)出給定二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目（1）順序存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)

intCountLeaf1（SqBiTreebt，intk）

/*一維數(shù)組bt[2k-1]為二叉樹(shù)存儲(chǔ)結(jié)構(gòu)，k為二叉樹(shù)深度，函數(shù)值為葉子數(shù)。*/{total=0;for(i=1;i<=2k-1;i++)if(bt[i]!=0)if((bt[2i]==0&&bt[2i+1]==0)||(i>(2k-1)/2))

total++;return(total);}2/5/202390數(shù)據(jù)結(jié)構(gòu)講義2．統(tǒng)計(jì)出給定二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目（2）二叉鏈表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)

intCountLeaf2（BiTreebt）

/*開(kāi)始時(shí)，bt為根結(jié)點(diǎn)所在鏈結(jié)點(diǎn)的指針，返回值為bt的葉子數(shù)*/{if(bt==NULL)return(0);if(bt->lchild==NULL&&bt->rchild==NULL)return(1);return(CountLeaf2(bt->lchild)+CountLeaf2(bt->rchild));}2/5/202391數(shù)據(jù)結(jié)構(gòu)講義3．創(chuàng)建二叉樹(shù)二叉鏈表存儲(chǔ)，并顯示。設(shè)創(chuàng)建時(shí)，按二叉樹(shù)帶空指針的先序次序輸入結(jié)點(diǎn)值，結(jié)點(diǎn)值類(lèi)型為字符型。輸出按中序輸出。

CreateBinTree（BinTree*bt）是以二叉鏈表為存儲(chǔ)結(jié)構(gòu)建立一棵二叉樹(shù)T的存儲(chǔ)，bt為指向二叉樹(shù)T根結(jié)點(diǎn)指針的指針。

InOrderOut（bt）為按中序輸出二叉樹(shù)bt的結(jié)點(diǎn)。2/5/202392數(shù)據(jù)結(jié)構(gòu)講義voidCreateBinTree(BinTree*T)

/*以加入結(jié)點(diǎn)的先序序列輸入，構(gòu)造二叉鏈表*/{charch;scanf("\n%c",&ch);if(ch=='0')*T=NULL;/*讀入0時(shí)，將相應(yīng)結(jié)點(diǎn)置空*/

else{*T=(BinTNode*)malloc(sizeof(BinTNode));

/*生成結(jié)點(diǎn)空間*/

(*T)->data=ch; CreateBinTree(&(*T)->lchild);

/*構(gòu)造二叉樹(shù)的左子樹(shù)*/

CreateBinTree(&(*T)->rchild);

/*構(gòu)造二叉樹(shù)的右子樹(shù)*/

}}2/5/202393數(shù)據(jù)結(jié)構(gòu)講義voidInOrderOut(BinTreeT)/*中序遍歷輸出二叉樹(shù)T的結(jié)點(diǎn)值*/{if(T){InOrderOut(T->lchild);/*中序遍歷二叉樹(shù)的左子樹(shù)*/

printf("%3c",T->data);/*訪(fǎng)問(wèn)結(jié)點(diǎn)的數(shù)據(jù)*/

InOrderOut(T->rchild);

/*中序遍歷二叉樹(shù)的右子樹(shù)*/}}main(){BiTreebt;CreateBinTree(&bt);InOrderOut(bt);}2/5/202394數(shù)據(jù)結(jié)構(gòu)講義4．表達(dá)式運(yùn)算我們可以把任意一個(gè)算數(shù)表達(dá)式用一棵二叉樹(shù)表示，圖所示為表達(dá)式3x2+x-1/x+5的二叉樹(shù)表示。在表達(dá)式二叉樹(shù)中，每個(gè)葉結(jié)點(diǎn)都是操作數(shù)，每個(gè)非葉結(jié)點(diǎn)都是運(yùn)算符。對(duì)于一個(gè)非葉子結(jié)點(diǎn)，它的左、右子樹(shù)分別是它的兩個(gè)操作數(shù)。對(duì)該二叉樹(shù)分別進(jìn)行先序、中序和后序遍歷，可以得到表達(dá)式的三種不同表示形式。前綴表達(dá)式+-+*3*xxx/1x5中綴表達(dá)式3*x*x+x-1/x+5后綴表達(dá)式3xx**x+1x/-5+2/5/202395數(shù)據(jù)結(jié)構(gòu)講義6.5.2最優(yōu)二叉樹(shù)――哈夫曼樹(shù)1．哈夫曼樹(shù)的基本概念最優(yōu)二叉樹(shù)，也稱(chēng)哈夫曼（Haffman）樹(shù)，是指對(duì)于一組帶有確定權(quán)值的葉結(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù)。二叉樹(shù)的路徑長(zhǎng)度是指由根結(jié)點(diǎn)到所有葉結(jié)點(diǎn)的路徑長(zhǎng)度之和。如果二叉樹(shù)中的葉結(jié)點(diǎn)都具有一定的權(quán)值，則可將這一概念加以推廣。設(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)度，記為：

WPL＝

Wk·Lk

其中Wk為第k個(gè)葉結(jié)點(diǎn)的權(quán)值，Lk

為第k個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度。2/5/202396數(shù)據(jù)結(jié)構(gòu)講義在給定一組具有確定權(quán)值的葉結(jié)點(diǎn)，可以構(gòu)造出不同的帶權(quán)二叉樹(shù)。例如，給出4個(gè)葉結(jié)點(diǎn)，設(shè)其權(quán)值分別為1，3，5，7，我們可以構(gòu)造出形狀不同的多個(gè)二叉樹(shù)。