算法與數(shù)據(jù)結(jié)構(gòu),第4章 樹與二叉樹,樹和二叉樹,在前兩章討論的數(shù)據(jù)結(jié)構(gòu)都屬于線性結(jié)構(gòu)。線性結(jié)構(gòu)的邏輯結(jié)構(gòu)簡單，易于實現(xiàn)各種運算和操作，主要用于描述客觀世界中具有單一前趨和單一后繼的數(shù)據(jù)關(guān)系。 然而，客觀世界中的許多事物的關(guān)系并非如此簡單，如人類社會中的族譜、各種社會組織機構(gòu)、交通道路和通訊網(wǎng)絡(luò)等，其中的聯(lián)系都是較為復(fù)雜的非線性關(guān)系，宜用非線性結(jié)構(gòu)來描述其數(shù)據(jù)關(guān)系。 樹與二叉樹中，每個數(shù)據(jù)元素至多只有一個前趨，但可以有多個后繼；數(shù)據(jù)元素間的關(guān)系是一對多的層次關(guān)系，主要用于描述客觀世界中具有層次結(jié)構(gòu)的數(shù)據(jù)關(guān)系。,第4章 樹與二叉樹,4.1 樹的基本概念 4.2 二叉樹 4.3 二叉樹的遍歷 4.4 線索二叉樹 4.5 樹和森林 4.6 哈夫曼樹,4.1 樹的基本概念,4.1.1 樹的定義及表示 4.1.2 樹的常用術(shù)語及運算,樹的定義及表示,客觀世界中的許多事物的關(guān)系可以用樹來描述，如人類社會中家族成員之間的血緣關(guān)系，以英國女王家族為例可表示成如下圖所示。 上圖看上去很像一棵倒置的樹，樹型結(jié)構(gòu)便由此而得名。,樹的遞歸定義,樹（tree）是n（n0）個結(jié)點的有限集合T。 當(dāng)n=0時稱為空樹，否則稱為非空樹。 在任一非空樹中，有且僅有一個稱為樹的根的結(jié)點；除根結(jié)點之外的其余結(jié)點可分為m（m0）個互不相交的集合T1，T2，Tm，其中每個集合本身又都是一棵樹，并且稱為根的子樹。 這是一個遞歸定義，即在樹的定義中又用到了樹這個術(shù)語，它反映了樹的固有特性： 即一棵樹由若干棵子樹構(gòu)成，而每棵子樹又都分別由若干棵更小的子樹構(gòu)成。,樹的遞歸定義（續(xù)）,這個樹的遞歸定義可以從如下三點來理解： 沒有任何結(jié)點的樹稱為空樹，這是樹的特例。 非空樹中至少有一個結(jié)點，只有一個結(jié)點時它就是樹的根，只有根結(jié)點的樹稱為最小非空樹。 在含有多個結(jié)點的樹中，除根結(jié)點外其余結(jié)點構(gòu)成若干棵子樹，且各子樹間互不相交。,樹的示例,下圖中，(a)是只有一個根結(jié)點的樹。(b)是有六個結(jié)點的一般樹，其中A是根，其余結(jié)點分成三個互不相交的子集：T1=B，T2=C，E，F(xiàn)，T3=D；T1、T2和T3是A的子樹，且其本身也都是一棵樹；其中，T1的根為B其子樹為空樹，T3的根為D其子樹為空樹，T2的根為C剩余結(jié)點分成兩個互不相交的子集T21=E和T22=F，T21和T22都是C的子樹。,樹的非遞歸定義,樹的非遞歸定義可以敘述為：稱數(shù)據(jù)結(jié)構(gòu)tree(D,R)為樹，則R中只有一個關(guān)系，且滿足以下條件： (1) 有且僅有一個沒有前趨的結(jié)點w，稱為樹的根； (2) 除根w外的每一個結(jié)點都有且只有一個前趨； (3) 對于除根w外的每一個結(jié)點K，都有一個從根w到k的一個結(jié)點序列K0(w)，K1，K2，Ki-1，Ki，Kn(k)（n1），其中Ki是Ki-1的后繼。 這個非遞歸定義中的(1)和(2)容易理解；對于(3)以前一頁的圖(b)中的任一結(jié)點如E說明一下，從根A到E存在一個線性序列A、C、E，序列中后一個結(jié)點是它前面一個結(jié)點的后繼，即C是A的后繼，E是C的后繼。,樹的表示,通常樹的表示方法有樹形表示、嵌套集合表示、凹入表示和廣義表表示四種，如下圖所示：,4.1 樹的基本概念,4.1.1 樹的定義及表示 4.1.2 樹的常用術(shù)語及運算,樹常用的基本術(shù)語,樹的結(jié)點：是指一個數(shù)據(jù)元素及其若干指向其子樹的分支，通常用一個記錄或結(jié)構(gòu)體來描述，在樹形表示中用一個圓圈及短線來表示。 結(jié)點的度：是指結(jié)點擁有的子樹數(shù)目。如右圖中，結(jié)點A的度為3，C的度為2，B、D、E、F的度為0。 葉子或終端結(jié)點：是指度為0的結(jié)點，如右圖)中的B、D、E、F都是葉子結(jié)點。 分支結(jié)點或非終端結(jié)點：是指度不為0的結(jié)點，如右圖中的A和C結(jié)點；通常又把非根的分支結(jié)點稱為內(nèi)部結(jié)點，如右圖中的C結(jié)點。 樹的度：是指樹中各結(jié)點度的最大值，如右圖中的樹的度為3。,樹常用的基本術(shù)語（續(xù)）,結(jié)點的層次：從根結(jié)點開始，根為第一層，根的孩子為第二層，依次類推。如右上圖中的A在第一層，B、C、D在第二層，E和F在第三層。 樹的深度或高度：是樹中結(jié)點的最大層次數(shù)。如右上圖中的樹高度為3。 有序樹和無序樹：如果將樹中結(jié)點的各子樹看成是從左到右依次有序且不能交換，則稱該樹為有序樹，否則稱為無序樹。如右下圖給出了兩棵不同的有序樹。 森林：是m棵互不相交的樹的集合。刪除一棵樹的根就會得到由子樹構(gòu)成的森林；反之，給森林加上一個根就會變成為一棵樹。,樹的其它術(shù)語,有時也引用家族樹中的一些習(xí)慣用語，如孩子、雙親、祖先、子孫、兄弟等。如稱結(jié)點的子樹的根為該結(jié)點的孩子，該結(jié)點稱為孩子的雙親； 同一個雙親的孩子之間互稱為兄弟；從結(jié)點向上到達根結(jié)點所途經(jīng)的所有結(jié)點稱為該結(jié)點的祖先，從結(jié)點向下所能到達的所有結(jié)點稱為該結(jié)點的子孫。如右圖中，A是B、C和D的雙親，B、C和D都是A的孩子，B、C和D三者之間互為兄弟；A和C是E的祖先，A的子孫是B、C、D、E和F。,樹的基本運算,setnull(T)：置T為空樹，即初始化一棵樹T。 root(T)或root(x)：求根函數(shù)。求樹T的根或求結(jié)點x所在樹的根結(jié)點，若T為空樹或x不在樹T中，則函數(shù)值為NULL。 parent(T，x)：求雙親函數(shù)。求樹T中結(jié)點x的雙親結(jié)點，若x是樹T的根結(jié)點或x不在樹T中，則函數(shù)值為NULL。 child(T，x，i)：求孩子函數(shù)。求樹T中結(jié)點x的第i個孩子結(jié)點，若結(jié)點x無第i個孩子則函數(shù)值為NULL。 create(x，F(xiàn))：建樹函數(shù)。生成一棵以x為根結(jié)點，以森林F為子樹森林的樹。 rsibling(T，x)：求右兄弟函數(shù)。求樹T中結(jié)點x的右邊兄弟，若x是其雙親的最右孩子或x不在T中，則函數(shù)值為NULL。,樹的基本運算（續(xù)）,addchild(y，i，x)：插入子樹操作。把以結(jié)點x為根的樹置為結(jié)點y的第i棵子樹。若樹中無結(jié)點y或它的子樹個數(shù)小于i-1，則為空操作。 delchild(x，i)：刪除子樹操作。刪除結(jié)點x的第i棵子樹，若無結(jié)點x或x的子樹個數(shù)小于i，則為空操作。 traverse(T)：遍歷操作。按某個次序依次訪問樹中各個結(jié)點，并使每個結(jié)點只被訪問一次。也就是說，遍歷操作的結(jié)果是對非線性結(jié)構(gòu)樹中各結(jié)點，按某個次序給出一個線性化的結(jié)點序列。,第4章 樹與二叉樹,4.1 樹的基本概念 4.2 二叉樹 4.3 二叉樹的遍歷 4.4 線索二叉樹 4.5 樹和森林 4.6 哈夫曼樹,4.2 二叉樹,4.2.1 二叉樹的概念 4.2.2 二叉樹的性質(zhì) 4.2.3 二叉樹的存儲結(jié)構(gòu) 4.2.4 二叉樹的簡單運算實現(xiàn),二叉樹的概念,二叉樹是另一種重要的樹型結(jié)構(gòu)。它的特點是每個結(jié)點至多有兩棵子樹，即二叉樹中任何結(jié)點的度不得大于2。 二叉樹的定義： 二叉樹（binary tree）是n（n0）個結(jié)點的有限集合，它或者（n=0時）為空樹，或者（n0時）由一個根結(jié)點及兩棵互不相交的分別稱為根的左子樹和右子樹的二叉樹組成。,二叉樹的概念（續(xù)）,由定義顯見二叉樹的遞歸性質(zhì)。 應(yīng)該指出的是，二叉樹與樹是兩個不同的概念，它不是樹的特殊情況；這是因為二叉樹的子樹有左右之分，而樹的子樹不必區(qū)分次序。 另外二叉樹與度為2的有序樹也是不同的概念；因為對于二叉樹的子樹而言，要么是根的左子樹，要么是根的右子樹，即使只有一棵子樹也要區(qū)分是左是右；而度為2的有序樹中，當(dāng)一個結(jié)點有兩棵子樹時有左右之分，而只有一棵子樹時就無左右之分。,二叉樹與度為2的普通樹的區(qū)別舉例,在下圖中，(a)和(b)所示的兩棵二叉樹雖然與(c)所示的普通樹相似，但卻不等同于這棵普通樹。,二叉樹的五種基本形態(tài),二叉樹可以是空樹，根也可以有空的左子樹、空的右子樹或左右子樹均為空，因此二叉樹有五種基本形態(tài)，如下圖所示：,二叉樹的基本運算,樹的術(shù)語對于二叉樹都適用。 與樹的基本運算類似，二叉樹也有如下的一些基本運算： 求二叉樹的根root(bt)； 求二叉樹中結(jié)點x的雙親parent(bt,x)； 求二叉樹中結(jié)點x的左孩子或右孩子lchild(bt,x)和rchild(bt,x)； 設(shè)置空二叉樹setnull(bt)； 建立以x為根，以二叉樹lbt和rbt為左右子樹的一棵二叉樹create(x,lbt,rbt)；,二叉樹的基本運算（續(xù)）,置以y為根的二叉樹為結(jié)點x的左子樹或右子樹addlchild(bt,x,y)和addrchild(bt,x,y)； 刪除結(jié)點x的左子樹或右子樹dellchild(bt,x)和delrchild(bt,x)； 在二叉樹中查找結(jié)點x的運算search(bt,x)； 按照某種次序遍歷二叉樹中的所有結(jié)點traverse(bt)。,4.2 二叉樹,4.2.1 二叉樹的概念 4.2.2 二叉樹的性質(zhì) 4.2.3 二叉樹的存儲結(jié)構(gòu) 4.2.4 二叉樹的簡單運算實現(xiàn),二叉樹的性質(zhì),二叉樹具有一些重要性質(zhì)。 性質(zhì)1 二叉樹的第i（i1）層上至多有2i-1個結(jié)點。 證明：用數(shù)學(xué)歸納法證明如下： 當(dāng)i=1時只有一個結(jié)點，2i-1=20=1，命題成立。 設(shè)對于任意的j，1ji時命題成立，即第j層上至多含有2j-1個結(jié)點。 則由歸納假設(shè)第i-1層上至多含有2i-2個結(jié)點。由于二叉樹中每個結(jié)點至多有兩個孩子，故第i層上的最大結(jié)點數(shù)應(yīng)為第i-1層上最大結(jié)點數(shù)的二倍，即2*2i-2=2i-1成立，故命題成立。,二叉樹的性質(zhì)（續(xù)）,性質(zhì)2 深度為k的二叉樹至多有2k-1個結(jié)點（k1）。 證明：深度為k的二叉樹最多含有的結(jié)點數(shù)應(yīng)是每層含有的最多結(jié)點數(shù)之和，由性質(zhì)1應(yīng)為20+21+2k-1=2k-1。 性質(zhì)3 對任意一棵二叉樹，若終端結(jié)點數(shù)為n，度為2的結(jié)點數(shù)為n2，則n0=n2+1。 證明：設(shè)二叉樹中度為1的結(jié)點數(shù)為n1，二叉樹中總的結(jié)點數(shù)為n，則有 n=n0+n1+n2 再考慮孩子結(jié)點，除根結(jié)點之外的結(jié)點都是一個結(jié)點的孩子，二叉樹中孩子結(jié)點總數(shù)為n-1；而度為1的結(jié)點有一個孩子，度為2的結(jié)點有兩個孩子，因此二叉樹中孩子結(jié)點的總數(shù)又為n1+2n2，即 n-1=n1+2n2 聯(lián)立以上二等式可得n0=n2+1，原命題得證。,二叉樹的特殊形態(tài)滿二叉樹,滿二叉樹（full binary tree）是指深度為k且有2k-1個結(jié)點的二叉樹。 下圖給出了深度為3的滿二叉樹。顯然，滿二叉樹的每層含有結(jié)點數(shù)為最大值，不存在度為1的結(jié)點，除葉子結(jié)點外每個結(jié)點都有左右孩子，且葉子結(jié)點全部在第k層上。,二叉樹的特殊形態(tài)完全二叉樹,完全二叉樹（complete binary tree）是指深度為k的、有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)它的每一個結(jié)點都與深度為k的滿二叉樹中編號從1到n的結(jié)點一一對應(yīng)。下圖給出了一棵深度為3的完全二叉樹示例。 顯然，完全二叉樹中前k-1層含有結(jié)點數(shù)為最大值，第k層不一定滿但全部集中在左邊而空缺留在右邊，葉子結(jié)點只可能在第k層和第k-1層上出現(xiàn)。 顯而易見，滿二叉樹是完全二叉樹的特殊情況，滿二叉樹一定是完全二叉樹，反之不然。,二叉樹的性質(zhì)（續(xù)）,性質(zhì)4 具有n 個結(jié)點的完全二叉樹的深度為 。 證明：設(shè)該完全二叉樹的深度為k，由完全二叉樹的定義及性質(zhì)2有2k-1-1n2k-1，即有 2k-1n2k 同時取對數(shù)后有 k-1log2nk 因為k為整數(shù)，故有 ，即 。,二叉樹的性質(zhì)（續(xù)）,性質(zhì)5 對于具有n個結(jié)點的完全二叉樹，如果按照自上而下自左至右的順序?qū)λ薪Y(jié)點從1到n編號，則對于任意的序號為i的結(jié)點有： 如果i=1，則結(jié)點i是根結(jié)點，無雙親；如果i1，則結(jié)點i的雙親結(jié)點編號為 。 如果2in，則結(jié)點i的左孩子編號為2i；否則無左孩子。 如果2i+1n，則結(jié)點i的右孩子編號為2i+1；否則無右孩子。 如果i為奇數(shù)且不為1，則結(jié)點i的左兄弟編號為i-1；否則無左兄弟。 如果i為偶數(shù)且小于n，則結(jié)點i的右兄弟編號為i+1；否則無右兄弟。,4.2 二叉樹,4.2.1 二叉樹的概念 4.2.2 二叉樹的性質(zhì) 4.2.3 二叉樹的存儲結(jié)構(gòu) 4.2.4 二叉樹的簡單運算實現(xiàn),順序存儲結(jié)構(gòu),二叉樹的順序存儲是用一組連續(xù)的存儲單元存儲二叉樹中的數(shù)據(jù)元素。 一般是按從根結(jié)點開始自上而下自左至右的順序來存儲，然而按這種方法存儲后結(jié)點在物理上的鄰接關(guān)系一般不能反映出它們在邏輯上的前趨和后繼關(guān)系。 只有通過某種方法能夠確定出結(jié)點之間的邏輯關(guān)系，這種存儲方法才有意義。,順序存儲結(jié)構(gòu)（續(xù)）,由二叉樹的性質(zhì)5我們知道，完全二叉樹以及它的特殊形態(tài)滿二叉樹中的結(jié)點，可以由結(jié)點的序號惟一確定結(jié)點之間的邏輯關(guān)系，如雙親、左孩子、右孩子、左兄弟、右兄弟等關(guān)系； 所以可以采用一維數(shù)組a1n按結(jié)點編號依次存儲完全二叉樹中各結(jié)點，這樣既可用一維數(shù)組的下標(biāo)確定結(jié)點位置和結(jié)點之間的關(guān)系，又可節(jié)省存儲空間。,完全二叉樹的順序存儲結(jié)構(gòu)示意圖,其中：a2的雙親是a1，左孩子是a4，右孩子是a5，無左兄弟其右兄弟是a3。,一般二叉樹的順序存儲結(jié)構(gòu),對于一般的二叉樹，如果仍按順序存儲依次存放各結(jié)點于數(shù)組中，通過數(shù)組下標(biāo)不能反映出結(jié)點之間的邏輯關(guān)系；只有通過添加一些并不存在的空結(jié)點，使之成為完全二叉樹形式才行。 顯然，會造成許多存儲空間的浪費，最壞情況下是單右枝樹，一棵深度為k的單右枝樹，只有k個結(jié)點卻需分配2k-1個存儲單元。 所以，不宜用順序存儲結(jié)構(gòu)存儲一般的二叉樹。,一般二叉樹的順序存儲結(jié)構(gòu)示意圖,單右枝二叉樹順序存儲結(jié)構(gòu)示意圖,鏈?zhǔn)酱鎯Y(jié)構(gòu),二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用鏈表來存儲二叉樹，用鏈指針來指示元素間的邏輯關(guān)系。 常用的鏈?zhǔn)酱鎯Ψ椒ㄓ须p鏈法和三鏈法兩種。 所謂雙鏈法即二叉鏈表表示法，它為每一個結(jié)點設(shè)置兩個指針域，分別指向該結(jié)點的左子樹和右子樹；當(dāng)無左子樹或右子樹時，其指針域值為NULL（或）。其結(jié)點結(jié)構(gòu)如下： 其中：data域存放結(jié)點的數(shù)據(jù)信息，lchild域存放指向左孩子的指針，rchild域存放指向右孩子的指針。,二叉樹的二叉鏈表表示示意圖,二叉鏈表的類型定義,顯然，二叉鏈表表示法是存儲二叉樹的最自然的方法，對于要經(jīng)常做插入或刪除運算的二叉樹尤為合適。 二叉鏈表表示法的類型定義為 typedef struct btnode elemtype data; /*數(shù)據(jù)域*/ struct btnode *lchild,*rchild; /*左、右孩子域*/ bitnode; typedef bitnode *bitree; 二叉鏈表表示法便于從根往下查找，即便于查找孩子或子孫。,二叉樹的三叉鏈表表示,若需要頻繁查找雙親或祖先，二叉鏈表就不太方便，需要由根結(jié)點開始向下查找，其效率較低。 解決這一類問題的辦法是采用三鏈法，即三叉鏈表表示法，增加一個指針域用來指向雙親結(jié)點。其結(jié)點結(jié)構(gòu)如下： 其中：parent是存放指向雙親結(jié)點的指針域。 三叉鏈表表示法既便于查找孩子結(jié)點，又便于查找雙親結(jié)點，這種方便是以增加存儲開銷為代價的。,二叉樹的三叉鏈表表示示意圖,4.2 二叉樹,4.2.1 二叉樹的概念 4.2.2 二叉樹的性質(zhì) 4.2.3 二叉樹的存儲結(jié)構(gòu) 4.2.4 二叉樹的簡單運算實現(xiàn),二叉樹的基本運算實現(xiàn),二叉樹基本運算的實現(xiàn)算法，依賴于具體的存儲結(jié)構(gòu)；采用不同的存儲結(jié)構(gòu)，二叉樹的基本運算實現(xiàn)的算法是不同的。這里我們討論的運算實現(xiàn)算法，是以二叉鏈表為存儲結(jié)構(gòu)的。 求二叉樹中結(jié)點x的雙親、左孩子、右孩子以及查找結(jié)點x的運算，都涉及要按照某種次序遍歷二叉樹中所有結(jié)點，在遍歷的過程中完成的運算和操作；由于二叉樹的遍歷運算在下一節(jié)我們專門討論，所以這些運算我們穿插安排在下一節(jié)討論。 只討論簡化了的問題，即把一個結(jié)點插入到二叉樹中作為左右孩子或刪除二叉樹中左右孩子的算法。,1.設(shè)置空二叉樹,設(shè)置空二叉樹setnull(bt) void setnull(bitree bt) /*設(shè)置一棵空二叉樹，即置頭結(jié)點的左右孩子鏈域為空*/ bt-lchild=NULL; /*左鏈域置空*/ bt-rchild=NULL; /*右鏈域置空*/ ,2.求二叉樹的根,求二叉樹的根root(bt) elemtype root(bitree bt) /*該運算返回二叉樹根結(jié)點的值， 當(dāng)二叉樹為空樹時返回NULL*/ if(bt-lchild=NULL) return NULL; else return bt-lchild-data; ,3.建立二叉樹操作,建立二叉樹操作create(x,lbt,rbt) bitree create(elemtype x,bitree lbt,bitree rbt) /*該運算生成一棵以x為根結(jié)點， lbt和rbt分別為左右子樹的二叉樹*/ bitree p; p=(bitree)malloc(sizeof(bitnode); p-data=x; p-lchild=lbt; p-rchild=rbt; return p; /*返回建成的二叉樹*/ ,4.插入左孩子,插入左孩子addlchild(bt,x) void addlchild(bitree bt,elemtype x) /*把元素x插入到二叉樹bt中成為它的左孩子*/ bitree p; p=(bitree)malloc(sizeof(bitnode); p-data=x; p-lchild=NULL; p-rchild=NULL; bt-lchild=p; /*插入bt的左孩子域*/ ,5.刪除左孩子,刪除左孩子dellchild(bt) void dellchild(bitree bt) /*刪除二叉樹bt的左孩子，整個左子樹全部被刪除*/ bitree p; p=bt-lchild; *保存左子樹指針*/ bt-lchild=NULL; free (p); /*釋放左子樹空間*/ ,第4章 樹與二叉樹,4.1 樹的基本概念 4.2 二叉樹 4.3 二叉樹的遍歷 4.4 線索二叉樹 4.5 樹和森林 4.6 哈夫曼樹,4.3 二叉樹的遍歷,4.3.1 遍歷二叉樹的遞歸算法 4.3.2 遍歷二叉村的非遞歸算法 4.3.3 遍歷序列與二叉樹的復(fù)原 4.3.4 基于遍歷的幾種二叉樹運算的 實現(xiàn)和應(yīng)用舉例,二叉樹的遍歷,二叉樹的遍歷是指按照某種次序巡訪二叉樹中的每個結(jié)點，使得每個結(jié)點都被訪問一次且只被訪問一次。遍歷是二叉樹中經(jīng)常要用到的一種操作。在許多實際應(yīng)用問題中，常常需要查找具有某一特征的結(jié)點，或者對二叉樹中每個結(jié)點逐個訪問，在訪問的過程中對某些結(jié)點或全部結(jié)點進行相應(yīng)的處理。 遍歷對于線性結(jié)構(gòu)來說是非常簡單的，只需順序掃描每個數(shù)據(jù)元素一次即可。由于二叉樹是一種非線性結(jié)構(gòu)，每個結(jié)點都有可能有兩棵子樹，這就需要尋找一種規(guī)律，使二叉樹中結(jié)點信息由非線性排列變成為某種意義上的線性排列次序序列。 所以我們可以說，遍歷操作的實質(zhì)就是使非線性結(jié)構(gòu)線性化。,二叉樹的遍歷（續(xù)）,由二叉樹的定義分析二叉樹的結(jié)構(gòu)特征可知，一棵非空的二叉樹是由根結(jié)點（D）、左子樹（L）和右子樹（R）三個基本部分組成的。 只要依次遍歷這三個部分，就可以遍歷整個二叉樹；而對這三個部分的遍歷有六種可能的次序，即DLR、DRL、LDR、RDL、LRD和RLD。 如果限定先左后右則只有三種情況，即DLR、LDR和LRD三種，分別稱為前序遍歷、中序遍歷和后序遍歷。,1.前序遍歷,前序遍歷（preorder traversal） 前序遍歷二叉樹的遞歸定義為：若二叉樹為空樹則遍歷結(jié)束，否則 訪問根結(jié)點； 前序遍歷根結(jié)點的左子樹； 前序遍歷根結(jié)點的右子樹； 例如對下圖的二叉樹，前序遍歷得到的結(jié)點序列為ABDFCEG。,前序遍歷的遞歸算法描述,void preorder(bitree bt) if(bt=NULL) return ; /*遞歸結(jié)束條件*/ else printf(“%dt”,bt-data); preorder(bt-lchild); /*前序遍歷左子樹*/ preorder(bt-rchild); /*前序遍歷右子樹*/ ,2.中序遍歷,中序遍歷（inorder traversal） 中序遍歷二叉樹的遞歸定義為：若二叉樹為空樹則遍歷結(jié)束，否則 中序遍歷根結(jié)點的左子樹； 訪問根結(jié)點； 中序遍歷根結(jié)點的右子樹； 例如對下圖的二叉樹，中序遍歷得到的結(jié)點序列為BFDAEGC。,中序遍歷的遞歸算法描述,void inorder(bitree bt) if(bt=NULL) return ; /*遞歸結(jié)束條件*/ else inorder(bt-lchild); /*中序遍歷左子樹*/ printf(“%dt”,bt-data); /*訪問根結(jié)點*/ inorder(bt-rchild); /*中序遍歷右子樹*/ ,3.后序遍歷,后序遍歷（postorder traversal） 后序遍歷二叉樹的遞歸定義為：若二叉樹為空樹則遍歷結(jié)束，否則 后序遍歷根結(jié)點的左子樹； 后序遍歷根結(jié)點的右子樹； 訪問根結(jié)點； 例如對下圖的二叉樹，后序遍歷得到的結(jié)點序列為FDBGECA。,后序遍歷的遞歸算法描述,void postorder(bitree bt) if(bt=NULL) return ; /*遞歸結(jié)束條件*/ else postorder(bt-lchild); /*后序遍歷左子樹*/ postorder(bt-rchild); /*后序遍歷右子樹*/ printf(“%dt”,bt-data); /*訪問根結(jié)點*/ ,二叉樹的遍歷（續(xù)）,二叉樹的前序、中序和后序三種次序遍歷，都是從根結(jié)點開始的，并且在遍歷過程中所經(jīng)過的結(jié)點路線也是相同的，僅僅只是訪問的時機不同而已。 如左下圖所示的二叉樹，其三種遍歷的巡訪路線和訪問時機可示意如右下圖所示。,二叉樹的遍歷舉例,4.3 二叉樹的遍歷,4.3.1 遍歷二叉樹的遞歸算法 4.3.2 遍歷二叉村的非遞歸算法 4.3.3 遍歷序列與二叉樹的復(fù)原 4.3.4 基于遍歷的幾種二叉樹運算的 實現(xiàn)和應(yīng)用舉例,遍歷二叉樹的非遞歸算法,遞歸算法簡潔精練、可讀性好、易理解，但其執(zhí)行效率較低；另外，并非所有程序設(shè)計語言都提供遞歸的功能設(shè)施。所以，我們有必要討論遍歷二叉樹的非遞歸算法。 我們注意觀察前面給出的三種次序的巡訪路線，它是從根結(jié)點開始沿左子樹深入直到最左下端時，返回進入剛剛遇到結(jié)點的右子樹； 在右子樹中，也是先深入到它的最左下結(jié)點時返回剛遇到結(jié)點的右子樹，如此深入和返回，直到從根結(jié)點的右子樹返回到根結(jié)點時止。 在這一過程中，返回結(jié)點的順序恰與深入結(jié)點的順序相反，先深入的后返回，正好符合棧的特點。 所以我們可以用棧來保存遍歷過程中的結(jié)點信息來實現(xiàn)遍歷二叉樹的非遞歸算法，并且假定?？臻g足夠大不會發(fā)生棧上溢以簡化算法。,1.前序遍歷二叉樹的非遞歸算法,前序遍歷二叉樹的非遞歸算法思想是：從二叉樹的根結(jié)點開始，沿左子樹一直深入到最左下結(jié)點時止，在深入的過程中訪問所遇到的結(jié)點，并把所遇到結(jié)點的非空右孩子進棧；當(dāng)左子樹結(jié)點全部處理完之后，從棧頂退出當(dāng)前最近訪問過結(jié)點的右孩子，再按上述過程遍歷該結(jié)點的右子樹；如此重復(fù)，直到棧空時為止。 在下面的算法中，二叉樹以二叉鏈表存儲，用一維數(shù)組stackMAXSIZE作為棧來保存結(jié)點的右孩子信息，top為棧頂指針，p始終指向巡訪過程中當(dāng)前要處理的結(jié)點。,前序遍歷的非遞歸算法描述,#define MAXSIZE 100 void nrpreorder(bitree bt) bitree stackMAXSIZE,p; int top=0; p=bt; do while(p!=NULL) printf(“%dt”,p-data); if(p-rchild!=NULL) /*如果右子樹不空*/ stack+top=p-rchild; /*右孩子進棧*/ p=p-lchild; if(top0) p=stacktop-; while(top0); /*當(dāng)棧不空時繼續(xù)遍歷*/ ,2.中序遍歷二叉樹的非遞歸算法,中序遍歷二叉樹的非遞歸算法，其基本思想與前序遍歷類同，只是沿左子樹向下搜索的過程中先將所遇結(jié)點進棧，待遍歷完左子樹返回時從棧頂退出結(jié)點并訪問，然后再遍歷右子樹。,中序遍歷的非遞歸算法描述,#define MAXSIZE 100 void nrinorder(bitree bt) bitree stackMAXSIZE,p; int top=0; p=bt; do while(p!=NULL) stack+top=p; /*所遇結(jié)點進棧*/ p=p-lchild; /*繼續(xù)搜索p的左子樹*/ if(top0) p=stacktop-; /*出棧一個結(jié)點*/ printf(“%dt”,p-data); /*訪問結(jié)點*/ p=p-rchild; /*繼續(xù)搜索右子樹*/ while(top0); ,3.后序遍歷二叉樹的非遞歸算法,后序遍歷二叉樹的非遞歸算法要比前序和中序遍歷稍復(fù)雜些。 在后序遍歷中，當(dāng)搜索指針指向一個結(jié)點時不能馬上訪問，需要先遍歷左子樹，所以結(jié)點需要進棧保存； 當(dāng)遍歷完左子樹返回再次搜索到該結(jié)點時還不能進行訪問，還需要遍歷其右子樹，所以結(jié)點需要再次進棧保存；即一個結(jié)點在兩次進棧兩次出棧之后才能訪問。,后序遍歷二叉樹的非遞歸算法續(xù),為了區(qū)別某一結(jié)點指針的兩次出棧，需設(shè)置一標(biāo)志flag同結(jié)點同時進出棧，flag定義如下： 棧中數(shù)據(jù)類型可定義為指向結(jié)點的指針和flag組成的結(jié)構(gòu)體類型： typedef struct stackelem bitree link; int flag; stackelemtype;,后序遍歷的非遞歸算法描述,#define MAXSIZE 100 void nrpostorder(bitree bt) stackelemtype stackMAXSIZE; /*定義棧*/ bitree p; int top=0,sign; p=bt; /*巡訪指針指向二叉樹的根結(jié)點*/ do while(p!=NULL) stack+top.link=p; /*結(jié)點第一次入棧*/ stacktop.flag=0; /*置標(biāo)志為0*/ p=p-lchild; /*遍歷左子樹準(zhǔn)備*/ ,后序遍歷的非遞歸算法描述續(xù),if(top0) sign=stacktop.flag; /*標(biāo)志出棧存于sign*/ p=stacktop-.link; if(sign=0) /*flag為0，是第一次出棧*/ stack+top.link=p; stacktop.flag=1; /*置標(biāo)志為1*/ p=p-rchild; else /*flag為1，是第二次出棧*/ printf(“%dt”,p-data); p=NULL; while(top0); ,4.二叉樹的層次遍歷,所謂層次遍歷（levelorder traversal）是指從二叉樹的根結(jié)點開始從上到下逐層遍歷該二叉樹，在同一層次中從左到右依次訪問各個結(jié)點。例如對右圖的二叉樹，按層次遍歷得到的結(jié)點序列為ABCDEFG。,由層次遍歷的定義可知，層次遍歷是從根結(jié)點開始訪問，然后訪問它的左孩子和右孩子，接下來是它左孩子的左孩子和右孩子，右孩子的左孩子和右孩子，。即在訪問完某個結(jié)點后，一般不能馬上訪問它的左孩子和右孩子（除根結(jié)點等特殊情況外），需要把它的左右孩子信息保存起來。,二叉樹的層次遍歷（續(xù)）,這種方式正好與隊列的操作特點吻合，所以可利用一個隊列結(jié)構(gòu)來實現(xiàn)層次遍歷，其做法是： (1) 首先將根結(jié)點入隊列； (2) 當(dāng)隊列不空，從隊列中取出隊頭結(jié)點訪問它，并在其左右孩子非空時，把它的左孩子和右孩子結(jié)點依次入隊列； (3) 反復(fù)執(zhí)行(2)，直到隊列為空時止。 在下面的層次遍歷算法中，二叉樹以二叉鏈表存儲，用一維數(shù)組queueMAXSIZE實現(xiàn)循環(huán)隊列，變量front和rear為分別表示隊頭指針和隊尾指針的指示器變量，并假定隊列有足夠空間不會發(fā)生上溢。,二叉樹的層次遍歷算法描述,#define MAXSIZE 100 void levelorder(bitree bt) bitree queueMAXSIZE; int front,rear; if(bt=NULL) return; front=0; rear=0; queue+rear=bt; /*根結(jié)點入隊列*/ while(front!=rear) front=(front+1)%MAXSIZE; printf(“%dt”,queuefront-data);,二叉樹的層次遍歷算法描述續(xù),if(queuefront-lchild!=NULL) rear=(rear+1)%MAXSIZE; /*修改隊尾指針*/ queuerear=queuefront-lchild; if(queuefront-rchild!=NULL) rear=(rear+1)%MAXSIZE; queuerear=queuefront-rchild; ,4.3 二叉樹的遍歷,4.3.1 遍歷二叉樹的遞歸算法 4.3.2 遍歷二叉村的非遞歸算法 4.3.3 遍歷序列與二叉樹的復(fù)原 4.3.4 基于遍歷的幾種二叉樹運算的 實現(xiàn)和應(yīng)用舉例,二叉樹的復(fù)原,由前面的討論可知，任意一棵二叉樹中結(jié)點的前序、中序、后序和層次遍歷次序都是惟一的。 反過來講，由一種遍歷次序能否惟一確定一棵二叉樹呢？回答是否定的。 然而，我們可以由兩種遍歷次序惟一確定一棵二叉樹，這就是二叉樹的復(fù)原問題。,1.利用前序序列和中序序列恢復(fù)二叉樹,二叉樹的前序遍歷是先訪問根結(jié)點，再按前序遍歷方式遍歷根結(jié)點的左子樹和右子樹，即由前序序列可以確定二叉樹的根結(jié)點。 另一方面，中序遍歷是先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹；根結(jié)點在中序序列中必然將結(jié)點分割成為兩個子序列，根結(jié)點前的子序列是其左子樹的中序序列，而根結(jié)點后的子序列是其右子樹的中序序列。,利用前序序列和中序序列恢復(fù)二叉樹續(xù),現(xiàn)在可以根據(jù)這兩個子序列在前序序列中找到對應(yīng)的左子序列和右子序列，兩個子序列在前序中的第一個結(jié)點分別是根結(jié)點的左孩子和右孩子結(jié)點，即左子樹和右子樹的根結(jié)點；此時左右子樹的根結(jié)點又分別把左右子序列各劃分成兩個子序列。 如此一直做下去，由前序序列確定各級子樹的根結(jié)點，由中序序列確定隸屬于各級子樹的左右子樹中的結(jié)點，當(dāng)取盡前序序列中的所有結(jié)點時，各級子樹中的左右孩子都惟一確定了，二叉樹也就恢復(fù)了；而且這種恢復(fù)是惟一的。,利用前序、中序序列恢復(fù)二叉樹舉例,已知一棵二叉樹的前序序列為ABDCEFG，中序序列為DBAFEGC，其二叉樹的恢復(fù)過程是： 先由前序序列知A為根結(jié)點，由中序序列知DB為左子樹而FEGC為右子樹，如下圖(a)； 其次由前序序列確定左右子樹的根結(jié)點為B和C，由中序序列知D為B的左孩子B無右孩子，F(xiàn)EG為C的左子樹C無右子樹，如上圖(b)；,利用前序、中序序列恢復(fù)二叉樹舉例續(xù),現(xiàn)在由前序序列確定C的左子樹的根結(jié)點為E，由中序序列知F為E的左孩子而G為E的右孩子，這樣就得到了最終恢復(fù)的二叉樹，如下圖(c)。,2.利用后序序列和中序序列恢復(fù)二叉樹,同利用前序序列和中序序列恢復(fù)二叉樹的道理一樣，利用后序序列和中序序列也可以惟一確定一棵二叉樹。 在恢復(fù)二叉樹的過程中，后序序列的作用如同前面的前序序列一樣是確定各級子樹的根結(jié)點；無非是前序序列中第一個結(jié)點為根結(jié)點而后序序列中最后一個結(jié)點為根結(jié)點。 中序序列的作用仍然是確定隸屬于各級子樹的左右子樹中的結(jié)點，當(dāng)各級子樹中的左右孩子都惟一確定時，二叉樹就完全恢復(fù)了。,利用后序、中序序列恢復(fù)二叉樹舉例,對于后序序列DBFGECA和中序序列BDAFEGC，可以這樣恢復(fù)二叉樹： 首先由后序序列知A為根結(jié)點，由中序序列知BD和FEGC分別為左右子樹，如下圖(a)； 其次由后序序列知B和C為左右子樹的根結(jié)點，由中序序列知D為B的右孩子B無左孩子，F(xiàn)EG為C的左子樹C無右子樹，如上圖(b)；,利用后序、中序序列恢復(fù)二叉樹舉例續(xù),現(xiàn)在由后序序列確定C的左子樹的根結(jié)點是E，由中序序列知F為E的左孩子而G為E的右孩子，最后得到的二叉樹，如下圖(c)。,3.利用層次序列和中序序列恢復(fù)二叉樹,利用層次序列和中序序列也可以惟一確定（或恢復(fù)）一棵二叉樹。 層次遍歷是從上到下處于不同層次的各級子樹根結(jié)點的前后順序排列，在同層中是從左到右依次順序排列的。 先由層次序列知其第一個結(jié)點為二叉樹的根結(jié)點，由中序序列區(qū)分隸屬于左右子樹中的結(jié)點序列；這樣的過程一直進行下去，直到其每一級子樹的孩子結(jié)點都惟一確定，二叉樹就恢復(fù)了。,利用層次、中序序列恢復(fù)二叉樹舉例,設(shè)有層次序列ABCDEFGH和中序序列BDAFEHGC，恢復(fù)過程： 由層次序列知根結(jié)點為A，由中序序列知其左子樹為BD而右子樹為FEHGC，如下圖(a)； 再由層次序列知B為A的左孩子而C為A的右孩子，由中序序列知D為B的右孩子而B無左孩子，F(xiàn)EHG為C的左子樹而C無右子樹，如下圖(b)；,利用層次、中序序列恢復(fù)二叉樹舉例續(xù),現(xiàn)在由層次序列可知FEG的根為E即E為C的左孩子，由中序序列知F是E的左孩子而HG是E的右子樹，如下圖(c)； 最后由層次序列知G是HG的根結(jié)點即G是E的右孩子，由中序序列知H是G的左孩子，即為所求的二叉樹，如下圖(d)。,二叉樹的復(fù)原（續(xù)）,在上面討論的二叉樹的恢復(fù)過程中，中序序列所起作用是很重要的，只有利用中序序列才能區(qū)分各級子樹中隸屬于左右子樹中的各結(jié)點，而前序序列、后序序列或?qū)哟涡蛄械淖饔脙H在于確定各級子樹的根結(jié)點。 所以，利用前序、后序和層次序列中的任何兩種序列或三種序列全用都不能惟一確定（或恢復(fù)）一棵二叉樹，這是因為只知根結(jié)點而無法區(qū)分左右子樹之緣故。,4.3 二叉樹的遍歷,4.3.1 遍歷二叉樹的遞歸算法 4.3.2 遍歷二叉村的非遞歸算法 4.3.3 遍歷序列與二叉樹的復(fù)原 4.3.4 基于遍歷的幾種二叉樹運算的 實現(xiàn)和應(yīng)用舉例,1.查找結(jié)點x的運算,查找二叉樹bt中的結(jié)點x，可以結(jié)合在四種遍歷算法中的任何一個算法中進行。在此我們以前序遍歷來實現(xiàn)查找運算的遞歸算法。 bitree search(bitree bt,elemtype x) if(bt!=NULL) if(bt-data=x) return bt; search(bt-lchild,x); /*在左子樹中查找*/ search(bt-rchild,x); /*在右子樹中查找*/ else return NULL; ,2.求二叉樹中的葉子結(jié)點數(shù)目,二叉樹中葉子結(jié)點即終端結(jié)點，它的度為0或者說左子樹和右子樹均為空?？梢岳萌我环N遍歷方法，在遍歷過程中對所遇結(jié)點判斷是否為葉子結(jié)點，若是則統(tǒng)計變量加1，直到遍歷完所有結(jié)點，葉子結(jié)點總數(shù)即可求得。下面給出利用中序遍歷求葉子結(jié)點數(shù)的遞歸算法： int countleaf(bitree bt) int num=0; if(bt!=NULL) if(bt-lchild=NULL),3.求二叉樹的高度,二叉樹的高度或深度為二叉樹中結(jié)點層次的最大值，由處于第一層的根結(jié)點開始遞推即可求得。可以在二叉樹的前序或后序遍歷過程中求出，下面給出的算法是在后序遍歷過程中求深度的遞歸算法。 int treedepth(bitree bt) int h,lh,rh; if(bt=NULL) h=0; else lh=treedepth(bt-lchild); /*左子樹高度賦lh*/ rh=treedepth(bt-rchild); /*右子樹高度賦rh*/ if(lh=rh) h=lh+1; else h=rh+1; return h; ,第4章 樹與二叉樹,4.1 樹的基本概念 4.2 二叉樹 4.3 二叉樹的遍歷 4.4 線索二叉樹 4.5 樹和森林 4.6 哈夫曼樹,4.4 線索二叉樹,4.4.1 線索二叉樹的概念 4.4.2 線索二叉樹的構(gòu)造算法 4.4.3 線索二叉樹上的運算實現(xiàn),線索二叉樹的概念,遍歷二叉樹是以一定規(guī)則將二叉樹中的結(jié)點排成一個線性序列，得到二叉樹中結(jié)點的某個次序序列，如前序序列、中序序列、后序序列或?qū)哟涡蛄校?這種對非線性結(jié)構(gòu)線性化的結(jié)果，使得除端點外的每個結(jié)點在這個線性序列中有且僅有一個前趨和一個后繼。 然而，用二叉鏈表作為存儲結(jié)構(gòu)時每個結(jié)點中只有指向其左右孩子的指針，從任意一個結(jié)點出發(fā)可以直接找到它的左右孩子，但一般不能直接找到在某一次序序列中的前趨和后繼結(jié)點。,線索二叉樹的概念（續(xù)）,如果在結(jié)點中增加指向其前趨和后繼的指針，將降低存儲空間的使用效率（密度）。 大家知道，n個結(jié)點的二叉鏈表中必有n+1個空指針，因此可以利用這些空指針域存放某一遍歷次序序列之下的前趨和后繼指針信息。 把這種附加的指向其前趨和后繼的指針稱之為線索（thread），加上了線索的二叉鏈表稱之為線索鏈表（thread linked list），相應(yīng)的二叉樹稱之為線索二叉樹（thread binary tree）。,線索二叉樹的概念（續(xù)）,在線索鏈表中規(guī)定： 若結(jié)點有左子樹則lchild域指向其左孩子，否則指向其遍歷序列的前趨； 若結(jié)點有右子樹則rchild域指向其右孩子，否則指向其遍歷序列的后繼。 為了區(qū)別結(jié)點的鏈域是指向其左右孩子的指針還是指向其前趨或后繼的線索，需要在每個結(jié)點中增加兩個線索標(biāo)志ltag和rtag，這兩個線索標(biāo)志不需要額外的存儲開銷，只需利用指針域的第一位（即符號位）便可實現(xiàn)。,線索二叉樹的類型定義,typedef enum0, 1ptrtag; typedef struct bithnode elemtype data; struct bithnode *lchild,*rchild; ptrtag ltag,rtag; bithrnode; typedef bithrnode *bithrtree; 其中：,線索二叉樹舉例,下圖是一棵二叉樹的中序線索二叉樹和相應(yīng)的中序線索鏈表，圖中的實線為指針而虛線為線索。在線索鏈表中增加了頭結(jié)點，其左鏈域lchild指向二叉樹的根結(jié)點，右鏈域rchild指向中序遍歷時的最后一個結(jié)點。,4.4 線索二叉樹,4.4.1 線索二叉樹的概念 4.4.2 線索二叉樹的構(gòu)造算法 4.4.3 線索二叉樹上的運算實現(xiàn),線索二叉樹的構(gòu)造算法,建立線索二叉樹的過程稱作對二叉樹線索化，線索化需要在遍歷的過程中來實現(xiàn)。 在對二叉樹的某種次序遍歷過程中，一邊遍歷一邊建立線索， 若當(dāng)前訪問結(jié)點的左孩子域為空則建立前趨線索， 若右孩子域為空則建立后繼線索。 為實現(xiàn)這一過程，可設(shè)指針pre指向剛剛訪問過的結(jié)點，指針p指向當(dāng)前結(jié)點，就可以方便前趨和后繼線索的填入。,線索二叉樹的構(gòu)造算法（續(xù)）,下面給出的是中序線索二叉樹線索化的遞歸算法， 其中：函數(shù)inorderthr處理頭結(jié)點以及與頭結(jié)點有關(guān)的指針和線索，包括對于空二叉樹的特殊處理；并調(diào)用函數(shù)inthreading對非空二叉樹進行中序線索化。 算法的描述如下： bithrtree inorderthr(bithrtree t) bithrtree thrt; thrt=(bithrtree)malloc(sizeof(bithrnode); thrt-ltag=0; thrt-rtag=1;,線索二叉樹的構(gòu)造算法（續(xù)）,if(t=NULL) thrt-lchild=thrt; thrt-rchild=thrt; else thrt-lchild=t; pre=thrt; inthreading(t); pre-rchild=thrt; pre-rtag=1; thrt-rchild=pre; return thrt; ,線索二叉樹的構(gòu)造算法（續(xù)）,void inthreading(bithrtree t) /*在中序遍歷過程中線索化二叉樹t*/ if(t!=NULL) inthreading(t-lchild); /*左子樹線索化*/ if(t-lchild=NULL) t-ltag=1; t-lchild=pre; if(pre-rchild=NULL) pre-rtag=1; pre-rchild=p; pre=p; inthreading(t-rchild); /*右子樹線索化*/ ,4.4 線索二叉樹,4.4.1 線索二叉樹的概念 4.4.2 線索二叉樹的構(gòu)造算法 4.4.3 線索二叉樹上的運算實現(xiàn),1. 遍歷中序線索二叉樹,遍歷線索二叉樹，只要從頭結(jié)點出發(fā)反復(fù)找結(jié)點的后繼，直到又回到頭結(jié)點時止。 查找一個結(jié)點的后繼有兩種情況： 如果結(jié)點的右線索標(biāo)志rtag=1，右指針?biāo)讣礊橹行蚝罄^。 如果結(jié)點的右線索rtag=0，該結(jié)點有右孩子，由中序遍歷定義知其后繼結(jié)點應(yīng)是它的右子樹上的最左下結(jié)點；即沿著它的右孩子結(jié)點的左指針鏈一直往下找，當(dāng)某結(jié)點左線索標(biāo)志為1時，該結(jié)點就是要找的最左下結(jié)點。,最左下結(jié)點示意圖,遍歷中序線索二叉樹算法描述,void inorderthr(bithrtree t) bithrtree p; p=t-lchild; while(p!=t) /*空樹或遍歷結(jié)束時p=t*/ while(p-ltag=0) p=p-lchild; /*找最左下結(jié)點*/ printf(“%dt”,p-data); while(p-rtag=1) ,2. 中序線索二叉樹的逆中序遍歷,所謂逆中序遍歷，是指先逆中序遍歷右子樹，然后訪問根結(jié)點，最后逆中序遍歷左子樹。其遍歷結(jié)果序列與中序序列正好相反，即從中序序列的最后一個結(jié)點到第一個結(jié)點的次序。 實現(xiàn)逆中序遍歷，只要從中序線索樹的頭結(jié)點出發(fā)，由rchild域找到中序的最后一個結(jié)點，然后反復(fù)查找結(jié)點的前趨結(jié)點，直到又回到頭結(jié)點時止。 確定一個結(jié)點的前趨結(jié)點有兩種情況： 如果結(jié)點的左線索標(biāo)志ltag=1，其左指針域lchild所指即為前趨。 如果ltag=0說明結(jié)點有左孩子，根據(jù)中序遍歷的定義其前趨結(jié)點應(yīng)是其左子樹上的最右下結(jié)點；即沿其左孩子的右指針鏈一直向下查找，當(dāng)某結(jié)點的右線索標(biāo)志為1，即rtag=1時，這個結(jié)點就是所要找的最右下結(jié)點。,最右下結(jié)點示意圖,逆中序遍歷線索二叉樹算法描述,void reverseinorder(bithrtree t) bithrtree p; p=t-rchild； /*p指向中序最后一個結(jié)點*/ while(p!=t) printf(“%dt”, p-data)； if(p-ltag=0) /*如果左孩子存在*/ p=p-lchild； while(p-rtag=0) /*找左子樹的最右下結(jié)點*/ p=p-rchild； else p=p-lchild； ,第4章 樹與二叉樹,4.1 樹的基本概念 4.2 二叉樹 4.3 二叉樹的遍歷 4.4 線索二叉樹 4.5 樹和森林 4.6 哈夫曼樹,4.5 樹和森林,4.5.1 樹和森林的存儲結(jié)構(gòu) 4.5.2 樹和森林與二叉樹之間的轉(zhuǎn)換 4.5.3 樹和森林的遍歷 4.5.4 樹的應(yīng)用舉例判定樹,樹和森林的存儲結(jié)構(gòu),森林是由若干棵樹組成的，樹是森林中只有一棵樹時的特殊情形； 只要弄清樹的存儲表示，森林的存儲表示問題就迎刃而解了。 這里，介紹樹的幾種常用存儲表示方法。 雙親表示法 孩子鏈表表示法 孩子兄弟表示法,1. 雙親表示法,在樹中，每個結(jié)點的雙親都是惟一的。利用樹的這一特性，可在存儲結(jié)點信息的同時為每個結(jié)點增加一個指向其雙親的指針parent，就可以惟一地表示任何一棵樹。 這種存儲結(jié)構(gòu)可形式說明如下： typedef struct ptrnode elemtype data; struct ptrnode *parent; ptnode; typedef ptnode *ptree;,樹的雙親表示法示例,在下圖中給出了一棵樹和它的雙親表示法示例。 顯然，雙親表示法便于向雙親方向查找，而不適合于查找孩子。,2. 孩子鏈表表示法,由于樹中每個結(jié)點可能有多棵子樹，所以可以考慮用多重鏈表表示。然而若以樹的度設(shè)置結(jié)點中的指針數(shù)的定長結(jié)點會造成空間的極大浪費，若不定長地設(shè)置結(jié)點又會給運算帶來不便。 為此可考慮為樹中每個結(jié)點的孩子建立一個單鏈表，這樣一棵樹的n個結(jié)點就有n個孩子鏈表，把這n個孩子鏈表的頭結(jié)點組織成一個順序表，頭結(jié)點的數(shù)據(jù)域填寫雙親結(jié)點的值。這種孩子表示法也稱作孩子鏈表表示法。 顯然，該子鏈表表示法便于查找孩子，而不適用于雙親方向的查找。 可以把雙親表示法與孩子鏈表表示法結(jié)合起來形成所謂的雙親孩子表示法，做到既方便查找孩子也方便查找雙親。,樹的孩子鏈表表示法示例,3. 孩子兄弟表示法,在樹的各種存儲結(jié)構(gòu)中，孩子兄弟表示法是最常用的存儲表示方法。此法也稱作二叉鏈表表示法或左孩子右兄弟表示法。它同二叉樹的存儲表示一樣，都是用二叉鏈表作為存儲結(jié)構(gòu)，所不同的是左指針是指向結(jié)點的第一個孩子而右指針指向結(jié)點的下一個兄弟。其結(jié)構(gòu)的形式說明如下： typedef struct cstnode elemtype data; struct cstnode *lchild,*rsibling; csnode; typedef csnode *cstree; 值得注意的是，樹的孩子兄弟表示法所表示出來的二叉鏈表可與一棵二叉樹惟一對應(yīng)，所以可借助二叉鏈表導(dǎo)出樹與二叉樹之間的確定對應(yīng)關(guān)系。,樹的孩子兄弟表示法示例,4.5 樹和森林,4.5.1 樹和森林的存儲結(jié)構(gòu) 4.5.2 樹和森林與二叉樹之間的轉(zhuǎn)換 4.5.3 樹和森林的遍歷 4.5.4 樹的應(yīng)用舉例判定樹,樹和森林與二叉樹之間的轉(zhuǎn)換,從樹的孩子兄弟表示法我們知道，可借助二叉鏈表導(dǎo)出樹與二叉樹之間的確定對應(yīng)關(guān)系。 此外還可以由“樹的孩子兄弟表示法示例”看出，樹所對應(yīng)的二叉樹右子樹必空。 如果把構(gòu)成森林中的各棵樹的根結(jié)點看作兄弟，森林的存儲表示則可用孩子兄弟表示法實現(xiàn)，也就是說一片森林可以借助二叉鏈表與一棵二叉樹惟一對應(yīng)。,1. 森林（或樹）轉(zhuǎn)換為二叉樹,由樹和森林的孩子兄弟表示法可知， 把樹或森林轉(zhuǎn)換為二叉樹： 二叉樹的根結(jié)點是樹或森林中第一棵樹的根結(jié)點； 二叉樹的左孩子為該結(jié)點在樹中的第一個孩子； 二叉樹的右孩子為該結(jié)點的下一個兄弟，按這樣的辦法一直做下去，就會得到樹或森林所對應(yīng)的一棵惟一的二叉樹。,森林（或樹）轉(zhuǎn)換為二叉樹(續(xù)),這種轉(zhuǎn)換辦法的形式化描述（遞歸定義）為： 如果F=T1,T2,Tm是森林，則按如下規(guī)則轉(zhuǎn)換為一棵二叉樹B=root,LB,RB： 若F為空（即m=0），則B為空樹； 若F非空（即m0），則B的根root為森林中第一棵樹的根root(T1)；B的左子樹LB是從T1中根結(jié)點的子樹森林F1=T11,T12,T1n轉(zhuǎn)換而成的二叉樹；其右子樹RB是從森林F=T2,T3,Tm轉(zhuǎn)換而成的二叉樹。,森林（或樹）轉(zhuǎn)換為二叉樹(續(xù)),前面的轉(zhuǎn)換方法是遞歸定義的。下面我們再給出一種直觀做圖轉(zhuǎn)換的方法，這種方法可用一句不太嚴(yán)密的口訣概括為“連兄弟，斷孩子，順時針旋轉(zhuǎn)45”。 口訣的解釋如下： 連兄弟，即把森林中所有的相鄰兄弟之間用一條橫線相連接； 斷孩子，即斷開每個結(jié)點與第二個及以后各個孩子的連線，只保留與第一個孩子間的連線； 順時針旋轉(zhuǎn)45，即以第一棵樹的根結(jié)點為軸心順時針旋轉(zhuǎn)45，使結(jié)構(gòu)層次分明。,一個森林轉(zhuǎn)換為二叉樹的過程,2. 二叉樹轉(zhuǎn)換為森林（或樹）,把二叉樹轉(zhuǎn)換為樹或森林是前述轉(zhuǎn)換的逆過程，可由二叉樹對應(yīng)的二叉鏈表依據(jù)前述孩子兄弟表示法的定義逆推還原成樹或森林。 其形式化轉(zhuǎn)換方法描述為： 如