---
title: 'Tree 樹狀結構'
disqus: kyleAlien
---
Tree 樹狀結構
===
## OverView of Content
如有引用參考請詳註出處，感謝 :smile:
**樹其實是圖 Graph 的一個子類，差異有**
1. 樹是無向的 (沒有方向)
2. 樹的分支是無法連通的
3. 樹沒有循環，末梢節點無法連接到根結點
> **樹狀結構**是==非線性==的資料結構，族譜、籃球比賽、組織圖、平面繪圖應用等等，可有二元、四元、八元樹
> 
[TOC]
## 基本觀念
1. 有`根` (Root) 有`節點` (Node)
2. 節點之間互相連接，但**不可以形成無窮迴圈**
3. 去除根就會變成`樹林`(Forest)，並且與其他樹是`互斥`的
> 
### 樹專有名詞
1. 分支度 (degree): 節點的子樹個數
2. 階度 (level) : 樹的層級
3. 高度 (height) : 最高 level
4. 終端節點 (terminal) : 末梢無分支
> 
## 二元樹
* 在電腦中儲存樹的方式是以鏈結串列 (Linked List) 為主
* 而為何要使用二元樹 ?
> 假設固定每個節點都有相同的分支度，假設 N 元樹每個節點有 M 連接，那此樹就使用了 N\*M 個位子...
> 2 元樹鏈結浪費率為 1/2
> 3 元樹鏈結浪費率為 1/3
> 4 元樹鏈結浪費率為 1/4
>
> 當 2 元樹時它的鏈結浪費率為最低，所以通常都使用 2 元樹
> 
* 二元樹每個節點只能連接 0~2 個分支樹，並且==有次序關係==
* **最大節點總和為 N = 2^K^-1** (K 為階度)，如果節點為 N 可推出**高度 H = log~2~(N+1)** (N 為節點)
### 滿二元樹 (Fully Binary Tree)
* 2^K^-1 (K >= 0)，K 為高度
> 
### 完整二元樹 (Complete)
* **必須依照次序**，由 **==左到右==** 排列
> 
### 歪斜二元樹 (Skewed)
* 只有 left Node or right Node
> 
### 嚴格二元樹 (Strictly)
* 每個非終端節點都有左右節點
> 
## 二元樹建立
* 建立二元樹的規則如下
> 1. 可以是空集合，若不是空結合，Node 上必須有 value
> 2. **left Node < Root < right Node**
> 3. 每個**節點的值必須要不同**
### 靜態
```java=
public class StaticBinaryTree {
public static void main(String[] args) {
int data[] = {6, 3, 5, 9, 7, 8, 4, 2};
for(int i = 0; i < data.length; i++) {
System.out.print("[" + data[i] + "] ");
}
System.out.println();
int[] result = makeBinaryTree(data);
for(int i = 0; i < result.length; i++) {
System.out.print("[" + result[i] + "] ");
}
System.out.println();
}
static int[] makeBinaryTree(int[] source) {
int nodeSize = binarySize(source.length);
System.out.println("Max Node Size is " + nodeSize);
int level;
int[] result = new int[nodeSize];
// 開始遍歷對象
for(int i = 0; i < source.length; i++) {
int putValue = source[i];
//"2. "
for(level = 1; result[level] != 0;) {
int resultValue = result[level];
//"3. "
if(putValue > resultValue) {
level = level * 2 + 1; // odd
} else {
level = level * 2; // even
}
}
result[level] = source[i];
}
return result;
}
//"1. "
static int binarySize(int x) {
return x * 2;
}
}
```
1. 一個節點必定連接兩個，所以需要的空間為 2 倍 (其實只需要 2^k^ -1)
2. `result[level] != 0` 的意思是，將要**放置的變數推送至最尾端再放置 (也就是要在新的陣列中找一個沒有放置過的點)**，放置**按照原本的順序放入**
3. ==放置的指標，以基偶數移動==，移動完後跳出迴圈並放入
> 
* 看靜態 2 元樹的可以看出，會浪費空間在放置 0
**--實作--**
> 
### 動態
* 使用 Linked 建置 2 元樹可以更省去空間
```java=
public class DynamicBinaryTree {
public static void main(String[] args) {
int[] a = {5, 8, 9, 6, 3, 1, 24, 7};
LinkedBinary l = new LinkedBinary(a);
}
}
class BinaryNode {
BinaryNode left;
final int value;
BinaryNode right;
public BinaryNode(int value) {
this.value = value;
}
}
class LinkedBinary {
BinaryNode root;
LinkedBinary(int[] Source) {
for(int i = 0; i < Source.length; i++) {
addToBinary(Source[i]);
}
}
void addToBinary(int data) {
BinaryNode n = new BinaryNode(data);
//"1."
if(root == null) {
root = n;
return;
}
//"2. "
BinaryNode realNode = root;
while(true) { // 找到末端
if(realNode.value > n.value) { // put to left
if(realNode.left != null) {
realNode = realNode.left;
} else {
realNode.left = n;
System.out.println("Put " + n.value + " to " + realNode.value + "'s left");
break;
}
} else { // put to right
if(realNode.right != null) {
realNode = realNode.right;
} else {
realNode.right = n;
System.out.println("Put " + n.value + " to " + realNode.value + "'s right");
break;
}
}
}
}
}
```
1. 建立根節點
2. 從根結點往下，搜尋到最底端 while(true)，在放入資料
> 
**--實作--**
> 
## 遍歷二元樹
* 前、中、後走訪只須==記得樹根==的位子即可，再來就一定是左再右
> 前序 : Root -> Left -> Right
> 中序 : Left -> Root -> Right # 最常使用
> 後續 : Left -> Right -> Root
### 中序走訪
```java=
... //接續 LinkedBinary
void inOrder(BinaryNode b) {
if(b != null) {
inOrder(b.left);
System.out.println("Now Data is " + b.value);
inOrder(b.right);
}
}
```
**--實作--**
> 
### 前序走訪
```java=
... //接續 LinkedBinary
void preOrder(BinaryNode b) {
if(b != null) {
System.out.println("Now Data is " + b.value);
preOrder(b.left);
preOrder(b.right);
}
}
```
**--實作--**
> 
### 後續走訪
```java=
... //接續 LinkedBinary
void postOrder(BinaryNode b) {
if(b != null) {
postOrder(b.left);
postOrder(b.right);
System.out.println("Now Data is " + b.value);
}
}
```
**--實作--**
> 
## 二元運算樹
* [**Stack**](https://hackmd.io/Cq9VpmG7RoORzqPKvAdHuA?view#算術運算式的求值) 也有運算堆疊
* 二元運算樹必須符合兩個規則
> 1. 考慮到運算式中的結合性，優先權，適當的加上**括號**
> 2. 利用運算子當樹根，左邊當左子樹，右邊當右子樹，優先權最低的運算子作為 Root
> > A-B\*(-C -3.5)
> > 1. 加上括號: A-(B*((-C)+(-3.5)))
> > 2. 由 (-C)+(-3.5) 開始往上畫
> > 
## 二元樹進階
二元排序樹、二元搜尋樹、引線二元樹
### 二元排序樹
1. 第一筆資料做為樹根
2. 後續資料與樹根做比較，小於樹根放左子樹，大於樹根放右子樹
* 使用 **==中序走訪==** 後就可以得到，==小 -> 大== 的排序
> Ex: 16, 2, 33, 14, 51, 1, 20, 15, 41
> Ans: 1, 2, 14, 15, 16, 20, 33, 41, 51
> 
```java=
public class TestTree {
public static void main(String[] args) {
int[] list = {16, 2, 33, 14, 51, 1, 20, 15, 41};
SortTree sort = new SortTree(list);
sort.printSort(sort.root);
}
}
class TreeNode {
final int value;
TreeNode left, right;
TreeNode(int value) {
this.value = value;
}
}
class BinaryTree {
TreeNode root;
BinaryTree(int[] list) {
for(int i = 0; i < list.length; i++) {
addNode(list[i]);
}
}
void addNode(int data) {
TreeNode n = new TreeNode(data);
if(root == null) {
root = n;
return;
}
TreeNode temp = root;
while(true) {
if(temp.value > n.value) { // left tree
if(temp.left == null) {
temp.left = n;
break;
} else {
temp = temp.left;
}
} else if (temp.value < n.value) { // right tree
if(temp.right == null) {
temp.right = n;
break;
} else {
temp = temp.right;
}
}
}
}
}
class SortTree extends BinaryTree {
SortTree(int[] list) {
super(list);
}
// 小到大，中序走訪
void printSort(TreeNode temp) {
if (temp != null) {
printSort(temp.left);
System.out.println("value : " + temp.value);
printSort(temp.right);
}
}
}
```
**--實做--**
> 
### 二元搜尋樹
* **搜尋與排序是一體兩面的**，只要依照二元樹的規則走即可
1. 可是空集合，若不是每個 Node 上必須有值
2. 小於樹根放左子樹，大於樹根放右子樹
3. 左右子樹都是二元樹
```java=
public class TestTree {
public static void main(String[] args) {
int[] list = {16, 2, 33, 14, 51, 1, 20, 15, 41};
SearchTree search = new SearchTree(list);
search.findValue(20);
}
}
...// Tree 同上
class SearchTree extends BinaryTree {
SearchTree(int[] list) {
super(list);
}
void findValue(int v) {
if(root == null) {
System.out.println("Tree Empty");
return;
}
int count = 0;
TreeNode temp = root;
while(true) {
if(temp == null) {
System.out.print("Cannot find " + v + "in tree");
break;
}
System.out.println("Times: " + count++);
if(v == temp.value) {
System.out.println("find " + v + " in tree");
break;
} else if (v > temp.value) {
temp = temp.right;
} else if(v < temp.value) {
temp = temp.left;
}
}
}
}
```
**--實做--**
> 
### 引線二元樹 (Threaded Binary Tree)
* 假設有 n 個節點的二元樹，其結點
> 真正有連結的結點為 n - 1 個
> 而沒有連結的結點有 n + 1 個
> > 假設 3 個節點，就有 2 個鏈結，4 個空鏈結
> > 
* 步驟 :
1. 將二元樹由**中序**走法排出，並將所有**空鏈結改為==引線==**
2. 如果引線鏈結指向該節點的左方，將引線指到中序走訪的前一個節點
3. 如果引線鏈結指向該節點的右方，將引線指到中序走訪的後一個節點
4. 如果指向空結點 (頭、尾)，將空結點的右鏈結指向自己
> 紅色為終端節點
> 
* Node 結構修改
> value: 節點資料
> right: 右子樹
> left: 左子樹
> rBit: 右控制位元，當為引線時 rBit = 0
> lBit: 左控制位元，當為引線時 lBit = 0
> 
```java=
class ThreadedNode {
// 該點具體數值
final int value;
// 左右子樹
ThreadedNode right, left;
// 左右引線
boolean lBit, rBit;
ThreadedNode(int value) {
this.value = value;
}
}
```
**--實做--**
>
* 優點
> 1. 通常在二元樹**走訪**時都需要使用堆疊，而**引線二元樹則不須堆疊處理**
> 2. 有效利用每個鏈結，中序走訪時也較省時
> 3. 任一節點都容易找出前後關係
* 缺點
> 1. 加入、刪除實要處理的資料較多，導致速度較慢
> 2. 引線子樹不共享
## 樹 & 二元樹 表示
二元樹只是樹狀結構的特例，廣義的樹狀結構可有多個子節點 (並不限 2 個，一般情況下也並不會只有一種狀況)，但是**二元樹的效率較高，所以將多元樹轉換二元樹就極其重要**
### 樹 & 二元樹轉換
* 樹轉化 -> 二元樹
> 1. 將結點的同梯度 (兄弟) 的連結
> 2. 刪除所有子節點的連接，但保留最左邊的連接
> 3. **平行節點==順時針==轉 45 度**
> 
* 二元樹 -> 樹 (其實就是反向操作)
> 1. **==逆時針轉== 45 度**
> 2. 將所有子節點連接
> 3. 刪除同梯度 (兄弟) 連接線
### 樹林轉換二元樹
分開的樹林也可轉換為二元樹，其方法與樹轉二元樹類似，只是在最初多了一個步驟
* 樹林 -> 二元樹
> 1. **由左至右**將每棵樹的樹根 (root) 連接，這樣就以**最左邊的樹根為全部的根**
> 2. 將結點的同梯度 (兄弟) 的連結
> 3. 刪除所有子節點的連接，但保留最左邊的連接
> 4. **平行節點==順時針==轉 45 度**
> 
* 二元樹 -> 樹林 (反推)
> 1. **==逆時針轉== 45 度**
> 2. 連接所有節點
> 3. 刪除同梯度 (兄弟) 的連結
> 4. 刪除根節點的連接 (就分開為樹林)
### 樹與樹林的走訪
`多元樹` & `樹林`都使用前、中、後序走訪，只是**走訪方法不同**
* ==多元樹走訪==
1. 中序走訪
> a. 先使用**中序走訪 (左根右)** 第一個子樹(B 子樹)
> b. 走訪樹根(A)
> c. 走訪接下來的子樹(C、D 子樹)
> 
> 上圖走訪 : EBFACGDHI
> 記法 : 先走訪其子樹
2. 前序走訪
> a. 訪問樹根 (A)
> b. 以**前序走訪 (根左右)** 依次訪問子樹 (B、C、D)
> 
> 上圖走訪 : ABEFCDGHI
> 記法 : 先走訪樹根，同前序走法
3. 後序走訪
> a. 以**後序走訪 (左右根)** 依次訪問子樹 (B、C、D)
> b. 最後拜訪樹根
> 
> 上圖走訪 : EFBCGHIDA
> 記法 : 先走訪棋子樹
* ==樹林走訪==
其走訪方式與多元樹走訪十分相像，也就是多元樹走訪的衍生
1. 中序走訪
> a. 以中序走訪訪問第一個**樹林的子樹群**
> b. 訪問樹根
> c. 以中序訪再走訪其他樹林
> 記法 : 先走訪其子樹
2. 前序走訪
> a. 顯訪問樹根
> b. 以前序依序走訪其他子樹
> 記法 : 先走訪樹根，同前序走法
3. 後序走訪
> a. 以後序依序走訪全部子樹
> b. 再到序串起樹根
> 記法 : 先走訪其子樹，到序串起樹根
### 唯一二元樹
透過**兩個排序(前、中、後序)的解可以得出唯一的二元樹**
* 排序的解有一個條件**必須**是 ==前、中序== or ==中、後序==，**如果只有++前後序那就無法得出++**
> 依序下列條件就可得出
> 1. 取每個樹中的 **最小節點** 為樹根，切開後左邊放左邊，右邊放右邊 (**不分大小放置左右**)
> 2. 由 **中序走訪** 的結果為準畫出
**--範例--**
> 中序走訪 : CBAEDFG
> 後序走訪 : ABGFCDE
>
> 唯一二元樹 ---- 起始點假設為 A，左右切開
> 
## 最佳化二元搜尋樹
> 在搜尋二元樹時可能有多個二元樹可以使用，而找出**最佳搜尋路徑找尋路徑就十分重要**，也就是找出 **==搜尋成本最低的二元樹==**
### 延伸二元樹 (Extension)
* 若有 N 個節點，就會有 N - 1 個非空節點，N + 1 個空節點，而在這些外節點上添加的節點稱為**外節點**，如下圖
* 畫出後就可以計算出 **內徑長(所有==內節點==到 Root 的總和)**，**外徑長(所有==外節點==到 Root 的總和)**
> 
> 內徑長(A ~ F to Root) : 1 + 2 + 3 + 1 + 2 + 2 = 11
> 外節點(a ~ h to Root) : 2 + 3 + 4 + 3 + 3 + 3 + 3 + 3 = 24
* 如果外部結點是 ==**加權值 (搜尋概率...)**== 就必須合併運算外徑長，使用**加權值 \* 內徑再相加**，又稱為加 **加權外徑長**
> 
> (加權 * 內徑) + ....
> 加權外徑長 : (1 * 1) + (4 * 2) + (6 * 3) + (1 * 3) + (3 * 2) + (8 * 2) + (2 * 2) + (5 * 2) => 1 + 8 + 18 + 3 + 6 + 16 + 4 + 10 = **66**
* 假設有兩個二元樹，互相比較外徑總和，==**最小外徑總和 (or 加權長度最小) 的為最佳二元樹**==
> 上面算出外徑為 24
> > 假設另一二元樹為 36，那上圖的二元樹就是最佳二元樹
> >
### 霍夫曼樹
* 霍夫曼樹經常用於**處理資料壓縮的問題，==根據資料出現的頻率來建構二元樹==**，每個節點都有外部節點，其節點為加權值
> 1. 對每一個節點產生兩個外部節點，並賦予這兩個節點該元素會出現的機率
> 2. 節點 N 有外部節點 T1、T2，**T1、T2 是機率出現最低的節點**，兩個加在一起就是 N 結點出現的機率
> 3. 消除步驟 1 & 2 插入 N，不斷重覆到機率 (權重) 消耗完畢
* 出現機率目前有 0.01、0.04、0.10、0.39、0.16、0.08、0.22，知道機率就可排出霍夫曼樹
> 
> 選重串列剩餘最小的兩個，重複步驟
> 
> 最後可得到結果，並得到 霍夫曼樹
> 
## 平衡樹
> 二元搜尋樹的缺點就是無法保持最佳狀態 (平衡樹)，在**加入資料的排序中時常會出現歪斜樹**，樹加高度增加就會導致效能下降 (權重變高)，所以**保持在平衡樹是最佳狀態**
### 平衡樹定義
* T1 & T2 都是樹，它們的高度分別是 H1 & H2，|H1 - H2| <= 1 就是平衡樹 (最大差距為 1)
> 
## Appendix & FAQ
:::info
:::
###### tags: `資料結構`
Sign in with Wallet
Connect another wallet