第6章 樹和二叉樹課件

第6章樹和二叉樹樹型結(jié)構(gòu)是一類非常重要的非線性結(jié)構(gòu)，它可以很好地描述客觀世界中廣泛存在的具有分支關(guān)系或?qū)哟翁匦缘膶?duì)象。因此在計(jì)算機(jī)領(lǐng)域里有著廣泛應(yīng)用。如：操作系統(tǒng)中的文件管理編譯程序中的語(yǔ)法結(jié)構(gòu)數(shù)據(jù)庫(kù)系統(tǒng)信息組織形式第6章樹和二叉樹第6章樹和二叉樹祖父父親伯父叔叔堂兄堂弟兄弟我長(zhǎng)子次子孫子孫子第6章樹和二叉樹主要內(nèi)容6.1樹及其抽象數(shù)據(jù)類型6.2二叉樹及其抽象數(shù)據(jù)類型6.3二叉樹的表示和實(shí)現(xiàn)6.4線索二叉樹6.5哈夫曼編碼與哈夫曼樹6.6樹的表示目的：理解樹結(jié)構(gòu)。要求：掌握二叉樹的表示和實(shí)現(xiàn)。重點(diǎn)：二叉樹實(shí)現(xiàn)，哈夫曼樹。難點(diǎn)：哈夫曼樹。第6章樹和二叉樹6.1樹及其抽象數(shù)據(jù)類型6.1.1樹定義6.1.2樹的術(shù)語(yǔ)6.1.3樹的表示法6.1.4樹抽象數(shù)據(jù)類型第6章樹和二叉樹6.1.1樹定義樹（tree）是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。n=0的樹稱為空樹；n＞0的樹T：有且僅有一個(gè)結(jié)點(diǎn)n0，它沒有前驅(qū)結(jié)點(diǎn)，只有后繼結(jié)點(diǎn)。n0稱作樹的根（root）結(jié)點(diǎn)。除結(jié)點(diǎn)外n0

，其余的每一個(gè)結(jié)點(diǎn)都有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)；有零個(gè)或多個(gè)直接后繼結(jié)點(diǎn)。（1）非遞歸定義ABCDEFGHJI第6章樹和二叉樹一顆大樹分成幾個(gè)大的分枝，每個(gè)大分枝再分成幾個(gè)小分枝，小分枝再分成更小的分枝，…

，每個(gè)分枝也都是一顆樹，由此我們可以給出樹的遞歸定義。樹（tree）是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。n=0的樹稱為空樹；n＞0的樹T：有且僅有一個(gè)結(jié)點(diǎn)n0，它沒有前驅(qū)結(jié)點(diǎn)，只有后繼結(jié)點(diǎn)。n0稱作樹的根（root）結(jié)點(diǎn)。除根結(jié)點(diǎn)之外的其他結(jié)點(diǎn)分為m（m≥0）個(gè)互不相交的集合T0，T1，…，Tm-1，其中每個(gè)集合Ti（0≤i＜m）本身又是一棵樹，稱為根的子樹（subtree）。（2）遞歸定義ABCDEFGHJI第6章樹和二叉樹舉例第6章樹和二叉樹6.1.2樹的術(shù)語(yǔ)父母、孩子與兄弟結(jié)點(diǎn)度結(jié)點(diǎn)層次、樹的高度邊、路徑無(wú)序樹、有序樹森林第6章樹和二叉樹1.父母、孩子與兄弟結(jié)點(diǎn)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)稱為父母（parents）結(jié)點(diǎn)。結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)稱為孩子（child）結(jié)點(diǎn)。擁有同一個(gè)父母結(jié)點(diǎn)的多個(gè)結(jié)點(diǎn)之間稱為兄弟（sibling）結(jié)點(diǎn)。結(jié)點(diǎn)的祖先（ancestor）是指從根結(jié)點(diǎn)到其父母結(jié)點(diǎn)所經(jīng)過的所有結(jié)點(diǎn)。結(jié)點(diǎn)的后代（descendant）是指該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，以及孩子的孩子等。祖先與后代的關(guān)系則是對(duì)父子關(guān)系的延伸，其定義了樹中結(jié)點(diǎn)的縱向次序。ABCDEFGHJI第6章樹和二叉樹2.度結(jié)點(diǎn)的度（degree）是指結(jié)點(diǎn)所擁有子樹的棵數(shù)。度為零的結(jié)點(diǎn)稱為葉子（leaf）或者終端結(jié)點(diǎn)

度不為零的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或者非終端結(jié)點(diǎn)、非葉結(jié)點(diǎn)。樹的度是指樹中各結(jié)點(diǎn)度的最大值。ABCDEFGHJI第6章樹和二叉樹3.結(jié)點(diǎn)層次、樹的高度結(jié)點(diǎn)的層次（level）屬性反映結(jié)點(diǎn)處于樹中的層次位置。約定根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次是其父母結(jié)點(diǎn)的層次加1.樹的高度（height）或深度（depth）是樹中結(jié)點(diǎn)的最大層次數(shù)。ABCDEFGHJI第6章樹和二叉樹4.邊、路徑設(shè)樹中X結(jié)點(diǎn)是Y結(jié)點(diǎn)的父母結(jié)點(diǎn)，有序?qū)Γ╔，Y）稱為連接這兩個(gè)結(jié)點(diǎn)的分支，也稱為邊（edge）。設(shè)（X0，X1，…，Xk-1）是由樹中結(jié)點(diǎn)組成的一個(gè)序列，且（Xi，Xi+1）（0≤i＜k-1）都是樹中的邊，則該序列稱為X0到Xk-1的一條路徑（path）。路徑長(zhǎng)度（pathlength）為路徑上的邊數(shù)。ABCDEFGHJI第6章樹和二叉樹5.無(wú)序樹、有序樹若把樹中每個(gè)結(jié)點(diǎn)的各子樹看成從左到右有次序的（即不能互換），則稱該樹為有序樹（OrderedTree）；否則稱為無(wú)序樹（UnorderedTree）如果規(guī)定k1和k2是兄弟，且k1在k2的左邊，則k1的任一子孫都在k2的任一子孫的左邊，則定義了樹中結(jié)點(diǎn)的橫向次序ABCDEFGHJIABCACB第6章樹和二叉樹6.森林森林（Forest）是m（m≥0）棵互不相交樹的集合。給森林加上一個(gè)根結(jié)點(diǎn)就變成一棵樹。將樹的根結(jié)點(diǎn)刪除就變成森林。ABCDEFGHJIBCDEFGHJI樹森林第6章樹和二叉樹6.1.3樹的表示法1、用二元組描述2、用樹型圖表示3、用文氏圖表示4、用凹入圖表示5、用廣義表表示第6章樹和二叉樹1、樹的邏輯結(jié)構(gòu)可以用二元組描述為：

Group=（D，R）有限個(gè)數(shù)據(jù)元素的集合這些數(shù)據(jù)元素間關(guān)系的集合D={A,B,C,D,E,F,G,H,I,J}R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<D,G>,<D,H>,<F,I>,<F,J>}ABCDEFGHJI第6章樹和二叉樹2、用樹型圖表示

3、用文氏圖表示ABCDEFGHJICEGHDBIJFA第6章樹和二叉樹4、用凹入圖表示

5、用廣義表圖表示ABEFIJCDGHA（B（E，F(xiàn)（I，J）），C，D（G，H））ABCDEFGHJI第6章樹和二叉樹6.1.4樹抽象數(shù)據(jù)類型(TTree.java)publicinterfaceTTree<E>{//樹接口

booleanisEmpty();//判斷是否空樹

EgetRoot(); //返回根結(jié)點(diǎn)元素

EgetParent(Echild);//返回child的父母結(jié)點(diǎn)

intgetChildCount(Eparent);//返回parent孩子結(jié)點(diǎn)數(shù)

EgetFirstChild(Eparent);//返回parent的孩子結(jié)點(diǎn)

EgetNextSibling(Eelement);//返回下一個(gè)兄弟結(jié)點(diǎn)

voidtraverse();//遍歷樹

voidinsert(Eparent,Eelement);//插入作為parent的孩子

voidremove(Eparent);//刪除以parent為根的子樹

voidclear();//清空}第6章樹和二叉樹6.2二叉樹及其抽象數(shù)據(jù)類型6.2.1二叉樹定義6.2.2二叉樹性質(zhì)6.2.3二叉樹抽象數(shù)據(jù)類型許多實(shí)際問題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹的形式。即使是一般的樹也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹，而且二叉樹的存儲(chǔ)結(jié)構(gòu)及其算法相比于樹來(lái)說(shuō)較為簡(jiǎn)單。因此將重點(diǎn)討論二叉樹的性質(zhì)、存儲(chǔ)以及常用的算法。第6章樹和二叉樹6.2.1二叉樹定義二叉樹（binarytree）是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合，此集合或者為空，或者由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左、右子樹的，互不相交的二叉樹組成。二叉樹可以為空集，因此根可以有空的左子樹或者右子樹，亦或者左、右子樹皆為空。

第6章樹和二叉樹二叉樹有別于度數(shù)為2的有序樹，在二叉樹中允許某些結(jié)點(diǎn)只有右子樹而沒有左子樹；而有序樹中，一個(gè)結(jié)點(diǎn)如果沒有第一子樹就不可能有第二子樹的存在。第6章樹和二叉樹思考畫出3個(gè)結(jié)點(diǎn)的無(wú)序樹和二叉樹的基本形態(tài)。第6章樹和二叉樹6.2.2二叉樹性質(zhì)性質(zhì)1：若根結(jié)點(diǎn)的層次為1，則二叉樹第i層最多有2i

1（i≥1）個(gè)結(jié)點(diǎn)。證明：用數(shù)學(xué)歸納法證明：

歸納基礎(chǔ)：i=1時(shí)，有2i-1=20=1。因?yàn)榈?層上只有一個(gè)根結(jié)點(diǎn)，所以命題成立。

歸納假設(shè)：假設(shè)對(duì)所有的j(1≤j<i)命題成立，即第j層上至多有2j-1個(gè)結(jié)點(diǎn)，證明j=i時(shí)命題亦成立。

歸納步驟：根據(jù)歸納假設(shè)，第i-1層上至多有2i-2個(gè)結(jié)點(diǎn)。由于二叉樹的每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子，故第i層上的結(jié)點(diǎn)數(shù)至多是第i-1層上的最大結(jié)點(diǎn)數(shù)的2倍。即j=i時(shí)，該層上至多有2×2i-2=2i-1個(gè)結(jié)點(diǎn)，故命題成立。

第6章樹和二叉樹性質(zhì)2：在高度為k的二叉樹中，最多有2k

1個(gè)結(jié)點(diǎn)（k≥0）。證明：在具有相同深度的二叉樹中，僅當(dāng)每一層都含有最大結(jié)點(diǎn)數(shù)時(shí)，其樹中結(jié)點(diǎn)數(shù)最多。因此利用性質(zhì)1可得，深度為k的二叉樹的結(jié)點(diǎn)數(shù)至多為：

20+21+…+2k-1=2k-1第6章樹和二叉樹性質(zhì)3：設(shè)一棵二叉樹的葉子結(jié)點(diǎn)數(shù)為n0，2度結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。證明：因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度均不大于2，所以結(jié)點(diǎn)總數(shù)(記為n)應(yīng)等于0度結(jié)點(diǎn)數(shù)、1度結(jié)點(diǎn)和2度結(jié)點(diǎn)數(shù)之和：

n=n0+n1+n2 (式子1)

另一方面，1度結(jié)點(diǎn)有一個(gè)孩子，2度結(jié)點(diǎn)有兩個(gè)孩子，故二叉樹中孩子結(jié)點(diǎn)總數(shù)是：n1+2n2

樹中只有根結(jié)點(diǎn)不是任何結(jié)點(diǎn)的孩子，故二叉樹中的結(jié)點(diǎn)總數(shù)又可表示為：

n=n1+2n2+1 (式子2)

由式子1和式子2得到：

n0=n2+1

ABCEF第6章樹和二叉樹滿二叉樹(FullBinaryTree)

一棵高度為k且有2k-1個(gè)結(jié)點(diǎn)的二又樹稱為滿二叉樹。滿二叉樹的特點(diǎn)：

（1）每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值。即對(duì)給定的高度，它是具有最多結(jié)點(diǎn)數(shù)的二叉樹。

（2）滿二叉樹中不存在度數(shù)為1的結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)均有兩棵高度相同的子樹，且樹葉都在最下一層上。

ABCDEFG第6章樹和二叉樹完全二叉樹(CompleteBinaryTree)

若一棵二叉樹至多只有最下面的兩層上結(jié)點(diǎn)的度可以小于2，并且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。

第6章樹和二叉樹完全二叉樹的特點(diǎn)：（1）滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。（2）在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點(diǎn)后得到的二叉樹就是一棵完全二叉樹。（3）在完全二叉樹中，若某個(gè)結(jié)點(diǎn)沒有左孩子，則它一定沒有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。

第6章樹和二叉樹性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為：

證明：設(shè)所求完全二叉樹的高度為k。由完全二叉樹定義可得：高度為k得完全二叉樹的前k-1層是高度為k-1的滿二叉樹，一共有2k-1-1個(gè)結(jié)點(diǎn)。

由于完全二叉樹深度為k，故第k層上還有若干個(gè)結(jié)點(diǎn)，因此該完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)：n>2k-1-1。

另一方面，由性質(zhì)2可得：n≤2k-1，即：

2k-1-1<n≤2k-1

由此可推出：2k-1≤n<2k，取對(duì)數(shù)后有：

k-1≤log2n<k

又因k-1和k是相鄰的兩個(gè)整數(shù)，故有

k-1=

由此即得：

k=+1第6章樹和二叉樹給二叉樹結(jié)點(diǎn)編號(hào)

在一棵n個(gè)結(jié)點(diǎn)的完全二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有結(jié)點(diǎn)編號(hào)，能得到一個(gè)反映整個(gè)二叉樹結(jié)構(gòu)的線性序列。

ABCDEFG0413265（a）完全二叉樹第6章樹和二叉樹性質(zhì)5：一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹，對(duì)序號(hào)為i（0≤i＜n）的結(jié)點(diǎn)，有：若i=0，則i為根結(jié)點(diǎn)，無(wú)父母結(jié)點(diǎn)；若i>0，則i的父母結(jié)點(diǎn)序號(hào)為:。若2i+1＜n，則i的左孩子結(jié)點(diǎn)序號(hào)為2i+1；否則i無(wú)左孩子。若2i+2＜n，則i的右孩子結(jié)點(diǎn)序號(hào)為2i+2；否則i無(wú)右孩子。第6章樹和二叉樹6.2.3二叉樹抽象數(shù)據(jù)類型(BinaryTTree.java)publicinterfaceBinaryTTree<E>{//二叉樹接口

booleanisEmpty(); //判斷是否空二叉樹

intcount(); //返回二叉樹的結(jié)點(diǎn)個(gè)數(shù)

intheight(); //返回二叉樹的高度

BinaryNode<E>getRoot();//返回二叉樹的根結(jié)點(diǎn)

BinaryNode<E>getParent(BinaryNode<E>node);//返回node父母結(jié)點(diǎn)

voidpreOrder(); //先根次序遍歷二叉樹

voidinOrder(); //中根次序遍歷二叉樹

voidpostOrder(); //后根次序遍歷二叉樹

voidlevelOrder(); //按層次遍歷二叉樹

BinaryNode<E>search(Eelement);//查找并返回元素為element結(jié)點(diǎn)

voidinsert(BinaryNode<E>p,Eelement,booleanleftChild);//插入element元素作為p結(jié)點(diǎn)的左/右孩子

voidremove(BinaryNode<E>p,booleanleftChild);//刪除p的左/右子樹

voidclear(); //清空}第6章樹和二叉樹6.3二叉樹的表示和實(shí)現(xiàn)6.3.1二叉樹的存儲(chǔ)結(jié)構(gòu)6.3.2二叉樹的二叉鏈表實(shí)現(xiàn)6.3.3二叉樹的遍歷6.3.4構(gòu)造二叉樹6.3.5二叉樹的插入和刪除操作6.3.6二叉樹遍歷的非遞歸算法6.3.7二叉樹的層次遍歷第6章樹和二叉樹6.3.1二叉樹的存儲(chǔ)結(jié)構(gòu)1、二叉樹的順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)是把把二叉樹的所有結(jié)點(diǎn)按照一定的線性次序存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中。在二叉樹的順序存儲(chǔ)結(jié)構(gòu)中只存儲(chǔ)結(jié)點(diǎn)的值（數(shù)據(jù)域），結(jié)點(diǎn)在這個(gè)序列中的相互位置決定結(jié)點(diǎn)之間的邏輯關(guān)系。二叉樹順序存儲(chǔ)的原則是：不管給定的二叉樹是不是完全二叉樹，都看作完全二叉樹，即按完全二叉樹的層次次序（從上到下，從左到右）把各結(jié)點(diǎn)依次存入數(shù)組中第6章樹和二叉樹（1）編號(hào)辦法在一棵n個(gè)結(jié)點(diǎn)的完全二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有結(jié)點(diǎn)編號(hào)，能得到一個(gè)反映整個(gè)二叉樹結(jié)構(gòu)的線性序列

ABCDEFG0413265（a）完全二叉樹ABCD0413265（b）一般二叉樹第6章樹和二叉樹

該編號(hào)方案中，由某結(jié)點(diǎn)的編號(hào)可以推出其父親、左兒子、右兒子及兄弟的編號(hào)，假設(shè)給定結(jié)點(diǎn)的編號(hào)為i（0≤i<n），則：（1）若i＝0，則該結(jié)點(diǎn)是為根結(jié)點(diǎn)，無(wú)父親。（2）若i≠0，則該結(jié)點(diǎn)的父親結(jié)點(diǎn)編號(hào)為(i-1)／2的整數(shù)部分。（3）若2i+1<n，則該結(jié)點(diǎn)的左兒子結(jié)點(diǎn)編號(hào)為2i+1，否則該結(jié)點(diǎn)無(wú)左兒子。該結(jié)點(diǎn)必為葉子結(jié)點(diǎn)。（4）若2i+2<n，則該結(jié)點(diǎn)的右兒子結(jié)點(diǎn)編號(hào)為2i+2，否則該結(jié)點(diǎn)無(wú)右兒子。（5）若i為偶數(shù)（不為0），則該結(jié)點(diǎn)的左兄弟為i-1。（6）若i為奇數(shù)（不為n-1），則該結(jié)點(diǎn)的右兄弟為i+1。（2）編號(hào)特點(diǎn)ABCDEFG0413265ABCD0413265第6章樹和二叉樹將二叉樹中所有結(jié)點(diǎn)按編號(hào)順序依次存儲(chǔ)在一個(gè)數(shù)組中。具體實(shí)現(xiàn)

ABCDEFG0413265ABCD0413265ABCDEF012345G6ABC012345D6第6章樹和二叉樹若一個(gè)二叉樹如下所示，試給出其順序存儲(chǔ)。練習(xí)ABCD第6章樹和二叉樹二叉樹順序存儲(chǔ)的優(yōu)點(diǎn)和缺點(diǎn)

對(duì)完全二叉樹而言，順序存儲(chǔ)結(jié)構(gòu)既簡(jiǎn)單又節(jié)省存儲(chǔ)空間。一般的二叉樹采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，雖然簡(jiǎn)單，但易造成存儲(chǔ)空間的浪費(fèi)?！纠孔顗牡那闆r下，一個(gè)高度為k且只有k個(gè)結(jié)點(diǎn)的右單支二叉樹需要2k-1個(gè)存儲(chǔ)單元。在對(duì)順序存儲(chǔ)的二叉樹做插入和刪除結(jié)點(diǎn)操作時(shí)，要大量移動(dòng)結(jié)點(diǎn)。第6章樹和二叉樹2.二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（1）二叉鏈表若一顆具有n個(gè)結(jié)點(diǎn)的二叉樹用二叉鏈表存儲(chǔ)，有多少個(gè)空鏈？第6章樹和二叉樹（2）三叉鏈表第6章樹和二叉樹6.3.2二叉樹的二叉鏈表實(shí)現(xiàn)1、二叉鏈表結(jié)點(diǎn)類（BinaryNode.java）

packagedataStructure.tree;publicclassBinaryNode<E>{publicEdata;publicBinaryNode<E>left,right;\\成員方法}datarightleft第6章樹和二叉樹構(gòu)造方法publicBinaryNode(Edata,BinaryNode<E>left,BinaryNode<E>right){this.data=data;this.left=left;this.right=right;}publicBinaryNode(Edata){this(data,null,null);}publicBinaryNode(){this(null,null,null);}第6章樹和二叉樹

publicbooleanisLeaf(){returnthis.left==null&&this.right==null;}publicStringtoString(){returnthis.data.toString();}第6章樹和二叉樹packagedataStructure.tree;importdataStructure.tree.BinaryNode;publicclassBinaryTree<E>{protectedBinaryNode<E>root;publicBinaryTree(){root=null;}publicBinaryTree(BinaryNode<E>root){this.root=root;}publicbooleanisEmpty(){returnthis.root==null;}publicBinaryNode<E>getRoot(){returnthis.root;} //跟二叉樹相關(guān)的其他操作}2、二叉樹類（BinaryTree.java）AdatarightleftC^G^^E^^BD^^root第6章樹和二叉樹6.3.3二叉樹的遍歷遍歷（traversal）二叉樹就是按照一定規(guī)則和次序訪問二叉樹種的所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅被訪問一次。一次完整的遍歷就是按照某種順序，使得二叉樹中的所有結(jié)點(diǎn)產(chǎn)生一個(gè)線性序列。第6章樹和二叉樹遍歷的種類非空二叉樹根結(jié)點(diǎn)D左子樹L右子樹RP3=63DLR

LDR

LRDDRL

RDL

RLD先左后右先右后左先根遍歷中根遍歷后根遍歷層序遍歷DLR第6章樹和二叉樹1、二叉樹的三種次序遍歷先根次序：訪問根結(jié)點(diǎn)，遍歷左子樹，遍歷右子樹。中根次序：遍歷左子樹，訪問根結(jié)點(diǎn)，遍歷右子樹。后根次序：遍歷左子樹，遍歷右子樹，訪問根結(jié)點(diǎn)。先根遍歷序列：ABDGCEFH中根遍歷序列：DGBAECHF后根遍歷序列：GDBEHFCA第6章樹和二叉樹2、二叉樹三種次序遍歷的遞歸算法若二叉樹為空二叉樹，則算法結(jié)束；否則先訪問根結(jié)點(diǎn)，再先根遍歷左子樹最后先根遍歷右子樹ABDECABCDEroot先根遍歷二叉樹遞歸算法第6章樹和二叉樹實(shí)現(xiàn)publicvoidpreOrder(){System.out.print("\npreOrderis:");preOrder(root);}privatevoidpreOrder(BinaryNode<E>p){if(p!=null){System.out.print(p.data+"");preOrder(p.left);preOrder(p.right);}}ABDECABCDEroot第6章樹和二叉樹中根遍歷二叉樹遞歸算法若二叉樹為空二叉樹，則算法結(jié)束；否則先中根遍歷左子樹再訪問根結(jié)點(diǎn)，最后中根遍歷右子樹DBEACABCDEroot第6章樹和二叉樹實(shí)現(xiàn)publicvoidinOrder(){System.out.print("\ninOrderis:");inOrder(root);}privatevoidinOrder(BinaryNode<E>p){if(p!=null){inOrder(p.left);System.out.print(p.data+"");inOrder(p.right);}}DBEACABCDEroot第6章樹和二叉樹后根遍歷二叉樹遞歸算法若二叉樹為空二叉樹，則算法結(jié)束；否則先后根遍歷左子樹再后根遍歷右子樹最后訪問根結(jié)點(diǎn)，DEBCAABCDEroot第6章樹和二叉樹實(shí)現(xiàn)publicvoidpostOrder(){System.out.print("\npostOrderis:");postOrder(root);}privatevoidpostOrder(BinaryNode<E>p){if(p!=null){postOrder(p.left);postOrder(p.right);System.out.print(p.data+"");}}DEBCAABCDEroot第6章樹和二叉樹P139【例6.1】構(gòu)造并遍歷二叉樹Traverse.java先根遍歷序列：ABDGCEFH中根遍歷序列：DGBAECHF后根遍歷序列：GDBEHFCA第6章樹和二叉樹3、基于遍歷的操作（1）求結(jié)點(diǎn)個(gè)數(shù)

publicintcount(){returncount(root);}publicintcount(BinaryNode<E>p){if(p!=null)return1+count(p.left)+count(p.right);elsereturn0;}DLR第6章樹和二叉樹（2）求高度

publicintdepth(){returndepth(root);}publicintdepth(BinaryNode<E>p){if(p!=null){intld=depth(p.left);intrd=depth(p.right);return(ld>=rd)?ld+1:rd+1;}return0;}DLR第6章樹和二叉樹（3）查找publicBinaryNode<E>search(Evalue){returnsearch(root,value);}publicBinaryNode<E>search(BinaryNode<E>p,Evalue){BinaryNode<E>find=null;if(p!=null&&value!=null){if(p.data.equals(value))find=p;else{find=search(p.left,value);if(find==null)find=search(p.right,value);}}returnfind;}DLR第6章樹和二叉樹（4）獲得父母結(jié)點(diǎn)

publicBinaryNode<E>getParent(BinaryNode<E>node){if(root==null||node==null||node==root)returnnull;returngetParent(root,node);}publicBinaryNode<E>getParent(BinaryNode<E>p,BinaryNode<E>node){BinaryNode<E>find=null;if(p!=null){if(p.left==node||p.right==node)find=p;else{find=getParent(p.left,node);if(find==null)find=getParent(p.right,node);}}returnfind;}DLR算法時(shí)間復(fù)雜度是O（n）第6章樹和二叉樹三種遍歷總結(jié)先根遍歷序列：ABDEC中根遍歷序列：DBEAC后根遍歷序列：DEBCAABCDE先根遍歷序列中的第一個(gè)元素一定是整個(gè)二叉樹的根結(jié)點(diǎn)中根遍歷根結(jié)點(diǎn)會(huì)把兩個(gè)左右子樹中的結(jié)點(diǎn)分隔開來(lái)。后根遍歷序列中的最后一個(gè)元素也一定是整個(gè)二叉樹的根結(jié)點(diǎn)第6章樹和二叉樹思考題先根中根后根ABDCEBDAECCBEDAFIGHCEDBIFHGA已知一個(gè)二叉樹的先根遍歷序列和中根遍歷序列，能否唯一決定一個(gè)二叉樹？如果能，請(qǐng)畫出這個(gè)二叉樹，并給出它的后根遍歷序列。已知一個(gè)二叉樹的后根遍歷序列和中根遍歷序列，能否唯一決定一個(gè)二叉樹？如果能，請(qǐng)畫出這個(gè)二叉樹，并給出它的先根遍歷序列。已知一個(gè)二叉樹的先根遍歷序列和后根遍歷序列，能否唯一決定一個(gè)二叉樹？如果不能，請(qǐng)舉例證明。第6章樹和二叉樹思考題解答先根中根后根ABDCEBDAECABCDE（B,D）（E,C）A（B,D）（E,C）BCA（B,D）（E,C）第6章樹和二叉樹先根中根后根CBEDAFIGHCEDBIFHGAA（C,B,E,D）（F,I）B（E,D）CGH（F,I,G,H）DEFI第6章樹和二叉樹6.3.4構(gòu)造二叉樹1、先根和中根序列表示2、標(biāo)明空子樹的先根序列表示3、廣義表表示4、以完全二叉樹的層次遍歷序列構(gòu)造鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的完全二叉樹

建立一顆二叉樹必須明確兩點(diǎn)：結(jié)點(diǎn)與父母結(jié)點(diǎn)及孩子結(jié)點(diǎn)之間的層次關(guān)系。兄弟結(jié)點(diǎn)間的左右子樹的次序關(guān)系。第6章樹和二叉樹1、先根和中根序列表示證明：設(shè)二叉樹的先根和中根遍歷序列分別用數(shù)組preorder和inorder表示。（1）由先根遍歷序列知，該二叉樹的根為：preorder[0]。（2）在inorder中一定存在下標(biāo)i，使得inorder

[i]==

preorder[0];ABDCE下標(biāo)01ii+1n-1preorder根左子樹右子樹BDAEC下標(biāo)0i-1ii+1n-1inorder根左子樹右子樹第6章樹和二叉樹由中根遍歷知，inorder[i]之前的結(jié)點(diǎn)在根的左子樹上，inorder[i]之后的結(jié)點(diǎn)在根的右子樹上，因此，根的左子樹由i個(gè)結(jié)點(diǎn)組成：先根序列——preorder[1],…,preorder[i];根序序列——inorder[0],…,inorder[i-1];根的右子樹由n-1-i個(gè)結(jié)點(diǎn)組成：先根序列——preorder[i+1],…,preorder[n-1];中根序列——inorder[i+1],…,inorder[n-1];（3）依次遞歸，可建立唯一的一顆二叉樹。ABDCE下標(biāo)01ii+1n-1preorder根左子樹右子樹BDAEC下標(biāo)0i-1ii+1n-1inorder根左子樹右子樹A（B,D）（E,C）第6章樹和二叉樹2、標(biāo)明空子樹的先根序列表示第6章樹和二叉樹算法描述數(shù)組preorder表示一顆二叉樹標(biāo)明空子樹的先根次序遍歷序列，構(gòu)造二叉樹的遞歸算法描述如下：（1）preorder[0]一定是二叉樹的根，創(chuàng)建根結(jié)點(diǎn)；preorder[1]一定是根的左孩子。（2）若preorder[i]不是“.”，則創(chuàng)建一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)元素是preorder[i+1]，但父母與孩子之間的鏈還未建立；否則當(dāng)前子樹為空，返回上一層結(jié)點(diǎn)。（3）返回到當(dāng)前結(jié)點(diǎn)時(shí)，下一個(gè)元素preorder[i+1]是當(dāng)前結(jié)點(diǎn)的右孩子結(jié)點(diǎn)；當(dāng)一個(gè)結(jié)點(diǎn)的左右孩子鏈已建立，則以當(dāng)前結(jié)點(diǎn)為根的一顆子樹就已建好，返回上一層結(jié)點(diǎn)。（4）重復(fù)執(zhí)行步驟2～3，直到返回根結(jié)點(diǎn)，則二叉樹建成，使root指向根結(jié)點(diǎn)。第6章樹和二叉樹datarightleftA^^ABD.G...CE..FH...012345678910111213141516A^^B^^A^^B^^D^^p第6章樹和二叉樹A^^B^^D^pG^^A^^B^D^G^^pA^B^D^G^^pABD.G...CE..FH...012345678910111213141516第6章樹和二叉樹publicBinaryTree(E[]preorder){root=create(preorder);}privateinti=0;privateBinaryNode<E>create(E[]preorder){BinaryNode<E>p=null;if(i<preorder.length){Eelem=preorder[i];i++;if(elem!=null){p=newBinaryNode<E>(elem);p.left=create(preorder);p.right=create(preorder);}}returnp;}構(gòu)造方法：第6章樹和二叉樹【例6.2】輸出二叉樹中指定結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)。Ancestors.java第6章樹和二叉樹3、廣義表表示廣義表可以表示一棵樹，但不能唯一表示一顆二叉樹。ABABA（B）第6章樹和二叉樹第6章樹和二叉樹4.以完全二叉樹的層次遍歷序列構(gòu)造鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的完全二叉樹

【例6.3】建立二叉鏈表表示的完全二叉樹。CompleteBinaryTree.javaABCDEFGH完全二叉樹的層次遍歷序列：ABCDEFGH第6章樹和二叉樹6.3.5二叉樹的插入和刪除操作1、插入一個(gè)結(jié)點(diǎn)

publicvoidinsert(BinaryNode<E>p,Eelement,booleanleftChild){if(p!=null){BinaryNode<E>q=newBinaryNode<E>(element);if(leftChild){q.left=p.left;p.left=q;}else{q.right=p.right;p.right=q;}}}第6章樹和二叉樹插入一個(gè)結(jié)點(diǎn)，作為p的左孩子結(jié)點(diǎn)

publicvoidinsert(BinaryNode<E>p,Eelement){insert(p,element,true);}第6章樹和二叉樹2、刪除一棵子樹publicvoidremove(BinaryNode<E>p,booleanleftChild){if(p!=null){if(leftChild)p.left=null;elsep.right=null;}}publicvoidremove(BinaryNode<E>p){remove(p,true);}第6章樹和二叉樹6.3.6二叉樹遍歷的非遞歸算法二叉樹的二叉鏈表存儲(chǔ)中每個(gè)結(jié)點(diǎn)都缺少指向其父母結(jié)點(diǎn)的鏈，因此，必須借助輔助的數(shù)據(jù)結(jié)構(gòu)完成非遞歸遍歷。應(yīng)該選擇具有“后進(jìn)先出”特點(diǎn)的——棧第6章樹和二叉樹1.初始化一個(gè)空棧。2.從二叉樹的根結(jié)點(diǎn)p開始，如果p不空或棧不空，循環(huán)執(zhí)行以下操作。1)如果p不空，表示到達(dá)了一個(gè)結(jié)點(diǎn)，將結(jié)點(diǎn)p入桟，并進(jìn)入其左子樹。2)如果p為空而棧不空，表明已經(jīng)沿著某條路徑走出了二叉樹，此時(shí)需返回訪問這條路徑起始的這個(gè)結(jié)點(diǎn)，而該結(jié)點(diǎn)正好被保存在棧的棧頂，因此彈出棧頂元素并讓p指向它，接下來(lái)訪問結(jié)點(diǎn)p，然后進(jìn)入其右子樹。3.算法結(jié)束算法描述第6章樹和二叉樹第6章樹和二叉樹第6章樹和二叉樹第6章樹和二叉樹代碼見：BinaryTree.java中的inOrderTraverse()方法第6章樹和二叉樹6.3.7二叉樹的層次遍歷層次遍歷：是指從二叉樹的第1層（根結(jié)點(diǎn)）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。層序遍歷需要借助具有先進(jìn)現(xiàn)出特點(diǎn)的——隊(duì)列實(shí)現(xiàn)。層次遍歷序列：ABCDEFG第6章樹和二叉樹1.初始化一個(gè)空隊(duì)。2.從二叉樹的根結(jié)點(diǎn)p開始，如果p不空時(shí)，循環(huán)執(zhí)行以下操作。1)訪問P結(jié)點(diǎn)；2)如果P存在左孩子結(jié)點(diǎn)，將左孩子結(jié)點(diǎn)入隊(duì)；3)如果P存在右孩子結(jié)點(diǎn)，將右孩子結(jié)點(diǎn)入隊(duì)；4)p指向出隊(duì)結(jié)點(diǎn)，繼續(xù)，直到隊(duì)列為空。3.算法結(jié)束。算法描述第6章樹和二叉樹第6章樹和二叉樹第6章樹和二叉樹實(shí)現(xiàn)publicvoidlevelOrder(){LinkedQueue<BinaryNode<E>>que=new

LinkedQueue<BinaryNode<E>>();BinaryNode<E>p=this.root;System.out.print("levelOrderis:

");while(p!=null){System.out.print(p.data+"");if(p.left!=null)que.enqueue(p.left);if(p.right!=null)que.enqueue(p.right);p=que.dequeue();}System.out.println();}第6章樹和二叉樹演示：二叉樹的操作BinaryTree_ex.java第6章樹和二叉樹6.5哈夫曼編碼與哈夫曼樹6.5.1哈夫曼編碼6.5.2哈夫曼樹第6章樹和二叉樹編碼方案討論什么是編碼和解碼（譯碼）？編碼：將文件中的每個(gè)字符均轉(zhuǎn)換為一個(gè)唯一的二進(jìn)制位串。解碼：將二進(jìn)制位串轉(zhuǎn)換為對(duì)應(yīng)的字符。1、等長(zhǎng)編碼方案2、變長(zhǎng)編碼方案ASCII編碼Unicode編碼專用等長(zhǎng)編碼6.5.1哈夫曼編碼第6章樹和二叉樹1、等長(zhǎng)編碼方案等長(zhǎng)編碼方案將給定字符集C中每個(gè)字符的碼長(zhǎng)固定為：，|C|表示字符集的大小。如：ASCII編碼對(duì)每個(gè)字符采用8位二進(jìn)制編碼Unicode編碼對(duì)每個(gè)字符采用16位二進(jìn)制編碼【例】語(yǔ)句：Ifawoodchuckcouldchuckwood！一共由32個(gè)字符組成（包括空格和標(biāo)點(diǎn)符號(hào)）。如果每個(gè)字符采用Unicode編碼，一共需要多少位？答：32×16＝512位。如果每個(gè)字符采用ASCII編碼，一共需要多少位？答：32×8＝256位。但實(shí)際上上述的字符串中只有13個(gè)不同的字符，每個(gè)字符采用4位表示足已。一共需要多少位？答：32×4＝128位。第6章樹和二叉樹2、變長(zhǎng)編碼方案每個(gè)字符的編碼長(zhǎng)度不固定，一般的做法是將頻度高的字符編碼編成短碼，將頻度低的字符編成長(zhǎng)碼。

Ifawoodchuckcouldchuckwood！采用變長(zhǎng)編碼第6章樹和二叉樹等長(zhǎng)、變長(zhǎng)編碼對(duì)比變長(zhǎng)編碼可以壓縮數(shù)據(jù)量，從而節(jié)省存儲(chǔ)空間，加快數(shù)據(jù)的傳輸。但等長(zhǎng)編碼解碼時(shí)很方便，不會(huì)出現(xiàn)解碼歧義問題。而變長(zhǎng)編碼就有可能會(huì)出現(xiàn)解碼歧義問題產(chǎn)生該問題的原因是某些字符的編碼可能與其他字符的編碼開始部分（稱為前綴）相同。

【例】設(shè)E、T、W分別編碼為00、01、0001，則解碼時(shí)無(wú)法確定信息串0001是ET還是W。第6章樹和二叉樹哈夫曼編碼因此對(duì)字符集進(jìn)行編碼時(shí)，要求字符集中任一字符的編碼都不是其余字符編碼的前綴。我們用哈夫曼樹可以實(shí)現(xiàn)滿足這種要求的編碼，并且用這樣的編碼可以使得編碼總長(zhǎng)度最短。我們稱這種編碼為哈夫曼編碼。第6章樹和二叉樹AAAABBBCDDBBAAA00001010101111101101010000存儲(chǔ)“AAAABBBCDDBBAAA”，字符集[A、B、D、C]，字符出現(xiàn)次數(shù)為7、5、2、1，頻率為0.47、0.33、0.13、0.07，哈夫曼編碼過程為：第6章樹和二叉樹6.5.2哈夫曼樹CDBA0001111257A：0B：10C：111D：110第6章樹和二叉樹從根結(jié)點(diǎn)到所有結(jié)點(diǎn)的路徑長(zhǎng)