蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章課件

1、蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章16.1 樹的一些專有名詞6.2 二叉樹6.3 二叉樹的表示方法 6.4 二叉樹遍歷6.5 二叉查找樹 6.6 其他論題6.7 程序集錦6.8 思考題蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章2樹結(jié)構(gòu)是指各項(xiàng)數(shù)據(jù)可通過邊（edge）連接起來的組織方法。 樹的定義如下：樹是由結(jié)點(diǎn)（node）和邊（edge）所組成的集合。它包括有一特殊的結(jié)點(diǎn)，稱為根（root）；其余的結(jié)點(diǎn)分成n個（n 0）互斥的集合T1，T2，Tn，每一個集合都是一棵樹。T1，T2，Tn是根的子樹（subtree）。 蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章3通過下面樹的表示法介紹樹的一些專有名詞：1. 結(jié)點(diǎn)與邊：結(jié)點(diǎn)代

2、表某項(xiàng)數(shù)據(jù)，而邊是指由一結(jié)點(diǎn)到另一結(jié)點(diǎn)的分支。圖中有14個結(jié)點(diǎn)，其結(jié)點(diǎn)的數(shù)據(jù)是英文字母。 蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章42. 祖先結(jié)點(diǎn)與子孫結(jié)點(diǎn)：若從結(jié)點(diǎn)X有一條路徑通往結(jié)點(diǎn)Y，則X是Y的祖先，Y是X的子孫。如上圖所示，結(jié)點(diǎn)A可通往K，故稱A是K的祖先，而K是A的子孫。3. 父結(jié)點(diǎn)與子結(jié)點(diǎn)：若結(jié)點(diǎn)X直接到結(jié)點(diǎn)Y，則稱X為Y的父結(jié)點(diǎn)，Y為X的子結(jié)點(diǎn)。如上圖所示，A為B、C、D的父結(jié)點(diǎn)，B、C、D為A的子結(jié)點(diǎn)。 蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章54. 兄弟結(jié)點(diǎn)：相同父結(jié)點(diǎn)的子結(jié)點(diǎn)。如圖所示，B、C、D為兄弟結(jié)點(diǎn)。5. 非終端結(jié)點(diǎn)：有子結(jié)點(diǎn)的結(jié)點(diǎn)。如圖所示，除了J、K、L、G、M、N、I外，其余的結(jié)

3、點(diǎn)皆為非終端結(jié)點(diǎn)。 6. 終端結(jié)點(diǎn)或葉子結(jié)點(diǎn)：沒有子結(jié)點(diǎn)的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)，如圖所示，J、K、L、G、M、N、I皆為葉子結(jié)點(diǎn)。 蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章67. 結(jié)點(diǎn)的度：一個結(jié)點(diǎn)的度是它擁有的子結(jié)點(diǎn)數(shù)。如圖所示A的度為3，而B的度為2。而一棵樹的度是指樹內(nèi)各結(jié)點(diǎn)所擁有的度的最大值，如圖所示，這棵樹的度為3。8. 層次：樹中結(jié)點(diǎn)世代的關(guān)系，一代為一個層次，根的層為1，如圖所示，此樹層次為4。9. 高度：樹中某結(jié)點(diǎn)的高度表示此結(jié)點(diǎn)到葉子結(jié)點(diǎn)的最長路徑（path）長度，如圖所示的A結(jié)點(diǎn)高度為3，C結(jié)點(diǎn)的高度為1，而樹的高度為樹中最大高度。如圖所示，此棵樹的高度為3。蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6

4、章710. 深度：某個結(jié)點(diǎn)的深度為根至此結(jié)點(diǎn)的路徑長度，如圖所示的C結(jié)點(diǎn)其深度為1，而M、N結(jié)點(diǎn)的深度為3，同理，E結(jié)點(diǎn)的深度為2。蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章8二叉樹是由結(jié)點(diǎn)所組成的有限集合，這個集合不是空集合就是由左子樹（left subtree）和右子樹（right subtree）所組成的。二叉樹與一般樹不同的地方是： 1.二叉樹的結(jié)點(diǎn)個數(shù)可以是零，而一般樹至少由一個結(jié)點(diǎn)所組成。2.二叉樹有排列順序的關(guān)系，而一般樹則沒有。3.二叉樹中每一結(jié)點(diǎn)的度至多為2，而一般樹無此限制。 蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章9有一棵樹如圖所示。試回答下列問題：（1）它是否是一棵二叉樹？（2）它是否是一棵

5、滿二叉樹？（3）它是否是一棵完全二叉樹？ 蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章10如何將二叉樹的結(jié)點(diǎn)存儲在一維數(shù)組中呢？可以想像此二叉樹為滿二叉樹，第I層具有2i-1個結(jié)點(diǎn)，依此類推。假若是三叉樹，第I層則有3i-1個結(jié)點(diǎn)。也可以利用鏈表的方式來解決這些問題，將每一結(jié)點(diǎn)劃分3個字段，左指針（Left Link）以LLINK表示，數(shù)據(jù)（data）以DATA表示，右指針（Right Link）以RLINK表示，如下圖所示。 蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章11二叉樹的遍歷（traversal）可分成3種：1 中序遍歷（inorder）：先遍歷左子樹，然后遍歷樹根，再遍歷右子樹。2 先序遍歷（preorde

6、r）：先遍歷樹根，然后遍歷左子樹，再遍歷右子樹。3 后序遍歷（postorder）：先遍歷左子樹，然后遍歷右子樹，再遍歷樹根。（舉例p125） 蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章12二叉查找樹（Binary Search Tree）的定義為二叉查找樹可以是空集點(diǎn)，假設(shè)不是空集合，則樹中的每一結(jié)點(diǎn)（node）均含有一關(guān)鍵字（key value），而且具有下列特性：1在左子樹的所有關(guān)鍵字均小于根的關(guān)鍵字。2在右子樹的所有關(guān)鍵字均大于根的關(guān)鍵字。3左子樹和右子樹是二叉查找樹。 蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章136.5.1 二叉查找樹的插入與刪除6.5.2 二叉查找樹的查詢 蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章

7、14由于二叉查找樹的特性是左子樹關(guān)鍵字均小于根的關(guān)鍵字，而右子樹的關(guān)鍵字均大于根的關(guān)鍵字。因此加入某一關(guān)鍵字只要逐一比較，依據(jù)關(guān)鍵字的大小往右或往左，便可找到此關(guān)鍵字插入的位置。 刪除某一結(jié)點(diǎn)時，若刪除的是葉結(jié)點(diǎn)，則直接刪除，假若刪除的不是葉結(jié)點(diǎn)，則在左子樹找到最大的結(jié)點(diǎn)或在右子樹找到最小的結(jié)點(diǎn)，取代將被刪除的結(jié)點(diǎn)。蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章15如何決定關(guān)鍵字X是否在二叉查找樹中，首先X先與根比較，若X等于根表示找到，如果X大于樹根，則往右子樹去查找；否則，到左子樹去查找。二叉查找樹的查詢程序如下：/ 查詢二叉查找樹tree中的data值，tree中的每個結(jié)點(diǎn)都有3個字段/ llink、k

8、ey、rlink，當(dāng)data不在tree中時，返回node的值為null/ llink(空的二叉樹)=rlink=null蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章16public Node_type search(Node_type tree, int data, Node_type node) node=tree; while(node!=null) if(datanode.key) node=node.rlink;else return node; 蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章171 將樹和森林轉(zhuǎn)換為二叉樹 一般樹轉(zhuǎn)換為二叉樹，步驟如下：（1）將結(jié)點(diǎn)的所有兄弟（sibling）連接在一起。（2）把

9、所有不是連到最左子結(jié)點(diǎn)的子結(jié)點(diǎn)鏈接刪除。（3）順時針旋轉(zhuǎn)45。蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章18森林轉(zhuǎn)換為二叉樹，步驟如下：（1）先將森林中的每棵樹轉(zhuǎn)換為二叉樹（不旋轉(zhuǎn)45）。（2）把所有二叉樹利用根結(jié)點(diǎn)全部鏈接在一起 。（3）旋轉(zhuǎn)45。蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章192 決定唯一的二叉樹 每一棵二叉樹都有唯一的一對中序與先序序列，也有唯一的中序與后序序列。如給予中序序列是FDHGIBEAC，而先序序列是ABDFGHIEC。由先序系列知，A是根，且由中序序列可知C是A的右子結(jié)點(diǎn)。由先序序列知B是FDHGIE的父結(jié)點(diǎn)，并從中序序列知E是B的右子結(jié)點(diǎn)。蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章20再由先序序列知D是FHGI的父結(jié)點(diǎn)，由中序知F是D的左子結(jié)點(diǎn)，HGI是D的右子結(jié)點(diǎn)。最后由先序序列可知G是HI的父結(jié)點(diǎn)，并從中序序列可知H是G的左子結(jié)點(diǎn)，I是G的右子結(jié)點(diǎn)。蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章211將如圖所示的一般樹轉(zhuǎn)換為二叉樹。2已知有一棵二叉樹，中序序列為ECBDA，先序序列為ABCED，試畫出此棵二叉樹。3已知有一棵二叉樹，中序序列為DFBAEGC，后序序列為FDBGECA，試畫出其所對應(yīng)的二叉樹。蔡明志數(shù)據(jù)結(jié)構(gòu)java版第6章22二叉查找樹結(jié)點(diǎn)的