資源描述：
《第6章+樹與二叉樹》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、第6章樹和二叉樹6.1樹的定義和基本術語6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.6赫夫曼樹及其應用特點：非線性結構，一個直接前驅，但可能有多個直接后繼（1：n）16.1樹的定義和基本術語1.樹的定義2.若干術語3.邏輯結構4.存儲結構5.樹的運算21.樹的定義注1：過去許多書籍中都定義樹為n≥1，曾經有“空樹不是樹”的說法，但現在樹的定義已修改。注2：樹的定義具有遞歸性，即樹的定義中還有樹。樹（Tree）是n個(n≥0)結點組成的有限集合T。在任何一棵非空樹中：（1）有且僅有一個結點稱為根（root）；（2）當n>1時，其余的結點可分為m
2、(m>0)個互不相交的有限集合T1,T2，…，Tm。其中，每個集合本身又是一棵樹，被稱作這個根的子樹（SubTree）。3A只有根結點的樹ABCDEFGHIJKLM有子樹的樹根子樹4樹的抽象數據類型定義（見教材P118-119）ADTTree{數據對象D:數據關系R:基本操作P：}ADTTree若D為空集，則稱為空樹；//允許n=0若D中僅含一個數據元素，則R為空集；否則R={H}，H是如下二元關系：①在D中存在唯一根元素root，在H下無前驅②若D-{root}≠Φ，則存在對D-{root}的一個劃分，對任意j≠k，有Dj∩Dk=Φ。且關系H...③對應
3、于D-{root}的劃分，H-……有唯一一個劃分，對任意j≠k，有Hj∩Hk=Φ。(Di,{Hi})D是具有相同特性的數據元素的集合。//至少有15個5基本操作：查找類插入類刪除類6Root(T)//求樹的根結點查找類：Value(T,cur_e)//求當前結點的元素值Parent(T,cur_e)//求當前結點的雙親結點LeftChild(T,cur_e)//求當前結點的最左孩子RightSibling(T,cur_e)//求當前結點的右兄弟TreeEmpty(T)//判定樹是否為空樹TreeDepth(T)//求樹的深度TraverseTree(T,V
4、isit())//遍歷7InitTree(&T)//初始化置空樹插入類：CreateTree(&T,definition)//按定義構造樹Assign(T,cur_e,value)//給當前結點賦值InsertChild(&T,&p,i,c)//將以c為根的樹插入為結點p的第i棵子樹8ClearTree(&T)//將樹清空刪除類：DestroyTree(&T)//銷毀樹的結構DeleteChild(&T,&p,i)//刪除結點p的第i棵子樹9樹的表示法有幾種：圖形表示法嵌套集合表示法廣義表表示法凹入表示法左孩子－右兄弟表示法這些表示法的示意圖參見教材P12
5、0圖6.210廣義表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)))根作為由子樹森林組成的表的名字寫在表的左邊11左孩子－右兄弟表示法ABCDEFGHIJKLM數據左孩子右兄弟(A(B(E(K,L),F),C(G),D(H(M),I,J)))122.若干術語——即上層的那個結點(直接前驅)——即下層結點的子樹的根(直接后繼)——同一雙親下的同層結點（孩子之間互稱兄弟）——即雙親位于同一層的結點（但并非同一雙親）——即從根到該結點所經分支的所有結點——即該結點下層子樹中的任一結點ABCGEIDHFJMLK根葉子森林有序樹無序樹——即根
6、結點(沒有前驅)——即終端結點(沒有后繼)——指m棵不相交的樹的集合(例如刪除A后的子樹個數)雙親孩子兄弟堂兄弟祖先子孫——結點各子樹從左至右有序，不能互換（左為第一）——結點各子樹可互換位置。132.若干術語（續(xù)）——即樹的數據元素及其分支——結點掛接的子樹數（有幾個直接后繼就是幾度。）結點結點的度結點的層次終端結點分支結點樹的度樹的深度(或高度)ABCGEIDHFJMLK——從根到該結點的層數（根結點算第一層）——即度為0的結點，即葉子——即度不為0的結點（也稱為內部結點）——所有結點度中的最大值（Max{各結點的度}）——指所有結點中最大的層數（Ma
7、x{各結點的層次}）問：右上圖中的結點數＝；樹的度＝；樹的深度＝133414ABCDEFGHIJKLM結點A的度：3結點B的度：2結點M的度：0葉子：K，L，F，G，M，I，J結點A的孩子：B，C，D結點B的孩子：E，F結點I的雙親：D結點L的雙親：E結點B，C，D為兄弟結點K，L為兄弟樹的度：3結點A的層次：1結點M的層次：4樹的深度：4結點F，G為堂兄弟結點A是結點F，G的祖先153.樹的邏輯結構(特點)：一對多（1:n），有多個直接后繼（如家譜樹、目錄樹等等），但只有一個根結點，且子樹之間互不相交。4.樹的存儲結構討論1：樹是非線性結構，該怎樣存儲？
8、————仍然有順序存儲、鏈式存儲等方式。16討論3：樹的鏈式存儲方
