第06章+樹和二叉樹

《第06章+樹和二叉樹》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第6章樹和二叉樹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)，哈夫曼樹。難點：線索二叉樹，哈夫曼樹?！稊?shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》前面討論的數(shù)據(jù)結(jié)構(gòu)都屬于線性結(jié)構(gòu)，其主要用于對客觀世界中具有單一的前驅(qū)和后繼的數(shù)據(jù)關(guān)系進行描述，而現(xiàn)實中的許多事物中的聯(lián)系都是非線性的。所謂非線性結(jié)構(gòu)是指，在該結(jié)構(gòu)中至少存在一個數(shù)據(jù)元素，有兩個或兩個以上的直接前驅(qū)（或直接后繼）元素。樹型結(jié)構(gòu)和圖型就是其中十分重要的非線性結(jié)構(gòu)，

2、可以用來描述客觀世界中廣泛存在的層次結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)的關(guān)系，如族譜、城市交通等?！稊?shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》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版）（第2版）》6.1.1樹定義樹（tree）是由n（n≥0）個結(jié)點組成的有限集合。n=0的樹稱為空樹；n＞0的樹T：根（root）結(jié)點，它沒有前驅(qū)結(jié)點。其他結(jié)點分為m棵互不相交的子樹?！稊?shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3c3b11211133a2a1b1aa1a2c1例：家譜圖《數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》樹的邏輯意義

3、由一個或多個結(jié)點組成的有限集合。僅有一個根結(jié)點，結(jié)點間有明顯的層次結(jié)構(gòu)關(guān)系。ACGT2DHIT3JMBELKT1F《數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》從邏輯結(jié)構(gòu)看：1）樹中只有根結(jié)點沒有前趨；2）除根外，其余結(jié)點都有且僅一個前趨；3）樹的結(jié)點，可以有零個或多個后繼；4）除根外的其他結(jié)點，都存在唯一一條從根到該結(jié)點的路徑；5）樹是一種分枝結(jié)構(gòu)（除根結(jié)點外）每個元素都有且僅有一個直接前趨，有且僅有零個或多個直接后繼。JIACBDHGFEKLM《數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》6.1.2樹的術(shù)語結(jié)點(node)：表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分

4、支。孩子(child)：結(jié)點子樹的根稱為該結(jié)點的孩子。父母，雙親(parents)：孩子結(jié)點的上層結(jié)點。兄弟(sibling)：同一雙親的孩子。《數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》6.1.2樹的術(shù)語結(jié)點度(degree)：結(jié)點擁有的子樹數(shù)葉結(jié)點：度為0的結(jié)點稱為葉結(jié)點，或者稱為終端結(jié)點分枝結(jié)點：度不為0的結(jié)點稱為分支結(jié)點，或者稱為非終端結(jié)點。一棵樹的結(jié)點除葉結(jié)點外，其余的都是分支結(jié)點樹的度：一棵樹中最大的結(jié)點度數(shù)結(jié)點的層(level)：從根結(jié)點算起，根為第一層，它的孩子為第二層……高度(depth)：樹中結(jié)點的最大層次數(shù)《數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》6.

5、1.2樹的術(shù)語路徑、路徑長度：如果一棵樹的一串結(jié)點n0,n1,…,nk-1有如下關(guān)系：結(jié)點ni是ni+1的父結(jié)點（0≤i

6、的樹的集合稱為森林。任何一棵樹，刪去根結(jié)點就變成了森林?！稊?shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》ABCDEFGHIJKLM結(jié)點A的度：3結(jié)點B的度：2結(jié)點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點A的孩子：B，C，D結(jié)點B的孩子：E，F(xiàn)結(jié)點I的雙親：D結(jié)點L的雙親：E結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟樹的度：3結(jié)點A的層：1結(jié)點M的層：4樹的高（深）度：4結(jié)點F，G為堂兄弟結(jié)點A是結(jié)點F，G的祖先《數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》6.1.3樹的表示法樹型表示bacghdefij《數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》圖形表示法：教師學生其他人員02級03級04

7、級05級……杭州電子科技大學計算機學院管理學院電子學院……葉子根子樹《數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》凹入表表示abdeijfcghabcedghij《數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》abcedghij廣義表（嵌套集合）表示ijdghabcea(b(d,e(i,j)),c(g,h))《數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》6.1.4樹抽象數(shù)據(jù)類型publicinterfaceTTree{//樹接口booleanisEmpty();//判斷是否空樹EgetRoot();//返回根結(jié)點元素EgetParent(Echild);//返回child的父母結(jié)點in

8、tgetChildCount(Epar