Tree 樹

• 由一個或多個節點（node）組成，一個節點也可以稱作樹
• 樹必須有一個唯一的 root 根節點
• 根節點以下的節點集合稱作子樹（subtree）
• 由節點之間的有向連線(edges)組成
• 樹是一種不會循環的圖形

Tree 的應用

• file system

檔案系統就是一種樹狀資料結構的應用，同樣可以適用於廣度優先搜尋法與深度優先搜尋法

下方有 food 根目錄跟 fruit、meat 子目錄與目錄內的 jpg 檔案

food
  |--- fruit
         |--- apple.jpg
         |--- orange.jpg
  |--- meat
         |--- beef.jpg
         |--- pork.jpg

若採用 深度優先搜尋法，只要看到目錄就會進入。進入 food 這個根目錄後，看到 fruit 目錄後，會直接進入並看到 apple.jpg 與 orange.jpg。接著再回到上一層，進入 meat 目錄看到 beef.jpg 與 pork.jpg

若採用 廣度優先搜尋法，進入 food 這個根目錄後，會看完所有的目錄，所以會看到 fruit 目錄與 meat 目錄，再來進入 fruit 目錄內，看到 apple.jpg 與 orange.jpg 檔案。接著再回到上一層，進入 meat 目錄看到 beef.jpg 與 pork.jpg。

• DOM (Document Object Model)

有接觸過網頁前端開發的人應該都有看過這個模型，是由 W3C 提出的瀏覽器的標準化模型，目前主流的瀏覽器皆已按照此模型設計。

Binary Tree

定義：

• 每一個節點最多只有兩個節點，具有方向性，稱作左節點、右節點。
• 符合樹的特性，但根節點必須至少擁有一個左子樹與右子樹。

  Binary Tree 的形容詞

full binary tree ：除了樹葉以外，每個節點都有兩個小孩。

complete binary tree ：各層節點全滿，除了最後一層，最後一層節點全部靠左。

perfect binary tree ：各層節點全滿。同時也是 full binary tree 和 complete binary tree 。

N-ary Tree 多元樹表示法

「多元樹」。分 N 岔的樹，每個節點可以有零個、一個、兩個、 …… 、 N 個小孩。

注意到：多元樹，節點只有一個小孩時，沒有左小孩、右小孩的差別；二元樹，節點只有一個小孩時，有左小孩、右小孩的差別。

Left child-Right sibling representation 左兒子-右兄弟表示法

每個節點中都只有一個最靠左的子節點，以及一個最靠近它的右兄弟。

多元樹重新表示成「左兒子右兄弟」：多元樹的左小孩，是「左兒子右兄弟」的左小孩；多元樹的其餘小孩（左小孩的兄弟），是「左兒子右兄弟」的右小孩、右右小孩、 …… 。

然後將樹往順時針轉 45 度，即為二元樹。

芸芸多元樹，皆得簡化成二元樹；區區二元樹，便可描述出多元樹。

樹的 Big O

參考文章

• 深度優先搜尋(DFS)和廣度優先搜尋(BFS)演算法，實用的節點搜尋法
• Binary Tree - 演算法筆記
• 樹的定義與基本術語