## 資結筆記｜二元樹（Binary Tree）

### 複習

  上次提到了[堆疊（stack)](https://hackmd.io/@fooox0864/SyOcueZukx)這個資料結構，如果還沒有看或是感興趣的讀者可以去看看唷！

<br/>

### 基本觀念

&emsp;&emsp;<font color="#0000FF">二元樹</font>（Binary Tree）是一種樹狀的資料結構，每個節點可以儲存3筆資料，包含數據本身（data）、左指標（left）、右指標（right）。見下圖

&emsp;&emsp;在樹狀結構中最上方的是<font color="#0000FF">根節點</font>（root node），每個節點最多可以有兩個子節點，這兩個子節點可以用左指標和右指標連結，如果一個節點沒有子節點稱為<font color="#0000FF">葉節點</font>（leaves node），見下圖
&emsp;&emsp;所謂的<font color="#0000FF">子節點</font>是指從同一個節點延伸出來的節點，以上圖為例，點7和點10是從點9延伸出來的，那我們就會稱點7和點10為點9的子節點，而點9為它們的<font color="#0000FF">父節點</font>，點7和點10互為<font color="#0000FF">兄弟節點</font>。

<br/>

### 建立二元樹

建立二元樹需遵守以下兩個規則

1. 先建立根節點
2. 接著插入的新數據，如果數據比目前的節點大，則向右邊節點送，若比目前小則向左邊節點送，直到送到的位置沒有子節點則建立該節點

接著只要不斷重複規則2即可完成二元樹的建立，見下圖

假設我們要建立的數據為12、8、9、3、10、4

（1）建立根節點
（2）8<12，向左
（3）9<12，向左；9>8，向右
（4）10<12，向左；10>8，向右；10>9，向右
（5）4<12，向左；4<8，向左；4>3，向右
以上這顆二元樹就建立完成

<br/>

### 刪除二元樹節點

二元樹刪除節點會遇到以下三種情況

<br/>

#### 一、刪除的是葉節點

這種情況因為沒有子節點，所以<font color="#0000FF">直接刪除</font>即可。

<br/>

#### 二、所刪除的節點有1個子節點

這種情況也很單純，將欲刪除的節點刪除，並將它原本的子節點移動到它的位置<font color="#0000FF">取代它</font>，就完成了。

<br/>

#### 三、所刪除的節點有2個子節點

有2種方法可以使用我們用下面這張圖舉例

**方法一**：從<font color="#0000FF">左子樹</font>找最<font color="#f00">大</font>節點

<br/>

&emsp;&emsp;以上圖為例，假設我們要刪除的是<font color="#0000FF">節點8</font>，8的左子樹里最大的是<font color="#0000FF">節點4</font>，將4移動到原先8的位置就可以了，另外如果節點4下面也有子節點，則<font color="#0000FF">重複執行</font>刪除節點的步驟就可以了。

<br/>

**方法二**：從<font color="#0000FF">右子樹</font>找最<font color="#f00">小</font>節點

<br/>

&emsp;&emsp;一樣以上圖為例，假設我們要刪除的是<font color="#0000FF">節點8</font>，從節點8的右子樹中，最小的是節點9，我們將節點9取代節點8的位置就完成了，一樣如果要移上去的節點下也有子節點，則<font color="#0000FF">重複執行</font>刪除節點的步驟。

<br/>

### 搜尋二元樹的數據

&emsp;&emsp;搜尋二元樹節點的方式跟插入有點像，從根節點開始和要找的節點比大小，目標節點如果比較大，就向右子節點走，如果較小，就向左子節點走。見圖
假設到最後沒有找到相同的子節點，則代表這個數據不存在。

<br/>

### 二元樹的分類

<br/>

#### 二元樹的階層（level）與深度（depth）

通常根節點稱為第一層然後向下延伸，見下圖


&emsp;&emsp;而深度則是該子節點與根節點的最短距離，depth = level - 1，以上圖舉例，節點5的階層是第4層，深度為3。另外，在二元樹中每 i 層最多有 $2^n$ 個節點，其中 n= i - 1

<br/>

#### 滿二元樹（full binary tree）

&emsp;&emsp;滿二元樹是指除了葉節點沒有子節點外，其餘每個節點皆有2個子節點，見下圖

<br/>

#### 完全二元樹（complete binary tree）

&emsp;&emsp;完全二元樹是指除了最深層外，每個節點都是滿的，最深一層可以從左到右連續有節點，不可以中斷，見下圖。

上面的這三棵樹都符合，下面的是不符合的
這樣有理解完全二元樹的概念嗎～至於為什麼會存在這種分類就與資料儲存有關

<br/>

#### 完美二元樹（perfect binary tree）

&emsp;&emsp;完美二元樹是指除了最深層的節點外，所有子節點都是滿的，見下圖


<br/>

#### 平衡二元樹（balanced binary tree）

&emsp;&emsp;平衡二元樹是指，每兩個節點的子節點深度相差小於等於1，見下圖
&emsp;&emsp;以這顆二元樹為例，以節點12為基準，左子樹深度3右子樹深度2，相差1
&emsp;&emsp;接著我們以節點9為基準，左子樹深度1，右子樹深度2，相差1，你可以檢查每一個節點，下方連結到的左右子樹的深度相差小於等於1，這棵樹就是平衡二元樹。接著我們舉一個不合格的例子
&emsp;&emsp;以節點12為基準，左子樹深度3，右子樹深度1，左右子樹相差2，不符合平衡二元樹的標準。

<br/>

### 二元樹的列印方式

<br/>

#### 中序（inorder）列印

所謂的中序列印分為以下3個步驟

（1）從左子樹往下走，直到無法前進就處理此節點

（2）接著處理此節點的父節點

（3）接著往右子樹走，若右子樹無法前進則回到上一層

以這張圖為例


&emsp;&emsp;大家可以跟著數字走，數字變為紅色則列印出這個數字你會得到以下數列 9 10 12 14 17 19 剛好是由小排到大，另外中序列印因為處理的順序是左子樹（left, L）根節點（root, D）右子樹（right, R）所以簡稱為LDR。

<br/>

#### 前序（preorder）列印

前序列印是走到哪就列印到哪，遍歷的順序是往左子樹走直到無法前進，接著往右走，以這張圖為例
&emsp;&emsp;因為走到哪就處理到哪所以蠻簡單的，使用前序列印出來的結果是 12 9 10 17 14 19 而又因為處理的順序是先根節點、左子樹、右子樹，所以縮寫為DLR。

<br/>

#### 後序（postorder）列印

&emsp;&emsp;後序列印跟前序不同在於，根節點留到最後處理，先處理左子樹，在處理右子樹，當這個節點的兩個子節點處理完成後，再處理該節點，見下圖


&emsp;&emsp;使用後序列印出來的結果是 10 9 14 19 17 12 因為處理的順序是先左子樹、右子樹、根節點，所以縮寫為LRD

<br/>

### 二元樹的時間複雜度

<br/>

| 時間複雜度比較 | 陣列（未排序） | 二元樹 |
| ---------- | -------- | -------- |
| 搜尋 | $O(n)$ | $O(logn)$ |

<br/>

| 時間複雜度比較 | 陣列（已排序） | 二元樹 |
| ---------- | -------- | -------- |
| 搜尋 | $O(log n)$ | $O(n)$ |
| 插入 | $O(n)$ | $O(n)$ |
| 刪除 | $O(n)$ | $O(n)$ |

<br/>

以上大概介紹完二元樹的概念了（累，因為這個主題有點龐大所以實作的部分留待後續在補，另外平衡二元樹在增減節點時，會遇到需要旋轉以維持樹的平衡，也請留待筆者後續補充。