《算法與數(shù)據(jù)結(jié)構(gòu)》第4章樹與二叉樹ppt.ppt

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