登入
首頁 所有文章 資料結構 樹—樹狀結構的基本名詞與介紹
長也   2018-03-05 21:02:05(1年前)    523點閱   0喜歡  0收藏
樹—樹狀結構的基本名詞與介紹  

樹狀結構

樹是由節點(node)與邊(edge)所組成的集合。包含一個特殊的節點樹根(root),其餘節點分成n個集合,每個集合都是一棵樹。

 

  1. 節點(node)與邊(edge):節點是某項資料,邊則是與其他節點的分支。如A為一節點,則他的分支為B與C
  2. 祖先與子孫節點:若節點X有通往節點K之路徑,則X是K的祖先,K是X的子孫。以上圖為例,A有一路徑可到G,則A是G的祖先,G是A的子孫。樹根則是所有節點的祖先,而所有節點都是樹根的子孫。
  3. 父節點(parent node)與子節點(children node):某X節點直接到Y節點,則Y稱為X的子節點,X稱為Y的父節點。上圖為例,A為B.C的父節點,B.C為A的子節點。
  4. 兄弟節點:有相同父節點的子節點。如上圖B與C都有一父節點A,則B與C稱為兄弟節點。
  5. 終結節點、樹葉節點(leaf node):沒有子節點的節點之稱。途中G、F、I皆為樹葉節點。與之相反的則為非終結節點,是有子節點的節點之稱。
  6. 分支度(degree):一節點所擁有的子節點數目。如圖中A節點分支度為2,C節點分支度為1,B節點分支度為2,若問此樹之分支度,則取最大值2。
  7. 階度(level):樹中節點世代之關係,一代為一階度,樹根之階度為1。

樹林(forest)

一顆樹若移除樹根,將成為樹林。如上圖若移除節點A,則將形成兩顆樹林。

樹的表示方法

除了畫成上圖,也可以使用(A(B(G,F),C(I)))方法表示。

節點的結構

一個節點儲存之欄位長度取決於該節點的分支度

data link1 link2 link3 …… link n

 

若一顆樹的分支度為k,節點數為n,則此樹需要nk個link欄位。

本文作者:長也

糾結與想不開的資管系學生,之前常碰PHP,現在常碰到的是Python,閒暇之餘就記錄一些筆記。

             

如要發表回覆,請先 登入

  0則回覆