iT邦幫忙

2021 iThome 鐵人賽

DAY 12
0
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 12

【Day12】[資料結構]-樹Tree

樹(Tree)屬於一種非線性結構,是一種上下階層關係,舉例: 組織架構圖、家族譜、賽程表等,類似一棵倒過來的樹,從一個樹根(root)開始向下發展許多節點(node)


樹的特性

  • 不能構成迴路,因此任兩個節點只能有唯一一條邊。
  • 一棵樹若有 n 個節點,一定有 n-1 條邊。
    https://ithelp.ithome.com.tw/upload/images/20210922/20121027KBI9Remgkt.jpg

左圖為一顆正確的樹,右圖的11因為構成迴路所以不是樹。


樹結構名稱

https://ithelp.ithome.com.tw/upload/images/20210922/20121027Ayxh0NIhqa.jpg

  1. Node(節點):每個Tree所連接到的點,都可被稱作這棵樹的Node(節點)。
  2. Root(根節點或樹根):每個Tree最初(或最頂層)的節點,每個Tree都只有一個Root,如: A節點。
  3. Parent(父節點):若該節點有下一層連結節點,則該節點為它的父節點,如: B是E的父節點。
  4. Children (子節點):若該節點有上一層連結節點,則該節點為它的子節點,如: D、E是B的子節點。
  5. Siblings (兄弟節點):有共同的父節點之節點,它們稱為兄弟節點,如: F、G為兄弟節點。
  6. Leaf(葉節點)/ Terminal(終端節點):沒有子節點的節點,如: H、I、E、F、G都是葉節點/終端節點。
  7. Level(階層):該節點所在的水平層級,如: B的階層為2。
  8. Degree (分支度):該節點的子節點總數,如: B的分支度為2。
  9. Depth(深度)/ Height(高度):這棵Tree的總共階層,上圖Tree的深度/高度為4。

上一篇
【Day11】- 遞迴Recursion
下一篇
【Day13】[資料結構]-二元樹Binary Tree
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言