<!--{%hackmd theme-dark %}--> # Binary search tree --- ## 名詞介紹 ---- * 樹(tree) * 節點(node) * 根節點(root) * 父節點(parent) * 子節點(child) * 葉節點(leaf) * 子樹(subtree) ---- <!-- .slide: data-background="#EEEEEE" -->  --- ## 二元搜尋樹 Binary Search Tree ---- 根據維基百科上的定義，我們可以知道； * 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值 * 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值 * 任意節點的左、右子樹也分別為二元搜尋樹 * 沒有鍵值相等的節點 ---- 8 -> 3 -> 10 -> 6 -> 7 -> 14 -> 13 -> 1 -> 4 <!-- .slide: data-background="#EEEEEE" -->  --- ## 遍歷 Traversal --- ## 深度優先遍歷 ### Depth-First Traversal(DFS) ---- ---- ### 前序 Pre-order * 存取根 * 存取左子樹 * 存取右子樹 ---- <!-- .slide: data-background="#EEEEEE" -->  8 -> 3 -> 1 -> 6 -> 4 -> 7 -> 10 -> 14 -> 13 ---- ### 後序 Post-order * 存取左子樹 * 存取右子樹 * 存取根 ---- <!-- .slide: data-background="#EEEEEE" -->  1 -> 4 -> 7 -> 6 -> 3 -> 13 -> 14 -> 10 -> 8 --- ## 廣度優先遍歷 ### Breadth-First Traversal(BFS) ---- * 分層遍歷 ---- <!-- .slide: data-background="#EEEEEE" -->  8 -> 3 -> 10 -> 1 -> 6 -> 14 -> 4 -> 7 -> 13 --- ## 代碼實現 ---- live coding