Chapter-5---教师与职员个人网页FTP空间伺服器(PWS).pptVIP

Chapter 5 樹狀結構 樹狀結構 - 定義 樹狀結構包含：樹根(root)、節點(node)、樹葉(leaf) A為樹根，分別與B、C、D相連接。從A到L稱為節點，共有11個節點。 每個節點都有父節點(樹根除外) 每個節點的下一個節點稱為子節點 同一個高度的節點稱為兄弟節點 尾端的樹葉稱為外部節點或終端節點 一棵樹除了樹葉外其餘為內部節點或非終端節點。 去除樹根，其餘稱為子樹，這些子樹構成一個”森林”，一個節點擁有的子樹數目稱為”分支度”。 樹狀結構-階度(高度) 像是人類的族譜，祖父母到孫子一共三代；在樹狀結構是以「階度、高度」來表示 樹狀結構 - 樹的串列表示法 樹狀結構的串列表示法： (A(B(E，F)，C，D(G(K)，H，I(L)))) 樹的記憶體表示法： 一般化串列節點結構表示法： (A(B(E，F)，C，D(G(K)，H，I(L)))) 樹狀結構 - 二元樹(Binary Tree) 樹狀結構每個節點的分支度沒有固定，處理不便。 二元樹為一個樹根與兩個以下的分支所構成的樹狀結構，二元樹的節點結構為 二元樹的分支度為一左一右，左子樹與右子樹。順序上通常小的置於左子樹，大的置於右子樹，因此二元樹又稱為有序樹。 樹與二元樹： 樹的子樹之間沒有順序關係，二元樹有。 樹至少要有一個樹根，不可以為空集合，二元樹可以。 樹的分支度大於等於 0，而二元樹的分支度小於等於 2 及大於等於 0。 樹狀結構-二元樹的特性 高度為1，節點只有樹根A，節點數為1；高度為2，節點數為3(A,B,C)；高度為3，節點數為7(A,B,C,D,E,F,G)。以此類推，高度為n，最大節點數為2n-1，數學式為：20+21+22+23+…+2n-1=(2n-1)/(2-1)=2n-1 第一高度有一個節點(A)，第二高度有二個節點(B,C)，第三高度有四個節點(D,E,F,G)，則第m高度的節點數目最多有2m-1個。 樹葉總數等於分支度2的節點總數加一。 結論： 高度為n的二元樹，其最大的節點數為2n-1 高度為n的二元樹，第m高度的節點樹目最多有2m-1個(其中n≧m) 非空的二元樹，若樹葉總數為n0，且分支度2的節點總數為n2，則n0=n2+1 例題 page174 樹狀結構-歪斜樹(Skewed Tree) 當二元樹只有在左邊的節點上或是只有在右邊的節點上，稱為歪斜樹。只有左子樹，稱為左歪斜樹；只有右子樹，稱為右歪斜樹。 樹狀結構-完整二元樹(Complete Binary Tree) 若二元樹的高度為n，節點依出現順序排成二元樹，且節點總數≦2n-1，此種二元樹稱為完整二元樹。若節點總數為m，則此完整二元樹的高度為log2m +1。 樹狀結構-完滿二元樹(Full Binary Tree) 若二元樹的高度為n，節點依出現順序排成二元樹，而且節點總數等於 2n-1，此種二元樹稱為完滿二元樹。若二元樹為完滿二元樹，節點總數為m，則此完滿二元樹的高度為log2(m+1)。 節點總數滿足log2(m+1)等於整數為完滿二元樹，否則為非完滿二元樹。該整數即為二元樹高度。 例題 page177 樹狀結構-二元樹的儲存表示法 二元樹儲存方式可用陣列和鏈結串列來表示。 循序陣列表示法： 將二元樹視為一個完滿二元樹，依節點的階度依序存放入記憶體內。 二元樹的儲存表示法 二元搜尋樹(binary search tree)為二元樹，具下列性質： 左子樹節點的值小於(≦)根節點的值 右子樹節點的值大於(≧)根節點的值 左、右子樹仍為二元搜尋樹 例題 ko5_1 樹狀結構-二元樹的儲存表示法 鏈結串列表示法： 陣列表示法較鏈結串列表示法浪費記憶體空間。 例題 ko5_2，例題page 184, 185 樹狀結構-二元樹的追蹤 二元樹的追蹤就是拜訪二元樹的每一個節點。 假設L、D、R分別代表節點的左子樹、資料、右子樹，依據二元樹由左而右追蹤的特性，會有三種情況：LDR(中序追蹤 inorder traversal)、LRD(後序追蹤 postorder traversal)、DLR(前序追蹤 preorder traversal)。 樹的種類 最小加權外路徑長度二元樹 加權代表兩個節點間的距離或價錢。 外長度路徑是指由樹根到每個外節點的路徑長度之總和；內路徑長度是指由樹根到每個內節點的路徑長度之總和。 假設有n個節點，每個外節點(長度或距離為k)均設有一加權數q，則此二元樹的加權外路徑長度等於： see Fig5-38(page 210) Huffman碼see Fig5-3 (page 210) Huffman解碼樹：see page 211~213 例題@page 213 最佳二元搜尋樹：指所有二元