iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 18
0
自我挑戰組

學習資料結構30天系列 第 18

[Data Structure][Tree] - Definition

Review

今天要講的資料結構是Tree,在Day10介紹Spanning tree,已經有簡略過Tree的定義了。

樹 Tree

沒有環路的連通圖

  • Tree是一種類似現實生活中樹幹和樹枝的非線性資料結構
  • 在CS中,我們通常將樹畫成顛倒的,樹根在上面,樹葉在下面
  • 非線性,且階層式的方式儲存資料
  • ex: 比賽賽程、公司職位圖、家族族譜

https://ithelp.ithome.com.tw/upload/images/20181101/20112438PcUueQe3e1.jpg

樹的構成

  1. 有根樹 Rooted tree : 在資料結構中的樹稱為Rooted tree。
  2. 樹根 Root : 樹中會有一個特別的節點為root,root通常畫在樹的最上面。
  3. 子樹 Subtree : Root會包含0個或多個subtree,通常畫在root的下面。

以上圖(祖譜)為例子,整個祖譜就是rooted tree,而祖父就是root,此root包含3個subtree,分別是以父母為root和姑姑姑丈為root及叔叔阿姨為root的subtree。
在從父母為root的subtree往下看,又分為兒子和女兒兩個subtree。

  • 由此可以知道,Rooted tree 就是從 root 一直遞迴下去,直到沒有subtree的節點。

樹狀結構 (示意圖)

https://ithelp.ithome.com.tw/upload/images/20181102/20112438IjGHB0wyPQ.jpg

名詞

  • 樹的節點分成兩類:
    1. 內部節點 internal node : 有Subtree的節點。又可以說是non-terminal node 或 branch。
      ex : 圖中的A點、B點、C點、D點、F點都有Subtree。
    2. 外部節點 external node : 沒有Subtree的節點。又可以說是terminal node 或是 leaf。
      ex : 圖中的E點、G點、H點、I點都沒有Subtree。
  • 節點的關係
    1. 父節點 parent node : parent node 在 child node的上面。
      ex : 圖中的A點是B點、C點的parent node。
    2. 子節點 child node : child node 在 parent node的下面。
      ex : 圖中的B點、C點是A點的child node。
    3. 兄弟節點 siblings : 擁有同一個 parent node 的節點。
      ex : 圖中的B點、C點是 siblings。
  • 階度 Level
    • 第1階 : Root
    • 第2階 : Root的child node。
    • 第3階 : Root的child node的child node。
    • .....以此類推。
  • 高度 Height : tree 的最大 level。
    ex : 上圖的樹的height = 4 。
  • 森林 Forest : 一個圖形裡有兩棵或兩顆以上的tree。

參考

細談資料結構 第六版
ISBN 978-986-312-014-8


林明進老師:「可以成為一顆大樹,就不要只作一片葉子。」


上一篇
[Data Structure][Graph] - AOE Network!
下一篇
[Data Structure][Tree] - Binary Tree
系列文
學習資料結構30天30

尚未有邦友留言

立即登入留言