第06章 樹和二叉樹(Java版)

第6章樹和二叉樹6.1樹及其抽象數(shù)據(jù)類型6.2二叉樹及其抽象數(shù)據(jù)類型6.3二叉樹的表示和實(shí)現(xiàn)6.4線索二叉樹6.5Huffman編碼與Huffman樹6.6樹的表示和實(shí)現(xiàn)本章是數(shù)據(jù)結(jié)構(gòu)課程的重中之重，也是難點(diǎn)所在，表現(xiàn)為二叉鏈表存儲(chǔ)結(jié)構(gòu)和遞歸算法相結(jié)合。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和遞歸算法本身就是兩個(gè)難 點(diǎn)，建立二叉樹需要將它們有機(jī)結(jié)合。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》目的和要求目的：理解樹型結(jié)構(gòu)；掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表達(dá) 非線性結(jié)構(gòu)，掌握遞歸算法設(shè)計(jì)。內(nèi)容：二叉樹的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)，二叉鏈 表表示的二叉樹類；中序線索二叉樹； Huffman樹；樹的定義、存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)。要求：理解樹和二叉樹概念，掌握樹和二叉樹的 表示和實(shí)現(xiàn)，掌握遞歸算法設(shè)計(jì)。重點(diǎn)：二叉鏈表表示的二叉樹類；Huffman樹；樹 的定義、存儲(chǔ)結(jié)構(gòu)和構(gòu)造算法。難點(diǎn)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表達(dá)非線性結(jié)構(gòu)；遞歸算法 設(shè)計(jì)。實(shí)驗(yàn)：樹和二叉樹的基本操作，鏈?zhǔn)酱鎯?chǔ)結(jié) 構(gòu)表示樹和二叉樹；遞歸算法。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.1樹及其抽象數(shù)據(jù)類型6.1.1樹定義6.1.2樹的術(shù)語6.1.3樹的表示法6.1.4樹抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.1.1樹定義樹（tree）是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。n=0的樹稱為空樹；n>0的樹T：根（root）結(jié)點(diǎn)，它沒有前驅(qū)結(jié)點(diǎn)。其他結(jié)點(diǎn)分為m棵互不相交的子樹。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.1.2樹的術(shù)語父母、孩子與兄弟結(jié)點(diǎn)度結(jié)點(diǎn)層次、樹的高度邊、路徑無序樹、有序樹森林?jǐn)?shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.1.3樹的表示法圖示法橫向凹入表示法A B E F C G D H I J廣義表表示A(B(E,F),C(G),D(H,I,J))數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.1.4樹抽象數(shù)據(jù)類型publicinterfaceTTree<T>//樹接口{boolean

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

TreeNode<T>getChild(TreeNode<T>p,inti);//返回p第i個(gè)孩子

TreeNode<T>getParent(TreeNode<T>node);//返回node的父母

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

intheight();//樹的高度

TreeNode<T>search(Tx);//查找并返回元素為x的結(jié)點(diǎn)

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

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

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

voidinsertRoot(Tx);//插入元素x作為根結(jié)點(diǎn)

TreeNode<T>insertChild(TreeNode<T>p,T

x,inti);//插入孩子voidremoveChild(TreeNode<T>p,inti);//刪除孩子}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.2二叉樹及其抽象數(shù)據(jù)類型6.2.1二叉樹定義6.2.2二叉樹性質(zhì)6.2.3二叉樹的遍歷6.2.4二叉樹抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.2.1二叉樹定義二叉樹（binarytree）是n個(gè)結(jié)點(diǎn)的有限集合：空二叉樹；由一個(gè)根結(jié)點(diǎn)、兩棵互不相交的左子樹和右子樹組成。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.2.2二叉樹性質(zhì)性質(zhì)1：若根結(jié)點(diǎn)的層次為1，則二叉樹第i層最多有2i1（i≥1）個(gè)結(jié)點(diǎn)。性質(zhì)2：在高度為k的二叉樹中，最多有2k1個(gè)結(jié)點(diǎn)（k≥0）。性質(zhì)3：設(shè)一棵二叉樹的葉子結(jié)點(diǎn)數(shù)為n0，2度結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》性質(zhì)4：n個(gè)結(jié)點(diǎn)完全二叉樹的高度是。性質(zhì)5：一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹，對(duì)序號(hào)為i（0≤i<n）的結(jié)點(diǎn)，有：若i=0，則i為根結(jié)點(diǎn)，無父母結(jié)點(diǎn)；若i>0，則i的父母結(jié)點(diǎn)序號(hào)為。若2i+1<n，則i的左孩子結(jié)點(diǎn)序號(hào)為2i+1；否則i無左孩子。若2i+2<n，則i的右孩子結(jié)點(diǎn)序號(hào)為2i+2；否則i無右孩子。

數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.2.3二叉樹的遍歷先根次序：訪問根結(jié)點(diǎn)，遍歷左子樹，遍歷右子樹。中根次序：遍歷左子樹，訪問根結(jié)點(diǎn)，遍歷右子樹。后根次序：遍歷左子樹，遍歷右子樹，訪問根結(jié)點(diǎn)。先根遍歷序列：ABDGCEFH中根遍歷序列：DGBAECHF后根遍歷序列：GDBEHFCA數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.2.4二叉樹抽象數(shù)據(jù)類型publicinterfaceBinaryTTree<T>{boolean

isEmpty();//判斷是否空

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

intheight();//返回高度

voidpreOrder();//先根次序遍歷

voidinOrder();//中根次序遍歷

voidpostOrder();//后根次序遍歷

voidlevelOrder();//按層次遍歷

BinaryNode<T>search(Tkey);//查找

BinaryNode<T>getParent(BinaryNode<T>node);//返回父母

voidinsertRoot(Tx);//插入元素x作為根結(jié)點(diǎn)

BinaryNode<T>insertChild(BinaryNode<T>p,Tx,boolean

leftChild);

voidremoveChild(BinaryNode<T>p,boolean

leftChild);

voidremoveAll();

}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.3二叉樹的表示和實(shí)現(xiàn)6.3.1二叉樹的存儲(chǔ)結(jié)構(gòu)6.3.2二叉樹的二叉鏈表實(shí)現(xiàn)6.3.3三叉樹的二叉鏈表實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.3.1二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》2.二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表三叉鏈表數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.3.2二叉樹的二叉鏈表實(shí)現(xiàn)二叉樹的二叉鏈表結(jié)點(diǎn)類publicclassBinaryNode<T>{Tdata;//數(shù)據(jù)元素

BinaryNode<T>left,right;//左、右孩子}二叉樹類publicclassBinaryTree<T>implementsBinaryTTree<T>{BinaryNode<T>root;//根結(jié)點(diǎn)}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》3.二叉樹三種次序遍歷的遞歸算法//先根次序遍歷以p結(jié)點(diǎn)為根的子樹privatevoidpreOrder(BinaryNode<T>p){if(p!=null)//若二叉樹不空

{System.out.print(p.data+"");//訪問當(dāng)前結(jié)點(diǎn)

preOrder(p.left);//按先根次序遍歷左子樹

preOrder(p.right);//按先根次序遍歷右子樹

}}【例6.1】構(gòu)造并遍歷二叉樹。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》4.基于遍歷的操作求結(jié)點(diǎn)個(gè)數(shù)求高度查找獲得父母結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》5.構(gòu)造二叉樹（1）先根和中根序列表示數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（2）標(biāo)明空子樹的先根序列表示【例6.2】輸出二叉樹中指定結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（3）廣義表表示數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（4）以完全二叉樹的層次遍歷序列構(gòu)造鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的完全二叉樹【例6.3】建立二叉鏈表表示的完全二叉樹。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.二叉樹的插入和刪除操作（1）插入一個(gè)結(jié)點(diǎn)（2）刪除一棵子樹數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》7.二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》8.二叉樹的層次遍歷數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.3.3三叉樹的二叉鏈表實(shí)現(xiàn)二叉樹的三叉鏈表結(jié)點(diǎn)類publicclassTriNode<T>{publicTdata;//數(shù)據(jù)域

publicTriNode<T>parent,left,right;

//父母結(jié)點(diǎn)、左和右孩子結(jié)點(diǎn)

publicintlevel;//結(jié)點(diǎn)的層次}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》2.三叉鏈表表示的二叉樹類publicclassTriBinaryTree<T>{publicTriNode<T>root;//根結(jié)點(diǎn)}（1）構(gòu)造二叉樹數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（2）插入結(jié)點(diǎn)例6.4輸出三叉鏈表存儲(chǔ)二叉樹的一條直徑。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.4線索二叉樹6.4.1線索二叉樹定義數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.4.2中序線索二叉樹二叉樹的中序線索化中序線索二叉樹類中根次序遍歷中序線索二叉樹【例6.5】構(gòu)造中序線索二叉樹并進(jìn)行中根次序遍歷。先根次序遍歷中序線索二叉樹后根次序遍歷中序線索二叉樹數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》1.二叉樹的中序線索化數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》2.中序線索二叉樹類publicclassThreadBinaryTree<T>{publicThreadNode<T>root;}3.中根次序遍歷中序線索二叉樹數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》4.先根次序遍歷中序線索二叉樹數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》5.后根次序遍歷中序線索二叉樹數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.5Huffman編碼與Huffman樹6.5.1Huffman編碼存儲(chǔ)“AAAABBBCDDBBAAA”，字符集[A、B、D、C]，字符出現(xiàn)次數(shù)為7、5、2、1，頻率為0.47、0.33、0.13、0.07，哈夫曼編碼過程為：AAAABBBCDDBBAAA00001010101111101101010000數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.5.2Huffman樹二叉樹的路徑長度數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》2.二叉樹的外路徑長度數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》3.二叉樹的帶權(quán)外路徑長度數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》4.Huffman算法哈夫曼樹定義為帶權(quán)外路徑長度最短的二叉樹。哈夫曼樹不唯一數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》構(gòu)造Huffman樹并獲得Huffman編碼Huffman編碼的譯碼數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》例6.6構(gòu)造Huffman樹并獲得Huffman編碼。<1>采用靜態(tài)三叉鏈表存儲(chǔ)Huffman樹數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》圖6-44Huffman樹和Huffman編碼若權(quán)值集合{5,29,7,8,14,23,3,11}對(duì)應(yīng)字符A～H數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》<2>存儲(chǔ)Huffman編碼數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.6樹的表示和實(shí)現(xiàn)6.6.1樹的遍歷6.6.2樹的存儲(chǔ)結(jié)構(gòu)6.3.3樹的孩子兄弟鏈表實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》6.6.1樹的遍歷樹的先根遍歷算法描述如下：訪問根結(jié)點(diǎn)。按照從左到右的次序先根遍歷根的每一棵子樹。樹的后根遍歷算法描述如下：按照從左到右