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

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

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

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

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

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

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

n0＝n2＋1。

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

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

在二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有唯一的一個(gè)進(jìn)入分支。設(shè)B為二叉樹中的分支數(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)的完全二叉樹的深度k為log2n+1。

證明根據(jù)完全二叉樹的定義和性質(zhì)2可知，當(dāng)一棵完全二叉樹的深度為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)的完全二叉樹，如果按照從上至下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從1開始順序編號(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ì)二叉樹的根結(jié)點(diǎn)從0開始編號(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)二叉樹的存儲(chǔ)二叉樹的基本操作及實(shí)現(xiàn)2/5/202314數(shù)據(jù)結(jié)構(gòu)講義6.2.1二叉樹的存儲(chǔ)1．順序存儲(chǔ)結(jié)構(gòu)所謂二叉樹的順序存儲(chǔ)，就是用一組連續(xù)的存儲(chǔ)單元存放二叉樹中的結(jié)點(diǎn)。一般是按照二叉樹結(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ù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序存儲(chǔ)比較合適，樹中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系，這樣既能夠最大可能地節(jié)省存儲(chǔ)空間，又可以利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹中的位置，以及結(jié)點(diǎn)之間的關(guān)系。2/5/202315數(shù)據(jù)結(jié)構(gòu)講義下面給出一棵完全二叉樹的順序存儲(chǔ)示意。2/5/202316數(shù)據(jù)結(jié)構(gòu)講義對(duì)于一般的二叉樹，如果仍按從上至下和從左到右的順序?qū)渲械慕Y(jié)點(diǎn)順序存儲(chǔ)在一維數(shù)組中，則數(shù)組元素下標(biāo)之間的關(guān)系不能夠反映二叉樹中結(jié)點(diǎn)之間的邏輯關(guān)系，只有增添一些并不存在的空結(jié)點(diǎn)，使之成為一棵完全二叉樹的形式，然后再用一維數(shù)組順序存儲(chǔ)。2/5/202317數(shù)據(jù)結(jié)構(gòu)講義如圖給出了一棵一般二叉樹改造后的完全二叉樹形態(tài)和其順序存儲(chǔ)狀態(tài)示意圖。顯然，這種存儲(chǔ)對(duì)于需增加許多空結(jié)點(diǎn)才能將一棵二叉樹改造成為一棵完全二叉樹的存儲(chǔ)時(shí)，會(huì)造成空間的大量浪費(fèi)，不宜用順序存儲(chǔ)結(jié)構(gòu)。2/5/202318數(shù)據(jù)結(jié)構(gòu)講義最壞的情況是右單支樹，一棵深度為k的右單支樹，只有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)給出一棵二叉樹的二叉鏈表示。二叉鏈表也可以帶頭結(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)而言，它增加了空間開銷。2/5/202322數(shù)據(jù)結(jié)構(gòu)講義下圖給出一棵二叉樹的三叉鏈表示。2/5/202323數(shù)據(jù)結(jié)構(gòu)講義盡管在二叉鏈表中無(wú)法由結(jié)點(diǎn)直接找到其雙親，但由于二叉鏈表結(jié)構(gòu)靈活，操作方便，對(duì)于一般情況的二叉樹，甚至比順序存儲(chǔ)結(jié)構(gòu)還節(jié)省空間。因此，二叉鏈表是最常用的二叉樹存儲(chǔ)方式。本書后面所涉及到的二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不加特別說(shuō)明的都是指二叉鏈表結(jié)構(gòu)。二叉樹的二叉鏈表存儲(chǔ)表示可描述為：

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

intInitiate(BiTree*bt)/*初始化建立二叉樹*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ù)域信息，以二叉樹lbt和rbt為左右子樹的二叉樹。建立成功時(shí)返回所建二叉樹結(jié)點(diǎn)的指針；建立失敗時(shí)返回空指針。

BiTreeCreate（elemtypex，BiTreelbt，BiTreerbt）

/*生成一棵以x為根結(jié)點(diǎn)的數(shù)據(jù)域值以lbt和rbt為左右子樹的二叉樹*/{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）

/*在二叉樹bt的結(jié)點(diǎn)parent的左子樹插入結(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）在二叉樹bt中刪除結(jié)點(diǎn)parent的左子樹。當(dāng)parent或parent的左孩子結(jié)點(diǎn)為空時(shí)刪除失敗。刪除成功時(shí)返回根結(jié)點(diǎn)指針；刪除失敗時(shí)返回空指針。

BiTreeDeleteL（BiTreebt，BiTreeparent）/*在二叉樹bt中刪除結(jié)點(diǎn)parent的左子樹*/{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í)，這樣刪除僅釋放了所刪子樹根結(jié)點(diǎn)的空間，若要?jiǎng)h除子樹分支中的結(jié)點(diǎn)，需用后面介紹的遍歷操作來(lái)實(shí)現(xiàn)。*/

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

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

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

DLR（稱為先序遍歷）

LDR（稱為中序遍歷）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

GDBEFCA2/5/202340數(shù)據(jù)結(jié)構(gòu)講義6.3.2二叉樹遍歷的非遞歸實(shí)現(xiàn)前面給出的二叉樹先序、中序和后序三種遍歷算法都是遞歸算法。當(dāng)給出二叉樹的鏈?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)講義如前圖所示的二叉樹，對(duì)其進(jìn)行先序、中序和后序遍歷都是從根結(jié)點(diǎn)A開始的，且在遍歷過(guò)程中經(jīng)過(guò)結(jié)點(diǎn)的路線也是一樣的，只是訪問(wèn)的時(shí)機(jī)不同而已。下圖中所示的從根結(jié)點(diǎn)左外側(cè)開始，由根結(jié)點(diǎn)右外側(cè)結(jié)束的曲線，為遍歷前圖的路線。沿著該路線按△標(biāo)記的結(jié)點(diǎn)讀得的序列為先序序列，按*標(biāo)記讀得的序列為中序序列，按⊕標(biāo)記讀得的序列為后序序列。2/5/202342數(shù)據(jù)結(jié)構(gòu)講義然而，這一路線正是從根結(jié)點(diǎn)開始沿左子樹深入下去，當(dāng)深入到最左端，無(wú)法再深入下去時(shí)，則返回，再逐一進(jìn)入剛才深入時(shí)遇到結(jié)點(diǎn)的右子樹，再進(jìn)行如此的深入和返回，直到最后從根結(jié)點(diǎn)的右子樹返回到根結(jié)點(diǎn)為止。先序遍歷是在深入時(shí)遇到結(jié)點(diǎn)就訪問(wèn)，中序遍歷是在從左子樹返回時(shí)遇到結(jié)點(diǎn)訪問(wèn)，后序遍歷是在從右子樹返回時(shí)遇到結(jié)點(diǎn)訪問(wèn)。在這一過(guò)程中，返回結(jié)點(diǎn)的順序與深入結(jié)點(diǎn)的順序相反，即后深入先返回，可以用棧來(lái)幫助實(shí)現(xiàn)這一遍歷路線。其過(guò)程如下：在沿左子樹深入時(shí)，深入一個(gè)結(jié)點(diǎn)入棧一個(gè)結(jié)點(diǎn)，若為先序遍歷，則在入棧之前訪問(wèn)之；當(dāng)沿左分支深入不下去時(shí)，則返回，即從堆棧中彈出前面壓入的結(jié)點(diǎn)，若為中序遍歷，則此時(shí)訪問(wèn)該結(jié)點(diǎn)，然后從該結(jié)點(diǎn)的右子樹繼續(xù)深入；若為后序遍歷，則將此結(jié)點(diǎn)再次入棧，然后從該結(jié)點(diǎn)的右子樹繼續(xù)深入，與前面類同，仍為深入一個(gè)結(jié)點(diǎn)入棧一個(gè)結(jié)點(diǎn)，深入不下去再返回，直到第二次從棧里彈出該結(jié)點(diǎn)，即從右子樹返回時(shí)，才訪問(wèn)之。2/5/202343數(shù)據(jù)結(jié)構(gòu)講義（1）先序遍歷的非遞歸實(shí)現(xiàn)在下面算法中，二叉樹以二叉鏈表存放，一維數(shù)組stack[MAXNODE]用以實(shí)現(xiàn)棧，變量top用來(lái)表示當(dāng)前棧頂?shù)奈恢?。voidNRPreOrder（BiTreebt）

/*非遞歸先序遍歷二叉樹*/{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);/*訪問(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ì)于下圖所示的二叉樹，用該算法進(jìn)行遍歷過(guò)程中，棧stack和當(dāng)前指針p的變化情況以及樹中各結(jié)點(diǎn)的訪問(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)要入兩次棧，出兩次棧，而訪問(wèn)結(jié)點(diǎn)是在第二次出棧時(shí)訪問(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ù)類型定義為指針和標(biāo)志flag合并的結(jié)構(gòu)體類型。定義如下：

typedefstruct{BiTreelink;intflag;

}stacktype;2/5/202348數(shù)據(jù)結(jié)構(gòu)講義后序遍歷二叉樹的非遞歸算法如下。在算法中，一維數(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)/*非遞歸后序遍歷二叉樹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);/*訪問(wèn)該結(jié)點(diǎn)數(shù)據(jù)域值*/

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

ABCDEFGHI

BCAEDGHFI試恢復(fù)該二叉樹。2/5/202354數(shù)據(jù)結(jié)構(gòu)講義上述過(guò)程是一個(gè)遞歸過(guò)程，其遞歸算法的思想是：先根據(jù)先序序列的第一個(gè)元素建立根結(jié)點(diǎn)；然后在中序序列中找到該元素，確定根結(jié)點(diǎn)的左、右子樹的中序序列；再在先序序列中確定左、右子樹的先序序列；最后由左子樹的先序序列與中序序列建立左子樹，由右子樹的先序序列與中序序列建立右子樹。2/5/202355數(shù)據(jù)結(jié)構(gòu)講義下面給出用C語(yǔ)言描述的該算法。假設(shè)二叉樹的先序序列和中序序列分別存放在一維數(shù)組preod[]與inod[]中，并假設(shè)二叉樹各結(jié)點(diǎn)的數(shù)據(jù)值均不相同。voidReBiTree（charpreod[],charinod[],intn,BiTreeroot）/*n為二叉樹的結(jié)點(diǎn)個(gè)數(shù)，root為二叉樹根結(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不用棧的二叉樹遍歷的非遞歸方法前面介紹的二叉樹的遍歷算法可分為兩類，一類是依據(jù)二叉樹結(jié)構(gòu)的遞歸性，采用遞歸調(diào)用的方式來(lái)實(shí)現(xiàn)；另一類則是通過(guò)堆棧或隊(duì)列來(lái)輔助實(shí)現(xiàn)。采用這兩類方法對(duì)二叉樹進(jìn)行遍歷時(shí)，遞歸調(diào)用和棧或隊(duì)列的使用都帶來(lái)額外空間增加，遞歸調(diào)用的深度和棧的大小是動(dòng)態(tài)變化的，都與二叉樹的高度有關(guān)。因此，在最壞的情況下，即二叉樹退化為單支樹的情況下，遞歸的深度或棧需要的存儲(chǔ)空間等于二叉樹中的結(jié)點(diǎn)數(shù)。2/5/202358數(shù)據(jù)結(jié)構(gòu)講義還有一類二叉樹的遍歷算法，就是不用棧也不用遞歸來(lái)實(shí)現(xiàn)。常用的不用棧的二叉樹遍歷的非遞歸方法有以下三種：⑴對(duì)二叉樹采用三叉鏈表存放，即在二叉樹的每個(gè)結(jié)點(diǎn)中增加一個(gè)雙親域parent，這樣，在遍歷深入到不能再深入時(shí)，可沿著走過(guò)的路徑回退到任何一棵子樹的根結(jié)點(diǎn)，并再向另一方向走。⑵采用逆轉(zhuǎn)鏈的方法，即在遍歷深入時(shí)，每深入一層，就將其再深入的孩子結(jié)點(diǎn)的地址取出，并將其雙親結(jié)點(diǎn)的地址存入。當(dāng)深入不下去而需返回時(shí)，可逐級(jí)取出雙親結(jié)點(diǎn)的地址，沿原路返回。⑶在線索二叉樹上的遍歷，即利用具有n個(gè)結(jié)點(diǎn)的二叉樹中的葉子結(jié)點(diǎn)和一度結(jié)點(diǎn)的n＋1個(gè)空指針域，來(lái)存放線索，然后在這種具有線索的二叉樹上遍歷時(shí)，就可不需要棧，也不需要遞歸了。2/5/202359數(shù)據(jù)結(jié)構(gòu)講義6.3.5層次遍歷所謂二叉樹的層次遍歷，是指從二叉樹的第一層（根結(jié)點(diǎn)）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。對(duì)于下圖所示的二叉樹，按層次遍歷所得到的結(jié)果序列為：

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

voidLevelOrder（BiTreebt）/*層次遍歷二叉樹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);/*訪問(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線索二叉樹線索二叉樹的定義及結(jié)構(gòu)線索二叉樹的基本操作實(shí)現(xiàn)2/5/202364數(shù)據(jù)結(jié)構(gòu)講義6.4.1線索二叉樹的定義及結(jié)構(gòu)1．線索二叉樹的定義按照某種遍歷方式對(duì)二叉樹進(jìn)行遍歷，可以把二叉樹中所有結(jié)點(diǎn)排列為一個(gè)線性序列。在該序列中，除第一個(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)。但是，二叉樹中每個(gè)結(jié)點(diǎn)在這個(gè)序列中的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)是什么，二叉樹的存儲(chǔ)結(jié)構(gòu)中并沒(méi)有反映出來(lái)，只能在對(duì)二叉樹遍歷的動(dòng)態(tài)過(guò)程中得到這些信息。為了保留結(jié)點(diǎn)在某種遍歷序列中直接前驅(qū)和直接后繼的位置信息，利用二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)中的那些空指針域來(lái)指示。這些指向直接前驅(qū)結(jié)點(diǎn)和指向直接后繼結(jié)點(diǎn)的指針被稱為線索（thread），加了線索的二叉樹稱為線索二叉樹。線索二叉樹將為二叉樹的遍歷提供許多遍歷。2/5/202365數(shù)據(jù)結(jié)構(gòu)講義2．線索二叉樹的結(jié)構(gòu)由于序列可由不同的遍歷方法得到，因此，線索樹有先序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。把二叉樹改造成線索二叉樹的過(guò)程稱為線索化。對(duì)前圖所示的二叉樹進(jìn)行線索化，得到先序線索二叉樹、中序線索二叉樹和后序線索二叉樹分別如圖(a)、(b)、(c)所示。圖中實(shí)線表示指針，虛線表示線索。2/5/202366數(shù)據(jù)結(jié)構(gòu)講義那么，下面的問(wèn)題是在存儲(chǔ)中，如何區(qū)別某結(jié)點(diǎn)的指針域內(nèi)存放的是指針還是線索？通?？梢圆捎孟旅鎯煞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)，僅在作為線索的地址前加一個(gè)負(fù)號(hào)，即負(fù)的地址表示線索，正的地址表示指針。2/5/202367數(shù)據(jù)結(jié)構(gòu)講義6.4.2線索二叉樹的基本操作實(shí)現(xiàn)在線索二叉樹中，結(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．建立一棵中序線索二叉樹建立線索二叉樹，或者說(shuō)對(duì)二叉樹線索化，實(shí)質(zhì)上就是遍歷一棵二叉樹。在遍歷過(guò)程中，訪問(wèn)結(jié)點(diǎn)的操作是檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空，如果為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索。為實(shí)現(xiàn)這一過(guò)程，設(shè)指針pre始終指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)，即若指針p指向當(dāng)前結(jié)點(diǎn)，則pre指向它的前驅(qū)，以便增設(shè)線索。另外，在對(duì)一棵二叉樹加線索時(shí)，必須首先申請(qǐng)一個(gè)頭結(jié)點(diǎn)，建立頭結(jié)點(diǎn)與二叉樹的根結(jié)點(diǎn)的指向關(guān)系，對(duì)二叉樹線索化后，還需建立最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的線索。2/5/202369數(shù)據(jù)結(jié)構(gòu)講義下面是建立中序線索二叉樹的遞歸算法，其中pre為全局變量。intInOrderThr(BiThrTree*head,BiThrTreeT)/*中序遍歷二叉樹T，并將其中序線索化，*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;/*若二叉樹為空，則左指針回指*/

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

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

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

if(!pre->rchild)/*后繼線索*/{pre->rtag=1;pre->rchild=p;}pre=p;InThreading(p->rchild);/*右子樹線索化*/}}2/5/202371數(shù)據(jù)結(jié)構(gòu)講義2．在中序線索二叉樹上查找任意結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)對(duì)于中序線索二叉樹上的任一結(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)的子樹的最右結(jié)點(diǎn)，即沿著其左子樹的右指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的右標(biāo)志為1時(shí)，它就是所要找的前驅(qū)結(jié)點(diǎn)。2/5/202372數(shù)據(jù)結(jié)構(gòu)講義在中序線索二叉樹上尋找結(jié)點(diǎn)p的中序前驅(qū)結(jié)點(diǎn)的算法如下：BiThrTreeInPreNode（BiThrTreep）/*在中序線索二叉樹上尋找結(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．在中序線索二叉樹上查找任意結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)對(duì)于中序線索二叉樹上的任一結(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)的子樹的最左結(jié)點(diǎn)，即沿著其右子樹的左指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的左標(biāo)志為1時(shí)，它就是所要找的后繼結(jié)點(diǎn)。2/5/202374數(shù)據(jù)結(jié)構(gòu)講義在中序線索二叉樹上尋找結(jié)點(diǎn)p的中序后繼結(jié)點(diǎn)的算法如下：BiThrTreeInPostNode（BiThrTreep）/*在中序線索二叉樹上尋找結(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．在中序線索二叉樹上查找任意結(jié)點(diǎn)在先序下的后繼

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

2/5/202376數(shù)據(jù)結(jié)構(gòu)講義下面就依據(jù)這一結(jié)論，討論在中序線索二叉樹上查找某結(jié)點(diǎn)在先序下后繼結(jié)點(diǎn)的情況。設(shè)開始時(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)為根的左子樹中在中序遍歷下的最后一個(gè)結(jié)點(diǎn)，因此p結(jié)點(diǎn)也是在該子樹中按先序遍歷的最后一個(gè)結(jié)點(diǎn)。此時(shí)，若p->rchild結(jié)點(diǎn)有右子樹，則所找結(jié)點(diǎn)在先序下的后繼結(jié)點(diǎn)的地址為p->rchild->rchild；若p->rchild為線索，則讓p＝p->rchild，反復(fù)情況（2）的判定。2/5/202377數(shù)據(jù)結(jié)構(gòu)講義在中序線索二叉樹上尋找結(jié)點(diǎn)p的先序后繼結(jié)點(diǎn)的算法如下：BiThrTreeIPrePostNode（BiThrTreehead,BiThrTreep）/*在中序線索二叉樹上尋找結(jié)點(diǎn)p的先序的后繼結(jié)點(diǎn),head為線索樹的頭結(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．在中序線索二叉樹上查找任意結(jié)點(diǎn)在后序下的前驅(qū)

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

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

voidInsertThrRight(BiThrTrees,BiThrTreep)

/*在中序線索二叉樹中插入結(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í)，找到s的后繼w，變w為p的后繼，p為w的前驅(qū)*/{w=InPostNode(p);

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

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

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

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

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

intCountLeaf1（SqBiTreebt，intk）

/*一維數(shù)組bt[2k-1]為二叉樹存儲(chǔ)結(jié)構(gòu)，k為二叉樹深度，函數(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ì)出給定二叉樹中葉子結(jié)點(diǎn)的數(shù)目（2）二叉鏈表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)

intCountLeaf2（BiTreebt）

/*開始時(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)建二叉樹二叉鏈表存儲(chǔ)，并顯示。設(shè)創(chuàng)建時(shí)，按二叉樹帶空指針的先序次序輸入結(jié)點(diǎn)值，結(jié)點(diǎn)值類型為字符型。輸出按中序輸出。

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

InOrderOut（bt）為按中序輸出二叉樹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)造二叉樹的左子樹*/

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

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

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

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

InOrderOut(T->rchild);

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