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

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

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

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

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

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

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

n0＝n2＋1。

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

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

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

B＝n－1（6-2）

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

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

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

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

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

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

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

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

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

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

BiTreeCreate（elemtypex，BiTreelbt，BiTreerbt）

/*生成一棵以x為根結(jié)點的數(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é)點parent的左子樹插入結(jié)點數(shù)據(jù)元素x*/

{BiTreep;if(parent==NULL){

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

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é)點parent的左子樹。當parent或parent的左孩子結(jié)點為空時刪除失敗。刪除成功時返回根結(jié)點指針；刪除失敗時返回空指針。

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

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

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

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

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

DLR（稱為先序遍歷）

LDR（稱為中序遍歷）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

typedefstruct{BiTreelink;intflag;

}stacktype;2/5/202348數(shù)據(jù)結(jié)構(gòu)講義后序遍歷二叉樹的非遞歸算法如下。在算法中，一維數(shù)組stack[MAXNODE]用于實現(xiàn)棧的結(jié)構(gòu)，指針變量p指向當前要處理的結(jié)點，整型變量top用來表示當前棧頂?shù)奈恢?，整型變量sign為結(jié)點p的標志量。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é)點第一次進棧*/{top++;stack[top].link=p;stack[top].flag=1;p=p->lchild;/*找該結(jié)點的左孩子*/}

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

/*結(jié)點第二次進棧*/{top++;stack[top].link=p;stack[top].flag=2;/*標記第二次出棧*/

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

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

ABCDEFGHI

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

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

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

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

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

ltag＝

rtag＝

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

typedefcharelemtype;

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

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

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

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

pre->rchild=*head;pre->rtag=1;/*最后一個結(jié)點線索化*/(*head)->rchild=pre;}return1;}2/5/202370數(shù)據(jù)結(jié)構(gòu)講義voidInTreading(BiThrTreep)/*中序遍歷進行中序線索化*/{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é)點的中序前驅(qū)結(jié)點對于中序線索二叉樹上的任一結(jié)點，尋找其中序的前驅(qū)結(jié)點，有以下兩種情況：⑴如果該結(jié)點的左標志為1，那么其左指針域所指向的結(jié)點便是它的前驅(qū)結(jié)點；⑵如果該結(jié)點的左標志為0，表明該結(jié)點有左孩子，根據(jù)中序遍歷的定義，它的前驅(qū)結(jié)點是以該結(jié)點的左孩子為根結(jié)點的子樹的最右結(jié)點，即沿著其左子樹的右指針鏈向下查找，當某結(jié)點的右標志為1時，它就是所要找的前驅(qū)結(jié)點。2/5/202372數(shù)據(jù)結(jié)構(gòu)講義在中序線索二叉樹上尋找結(jié)點p的中序前驅(qū)結(jié)點的算法如下：BiThrTreeInPreNode（BiThrTreep）/*在中序線索二叉樹上尋找結(jié)點p的中序前驅(qū)結(jié)點*/{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é)點的中序后繼結(jié)點對于中序線索二叉樹上的任一結(jié)點，尋找其中序的后繼結(jié)點，有以下兩種情況：⑴如果該結(jié)點的右標志為1，那么其右指針域所指向的結(jié)點便是它的后繼結(jié)點；⑵如果該結(jié)點的右標志為0，表明該結(jié)點有右孩子，根據(jù)中序遍歷的定義，它的后繼結(jié)點是以該結(jié)點的右孩子為根結(jié)點的子樹的最左結(jié)點，即沿著其右子樹的左指針鏈向下查找，當某結(jié)點的左標志為1時，它就是所要找的后繼結(jié)點。2/5/202374數(shù)據(jù)結(jié)構(gòu)講義在中序線索二叉樹上尋找結(jié)點p的中序后繼結(jié)點的算法如下：BiThrTreeInPostNode（BiThrTreep）/*在中序線索二叉樹上尋找結(jié)點p的中序后繼結(jié)點*/{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é)點在先序下的后繼

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

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

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

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

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

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

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

voidInsertThrRight(BiThrTrees,BiThrTreep)

/*在中序線索二叉樹中插入結(jié)點p使其成為結(jié)點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)

/*當s原來右子樹不空時，找到s的后繼w，變w為p的后繼，p為w的前驅(qū)*/{w=InPostNode(p);

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

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é)點指針的二叉樹中查找數(shù)據(jù)元素x*/{BiTreep;if(bt->data==x)returnbt;/*查找成功返回*/

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

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

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

intCountLeaf1（SqBiTreebt，intk）

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

intCountLeaf2（BiTreebt）

/*開始時，bt為根結(jié)點所在鏈結(jié)點的指針，返回值為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è)創(chuàng)建時，按二叉樹帶空指針的先序次序輸入結(jié)點值，結(jié)點值類型為字符型。輸出按中序輸出。

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

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

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

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

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

(*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é)點值*/{if(T){InOrderOut(T->lchild);/*中序遍歷二叉樹的左子樹*/

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

InOrderOut(T->rchild);

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

WPL＝

Wk·Lk

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

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