Tree 樹
樹（Tree）資料結構的學習筆記
-3 min read
- 由一個或多個節點（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 度，即為二元樹。
芸芸多元樹，皆得簡化成二元樹；區區二元樹，便可描述出多元樹。