第6章 樹和二叉樹課件

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

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

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

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

Group=（D，R）有限個數(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é)點元素

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

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

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

EgetNextSibling(Eelement);//返回下一個兄弟結(jié)點

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ù)據(jù)結(jié)構(gòu)往往是二叉樹的形式。即使是一般的樹也能簡單地轉(zhuǎn)換為二叉樹，而且二叉樹的存儲結(jié)構(gòu)及其算法相比于樹來說較為簡單。因此將重點討論二叉樹的性質(zhì)、存儲以及常用的算法。第6章樹和二叉樹6.2.1二叉樹定義二叉樹（binarytree）是由n（n≥0）個結(jié)點組成的有限集合，此集合或者為空，或者由一個根結(jié)點加上兩棵分別稱為左、右子樹的，互不相交的二叉樹組成。二叉樹可以為空集，因此根可以有空的左子樹或者右子樹，亦或者左、右子樹皆為空。

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

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

歸納基礎(chǔ)：i=1時，有2i-1=20=1。因為第1層上只有一個根結(jié)點，所以命題成立。

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

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

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

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

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

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

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

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

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

由式子1和式子2得到：

n0=n2+1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

k-1≤log2n<k

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

k-1=

由此即得：

k=+1第6章樹和二叉樹給二叉樹結(jié)點編號

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

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

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

intcount(); //返回二叉樹的結(jié)點個數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對完全二叉樹而言，順序存儲結(jié)構(gòu)既簡單又節(jié)省存儲空間。一般的二叉樹采用順序存儲結(jié)構(gòu)時，雖然簡單，但易造成存儲空間的浪費?！纠孔顗牡那闆r下，一個高度為k且只有k個結(jié)點的右單支二叉樹需要2k-1個存儲單元。在對順序存儲的二叉樹做插入和刪除結(jié)點操作時，要大量移動結(jié)點。第6章樹和二叉樹2.二叉樹的鏈式存儲結(jié)構(gòu)（1）二叉鏈表若一顆具有n個結(jié)點的二叉樹用二叉鏈表存儲，有多少個空鏈？第6章樹和二叉樹（2）三叉鏈表第6章樹和二叉樹6.3.2二叉樹的二叉鏈表實現(xiàn)1、二叉鏈表結(jié)點類（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é)點，并且每個結(jié)點僅被訪問一次。一次完整的遍歷就是按照某種順序，使得二叉樹中的所有結(jié)點產(chǎn)生一個線性序列。第6章樹和二叉樹遍歷的種類非空二叉樹根結(jié)點D左子樹L右子樹RP3=63DLR

LDR

LRDDRL

RDL

RLD先左后右先右后左先根遍歷中根遍歷后根遍歷層序遍歷DLR第6章樹和二叉樹1、二叉樹的三種次序遍歷先根次序：訪問根結(jié)點，遍歷左子樹，遍歷右子樹。中根次序：遍歷左子樹，訪問根結(jié)點，遍歷右子樹。后根次序：遍歷左子樹，遍歷右子樹，訪問根結(jié)點。先根遍歷序列：ABDGCEFH中根遍歷序列：DGBAECHF后根遍歷序列：GDBEHFCA第6章樹和二叉樹2、二叉樹三種次序遍歷的遞歸算法若二叉樹為空二叉樹，則算法結(jié)束；否則先訪問根結(jié)點，再先根遍歷左子樹最后先根遍歷右子樹ABDECABCDEroot先根遍歷二叉樹遞歸算法第6章樹和二叉樹實現(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é)點，最后中根遍歷右子樹DBEACABCDEroot第6章樹和二叉樹實現(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é)點，DEBCAABCDEroot第6章樹和二叉樹實現(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é)點個數(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é)點

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算法時間復(fù)雜度是O（n）第6章樹和二叉樹三種遍歷總結(jié)先根遍歷序列：ABDEC中根遍歷序列：DBEAC后根遍歷序列：DEBCAABCDE先根遍歷序列中的第一個元素一定是整個二叉樹的根結(jié)點中根遍歷根結(jié)點會把兩個左右子樹中的結(jié)點分隔開來。后根遍歷序列中的最后一個元素也一定是整個二叉樹的根結(jié)點第6章樹和二叉樹思考題先根中根后根ABDCEBDAECCBEDAFIGHCEDBIFHGA已知一個二叉樹的先根遍歷序列和中根遍歷序列，能否唯一決定一個二叉樹？如果能，請畫出這個二叉樹，并給出它的后根遍歷序列。已知一個二叉樹的后根遍歷序列和中根遍歷序列，能否唯一決定一個二叉樹？如果能，請畫出這個二叉樹，并給出它的先根遍歷序列。已知一個二叉樹的先根遍歷序列和后根遍歷序列，能否唯一決定一個二叉樹？如果不能，請舉例證明。第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、標明空子樹的先根序列表示3、廣義表表示4、以完全二叉樹的層次遍歷序列構(gòu)造鏈式存儲結(jié)構(gòu)的完全二叉樹

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

[i]==

preorder[0];ABDCE下標01ii+1n-1preorder根左子樹右子樹BDAEC下標0i-1ii+1n-1inorder根左子樹右子樹第6章樹和二叉樹由中根遍歷知，inorder[i]之前的結(jié)點在根的左子樹上，inorder[i]之后的結(jié)點在根的右子樹上，因此，根的左子樹由i個結(jié)點組成：先根序列——preorder[1],…,preorder[i];根序序列——inorder[0],…,inorder[i-1];根的右子樹由n-1-i個結(jié)點組成：先根序列——preorder[i+1],…,preorder[n-1];中根序列——inorder[i+1],…,inorder[n-1];（3）依次遞歸，可建立唯一的一顆二叉樹。ABDCE下標01ii+1n-1preorder根左子樹右子樹BDAEC下標0i-1ii+1n-1inorder根左子樹右子樹A（B,D）（E,C）第6章樹和二叉樹2、標明空子樹的先根序列表示第6章樹和二叉樹算法描述數(shù)組preorder表示一顆二叉樹標明空子樹的先根次序遍歷序列，構(gòu)造二叉樹的遞歸算法描述如下：（1）preorder[0]一定是二叉樹的根，創(chuàng)建根結(jié)點；preorder[1]一定是根的左孩子。（2）若preorder[i]不是“.”，則創(chuàng)建一個結(jié)點，該結(jié)點的左孩子結(jié)點元素是preorder[i+1]，但父母與孩子之間的鏈還未建立；否則當(dāng)前子樹為空，返回上一層結(jié)點。（3）返回到當(dāng)前結(jié)點時，下一個元素preorder[i+1]是當(dāng)前結(jié)點的右孩子結(jié)點；當(dāng)一個結(jié)點的左右孩子鏈已建立，則以當(dāng)前結(jié)點為根的一顆子樹就已建好，返回上一層結(jié)點。（4）重復(fù)執(zhí)行步驟2～3，直到返回根結(jié)點，則二叉樹建成，使root指向根結(jié)點。第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é)點的所有祖先結(jié)點。Ancestors.java第6章樹和二叉樹3、廣義表表示廣義表可以表示一棵樹，但不能唯一表示一顆二叉樹。ABABA（B）第6章樹和二叉樹第6章樹和二叉樹4.以完全二叉樹的層次遍歷序列構(gòu)造鏈式存儲結(jié)構(gòu)的完全二叉樹

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

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章樹和二叉樹插入一個結(jié)點，作為p的左孩子結(jié)點

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二叉樹遍歷的非遞歸算法二叉樹的二叉鏈表存儲中每個結(jié)點都缺少指向其父母結(jié)點的鏈，因此，必須借助輔助的數(shù)據(jù)結(jié)構(gòu)完成非遞歸遍歷。應(yīng)該選擇具有“后進先出”特點的——棧第6章樹和二叉樹1.初始化一個空棧。2.從二叉樹的根結(jié)點p開始，如果p不空或棧不空，循環(huán)執(zhí)行以下操作。1)如果p不空，表示到達了一個結(jié)點，將結(jié)點p入桟，并進入其左子樹。2)如果p為空而棧不空，表明已經(jīng)沿著某條路徑走出了二叉樹，此時需返回訪問這條路徑起始的這個結(jié)點，而該結(jié)點正好被保存在棧的棧頂，因此彈出棧頂元素并讓p指向它，接下來訪問結(jié)點p，然后進入其右子樹。3.算法結(jié)束算法描述第6章樹和二叉樹第6章樹和二叉樹第6章樹和二叉樹第6章樹和二叉樹代碼見：BinaryTree.java中的inOrderTraverse()方法第6章樹和二叉樹6.3.7二叉樹的層次遍歷層次遍歷：是指從二叉樹的第1層（根結(jié)點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問。層序遍歷需要借助具有先進現(xiàn)出特點的——隊列實現(xiàn)。層次遍歷序列：ABCDEFG第6章樹和二叉樹1.初始化一個空隊。2.從二叉樹的根結(jié)點p開始，如果p不空時，循環(huán)執(zhí)行以下操作。1)訪問P結(jié)點；2)如果P存在左孩子結(jié)點，將左孩子結(jié)點入隊；3)如果P存在右孩子結(jié)點，將右孩子結(jié)點入隊；4)p指向出隊結(jié)點，繼續(xù)，直到隊列為空。3.算法結(jié)束。算法描述第6章樹和二叉樹第6章樹和二叉樹第6章樹和二叉樹實現(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章樹和二叉樹編碼方案討論什么是編碼和解碼（譯碼）？編碼：將文件中的每個字符均轉(zhuǎn)換為一個唯一的二進制位串。解碼：將二進制位串轉(zhuǎn)換為對應(yīng)的字符。1、等長編碼方案2、變長編碼方案ASCII編碼Unicode編碼專用等長編碼6.5.1哈夫曼編碼第6章樹和二叉樹1、等長編碼方案等長編碼方案將給定字符集C中每個字符的碼長固定為：，|C|表示字符集的大小。如：ASCII編碼對每個字符采用8位二進制編碼Unicode編碼對每個字符采用16位二進制編碼【例】語句：Ifawoodchuckcouldchuckwood！一共由32個字符組成（包括空格和標點符號）。如果每個字符采用Unicode編碼，一共需要多少位？答：32×16＝512位。如果每個字符采用ASCII編碼，一共需要多少位？答：32×8＝256位。但實際上上述的字符串中只有13個不同的字符，每個字符采用4位表示足已。一共需要多少位？答：32×4＝128位。第6章樹和二叉樹2、變長編碼方案每個字符的編碼長度不固定，一般的做法是將頻度高的字符編碼編成短碼，將頻度低的字符編成長碼。

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

【例】設(shè)E、T、W分別編碼為00、01、0001，則解碼時無法確定信息串0001是ET還是W。第6章樹和二叉樹哈夫曼編碼因此對字符集進行編碼時，要求字符集中任一字符的編碼都不是其余字符編碼的前綴。我們用哈夫曼樹可以實現(xiàn)滿足這種要求的編碼，并且用這樣的編碼可以使得編碼總長度最短。我們稱這種編碼為哈夫曼編碼。第6章樹和二叉樹AAAABBBCDDBBAAA00001010101111101101010000存儲“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é)點到所有結(jié)點的路徑長