樹的走訪：寬度優先走訪（BFS）、深度優先走訪（DFS）
樹（Tree）演算法的筆記
-7 min read走訪的意思是，從根節點開始，逐個走訪各個節點，不同的拜訪順序，在程式碼的實作有很大的落差。
依照走訪原則，可以分為兩種：
- 寬度優先走訪 Breadth-First Tree Traversal
- 深度優先走訪 Depth-First Tree Traversal(PreOrder, InOrder, PostOrder)
一、寬度優先走訪 Breadth-First Tree Traversal
寬度優先的概念其實很簡單，從根開始，同一層都先走訪完之後，再進入下一層：如圖：level 1 的 1 開始，走訪完後進入 level 2 走訪 2, 3，再進入 level 走訪 4, 5, 6, 7。
以上圖為例，這個樹狀圖有四層，分別為 第一層: 2 第二層: 7, 5 第三層: 2, 10, 6, 9 第四層: 5, 11, 4
走訪的順序就會是： 2, 7, 5, 2, 10, 6, 9, 2, 11, 4
用 JavaScript 實作寬度優先走訪
實作一個 BFTT 函式，input 為 Tree，output 為依照 寬度優先走訪 的順序組成 result 陣列。
有一個 Tree，每個節點都叫做 TreeNode，TreeNode 有兩個屬性 value 與 children，value 為數字，children 為 TreeNode 陣列或是 null。
Tree Node 型別
/** * @typedef { Object } TreeNode * @property { number } value * @property { Array[TreeNode] | null } * /Tree
const tree = { value: 2, children: [ { value: 7, children: [ { value: 2, children: null }, { value: 10, children: null }, { value: 6, children: [ { value: 5, children: null }, { value: 11, children: null }, ], }, ], }, { value: 5, children: [ { value: 9, children: [ { value: 4, children: null } ], }, ], }, ],};思路
一層層遍歷 children，存進 queue，然後依照 queue 的特性：先進先出，從 queue 內排序第一的開始處理，處理完則離開 queue。
function BFTT(root) { const result = [] const queue = [] queue.push(root) const traversal = (tree) => { result.push(tree.value) const subTree = tree.children if (subTree) { for (let i = 0; i < subTree.length; i++) queue.push(subTree[i]) } } while (queue.length !== 0) { traversal(queue[0]) queue.shift() } return result}const result = BFTT(tree)console.log(result)// [2, 7, 5, 2, 10, 6, 9, 2, 11, 4];二、Depth-First Tree Traversal（深度優先走訪）
深度優先走訪 根據每個 subTree 的走訪順序，又可以區分為三種：Pre-Order、In-Order、Post-Order。
1. Pre-Order
先遇到的節點先處理。
順序：root, left, right
從圖片中可以看到從根節點 F 開始，藍色為走訪順序，若顯示紅色則為無法再走下去的情況，這時就會則回到上一層繼續走訪，直到沒辦法再繼續下去。
實作方法：先遇到的節點先走訪，並採用遞迴方式，若有 left, right 節點則繼續遞迴。
function preOrder(root) { const result = [] const traversal = (node) => { result.push(node.value) if (node.left) traversal(node.left) if (node.right) traversal(node.right) } traversal(root) return result}// PreOrder: ["F", "B", "A", "D", "C", "E", "G", "I", "H"]2. In-Order
順序： left, root, right
從圖片中可以看到從根節點 F 開始，藍色為走訪順序，若該節點為目前最左邊的節點，則推入 Inorder 陣列中；若顯示紅色則為無法再走下去的情況，這時就會則繼續尋找最左邊的節點，直到沒辦法再繼續下去。
實作方法：越左的節點先走訪，並採用遞迴方式，若有 left, right 節點則繼續遞迴。
function InOrder(root) { const result = [] const traversal = (node) => { if (node.left) traversal(node.left) result.push(node.value) if (node.right) traversal(node.right) } traversal(root) return result}// // ["A", "B", "C", "D", "E", "F", "G", "H", "I"];3. Post-Order
順序：left, root, right
從圖片中可以看到從根節點 F 開始，藍色為走訪順序，若該節點為目前最左邊的節點，則推入 Postorder 陣列中，若找不到最左節點，就會將右邊的節點推入；若顯示紅色則為無法再走下去的情況，這時就會則繼續尋找，直到沒辦法再繼續下去。
實作方法：越左的節點先走訪，並採用遞迴方式，若有 left, right 節點則繼續遞迴。
function PostOrder(root) { const queue = [] const traversal = (node) => { if (node.left) traversal(node.left) if (node.right) traversal(node.right) queue.push(node.value) } traversal(root) return queue}// ['A', 'C', 'E', 'D', 'B', 'H', 'I', 'G', 'F']