iT邦幫忙

2021 iThome 鐵人賽

DAY 13
0
Software Development

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

【Day13】[資料結構]-二元樹Binary Tree

二元樹(Binary Tree)是最廣泛被使用的樹狀資料結構,簡單來說即為每個節點最多只能有兩個子節點


樹與二元樹不同之處

  • 樹不能是空集合,二元樹可以是空集合。
  • 樹的分支度是 d ≥ 0,二元樹的分支度是 0 ≤ d ≤ 2。
  • 樹的左右沒有次序關係,二元樹的左右有次序關係。

二元樹的種類

  • 完全二元樹(Complete Binary Tree)
    一棵二元樹中,除了最後一層不是滿的,其餘層都是滿的。
    https://ithelp.ithome.com.tw/upload/images/20210924/20121027aY9Df1to3c.jpg
  • 滿二元樹(Fully Binary Tree)
    每一層節點數都是最大節點數量。
    https://ithelp.ithome.com.tw/upload/images/20210924/20121027oDkVmp8hX1.jpg
  • 歪斜樹(Skewed Binary Tree)
    一棵二元樹中,完全沒有左邊或右邊節點,如果集中左邊為「左歪斜樹」,集中右邊為「右歪斜樹」。
    https://ithelp.ithome.com.tw/upload/images/20210924/20121027y5kvvQKd6k.jpg

常見二元樹的實作方式

  1. 陣列表示法
    根節點放在陣列索引位置 0。
    若父節點索引為 i:
    • 父節點的左子節點,放在陣列索引位置 (2 * i) + 1。
    • 父節點的右子節點,放在陣列索引位置 (2 * i) + 2。
    • 若節點不為根節點,節點的父節點放在陣列索引位置 (i - 1) / 2(取商)。

https://ithelp.ithome.com.tw/upload/images/20210924/20121027qtbTbwxGY8.jpg

陣列的介紹可以參考此篇

  1. 鏈結串列表示法
    節點含有兩個指標,左右指標分別指向左邊的子節點右邊的子節點
    https://ithelp.ithome.com.tw/upload/images/20210924/20121027MMrsu27ECV.jpg

鏈結串列的介紹可以參考此篇


上一篇
【Day12】[資料結構]-樹Tree
下一篇
【Day14】[資料結構]-二元樹走訪Binary Tree Traversal
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言