資料結構筆記-樹(Tree)

樹 (Tree) 的名詞介紹

樹 (Tree) 在與 List 不同，屬於非線性的一種資料結構，如下方示意圖。

• Root: 樹的頂端稱為 root。
• Child: A- D Nodes 都是 Root Node 的 Child 。
• Parent: Root Node 是 A-D Nodes 的 Parent 。
• Siblings: A-Node 與 D-Node 位置同屬同一階，互為兄弟 (Siblings)。
• Leaf: B-D Nodes 沒有 Child ，所以稱為 Leaf 。
• Edge: Node 與 Node 之間的連結稱為 Edge 。

樹的常見應用

• HTML DOM
• JSON
• 網路的路由 (Network routing)
• Abstract syntax tree
• 人工智慧 (AI)
• 電腦系統內的資料夾操作系統

二元樹 (Binary tree) 以及二元搜尋樹 (Binary search tree)

樹的種類有許多種，一般常見的樹為二元樹 (每個 Parent Node 至多僅能含有兩個 Children Node，)，其中的二元搜尋樹在搜尋 (Searching) 方面因為速度較快的特性而有廣泛的應用，其結構特性為:

• 每個 Parent Node 至多僅能含有兩個 Children Node 。
• 左方 Child Node 的值比其 Parent Node 小
• 右方 Child Node 的值比其 Parent Node 大

透過JavaScript實現二元搜尋樹 (Binary Search Tree)

樹的每一個節點 (Node) 都含有值 (val) 以及其 Child Node (left 和right) 的性質，且基本的功能包括:

• 插入 (Insert) : 在樹 (Tree) 上新增新的節點。
• 尋找 (Find) : 尋找並回傳在樹 (Tree) 上的節點。

Insert Method (迭代方法)

Insert Method (遞迴方法)

Find Method

二元搜尋樹 (Binary Search Tree) 的時間複雜度

插入 (insert) 以及尋找 (find) 這兩個函式所需要的時間複雜度為 O (log n) ，其中 log 是以 2 為底的對數，因此當資料數量變成兩倍時，插入及搜尋的時間所需要的迭代次數僅會增加一次。

• Insertion - O (log n)
• Searching - O (log n)

需要注意的是二元搜尋樹有個特例，也就是資料結構呈現線性的情況，如下方程式碼，這時候的新增以及尋找的時間複雜度就會變成 O (n) ，倘若資料變成長鏈狀而非樹狀時，就要考慮是否改成線性的資料結構會比較合適。

樹的遍歷 (Tree Traversal)

Tree Traversal 可以透過兩種方式達到，分別是 1. 廣度優先搜尋 (Breadth-first Search, BFS) 以及 2. 深度優先搜尋 (Depth-first Search, DFS)。

假設一開始的樹結構如下圖:

1. 廣度優先搜尋 (Breadth-first Search, BFS):

廣度優先搜尋 (BFS) 會從 Root 開始，針對其每一層的 Child Node 遍歷，遍歷完畢才會進行下一層 Child Node 的遍歷(先進行橫向遍歷，再進行縱向)。

queue 陣列 在 BFS 內的演變如下:

2. 深度優先搜尋 (Depth-first Search, DFS) :

深度優先搜尋 (DFS) 則是以樹的縱向先進行遍歷，而後才是橫向，兩者的時間複雜度是一樣的，然而對於結構較寬的樹而言，廣度優先搜尋會消耗較多的記憶體，而深度優先搜尋則是在結構較深的樹會佔據較多的記憶體。

2-1 深度優先搜尋 (Depth-first Search, DFS) -前序遍歷 (PreOrder)

前序遍歷 (PreOrder) 函式所回傳的陣列，可以用來複製一模一樣的樹結構。

2-2 深度優先搜尋 (Depth-first Search, DFS) -後序遍歷 (PostOrder)

2-3 深度優先搜尋 (Depth-first Search, DFS) -中序遍歷 (InOrder)

中序遍歷 (InOrder) 可以用來回傳已排列的資料。

參考資料

• JavaScript Algorithms and Data Structures Masterclass