iT邦幫忙

2021 iThome 鐵人賽

DAY 14
0
Software Development

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

【Day14】[資料結構]-二元樹走訪Binary Tree Traversal

二元樹走訪或稱二元樹遍歷,簡單來說就是走訪樹中各節點,轉化為線性關係


主要分成兩種策略方式

  • 深度優先搜尋(Depth-first Search,DFS)
    從根節點出發,選擇某一子樹並以垂直方向由上到下處理,將其子節點訪問完後,再選擇另一子樹走訪。
  • 廣度優先搜尋(Breath-first Search,BFS)
    從根節點出發,以水平方向由左到右走訪,將同階層的兄弟節點訪問完之後,再走訪下一階層的節點。

深度優先搜尋 DFS

https://ithelp.ithome.com.tw/upload/images/20210925/20121027KNAP2Q2EsN.jpg
假設根結點為N、左子樹為L、右子樹為R

  • 前序走訪(Pre-order Traversal): NLR, 根節點 → 左子樹 → 右子樹
  • 中序走訪(In-order Traversal): LNR, 左子樹 → 根節點 → 右子樹
  • 後序走訪(Post-order Traversal): LRN, 左子樹 → 右子樹 → 根節點

廣度優先搜尋 BFS

https://ithelp.ithome.com.tw/upload/images/20210925/20121027ttoGqdrCdi.jpg

  • 層序走訪(Level-order Traversal): 1234567

以下圖為例

https://ithelp.ithome.com.tw/upload/images/20210925/20121027j1S82bAe4Z.jpg

  1. 前序走訪: 順序是根節點、左子節點、右子節點。
    [1, 2, 4, 8, 9, 5, 3, 6, 10, 11, 7]
  2. 中序走訪: 順序是左子節點、根節點、右子節點。
    [8, 4, 9, 2, 5, 1, 10, 6, 11, 3, 7]
  3. 後序走訪歷: 順序是左子節點、右子節點、根節點。
    [8, 9, 4, 5, 2, 10, 11, 6, 7, 3, 1]
  4. 層序走訪: 順序是由根節點一層一層往下,由左往右。
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

上一篇
【Day13】[資料結構]-二元樹Binary Tree
下一篇
【Day15】[資料結構]-二元搜尋樹Binary Search Tree, BST
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言