iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 10
0

https://ithelp.ithome.com.tw/upload/images/20181025/20111557HMxkU90pRg.jpg
https://ithelp.ithome.com.tw/upload/images/20181025/20111557YJPwsCiXLy.jpg

分得出來兩張圖片的差別嗎?
第一張,我們稱為 樹 (Tree) ,第二張是所謂的迴路,屬於一般的無相圖。

樹有幾個特性:

  • 不包含迴路。
  • 一棵樹中的任意兩個節點有且僅唯一的一條路徑連通。
  • 一棵樹如果有 n 個節點,那一定恰好有 n-1 條邊。
  • 在一棵樹中加一條邊將會構成一個迴路。如上面的第二張圖。

https://ithelp.ithome.com.tw/upload/images/20181025/20111557LYZQNoz7vX.jpg

樹的結構名稱:

  • 節點:圖上的每個點。
  • 根:又稱根節點或祖先,一棵樹只有一個根節點,沒有父節點的就稱為根節點。如圖的 1 號。
  • 葉節點:如果節點不能往下延伸,便稱為葉節點。例如 4、5、6、7 號。
  • 父節點:如果節點能往下沿伸其他節點,那此節點就稱為父節點。例如 2 是 4 和 5 號的父節點。
  • 子節點:承接父節點的節點,就稱子節點。例如 4 和 5 號是 2 號的子節點。
  • 深度:每一個節點都有深度,第一層從根節點開始算起。例如 4 號的深度是 3。

了解了什麼是基本的樹,明天繼續來討論最著名的二元樹。


上一篇
[資料結構] 堆疊 (Stack) - 2
下一篇
[資料結構] 二元樹 (Binary Tree)
系列文
30天學演算法和資料結構31

尚未有邦友留言

立即登入留言