---
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. 每個**節點的值必須要不同**

### 靜態

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 元樹可以更省去空間

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

### 中序走訪

... //接續 LinkedBinary
	void inOrder(BinaryNode b) {
		if(b != null) {
			inOrder(b.left);
			System.out.println("Now Data is " + b.value);
			inOrder(b.right);
		}
	}

**--實作--**
> 

### 前序走訪

... //接續 LinkedBinary
	void preOrder(BinaryNode b) {
		if(b != null) {
			System.out.println("Now Data is " + b.value);
			preOrder(b.left);
			preOrder(b.right);
		}
	}

**--實作--**
> 

### 後續走訪

... //接續 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
> 

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. 左右子樹都是二元樹

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
> 

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: `資料結構`