# 二元樹(Binary Tree)

在提二元樹之前簡單提一下樹結構，因為這本筆記比較注重實作部分，所以概念的部分建議自己補上。

## 樹結構

> 圖片來源 維基百科 - 樹狀結構

* 在樹狀結構中的基本單位，稱為**節點（Node）**。
* 節點之間的連結，稱為**分支（branch）**。
* 節點與分支形成樹狀，結構的開端，稱為**根（root）**，或根節點。
* 根節點之外的節點，稱為**子節點（child）**。
* 沒有連結到其他子節點的節點，稱為**葉子節點（Leaf）**。

也就是說，雖然稱之為樹，但是其上下顛倒，根節點指的是最上面資料的開頭，而葉子節點是最下面沒有子節點的資料。

### 定義與特性
1. 由 1 個以上的節點所構成的集合，不可為空。
2. 至少有一個特殊節點，稱為根節點。
3. 一個節點可以有多個子節點。
4. 無左右次序。

### 為什麼需要樹結構

我們先來回顧一下之前提到過的儲存方式

#### ⚔【陣列】
* **優點**：可以通過索引訪問元素，速度快，對於有序陣列還可以用二元搜尋找提高搜尋速度。
* **缺點**：當要搜尋具體某個值，或者插入、刪除元素會整體移動，效率較低。
因為陣列大小是固定的，若想要插入新的值，需要陣列擴容：每次在底層都需要創建新陣列，並將原來的陣列數據 copy 回去並插入新的數據。


:::warning
ArrayList 底層維護了一個 `Object[]` 型別的陣列 elementData，所以仍然是進行了陣列擴容。
:::

#### ⚔【鏈結串列】
* **優點**：一定程度上對陣列儲存方式有優化，插入和刪除元素只需要修改鏈結即可。
* **缺點**：在進行搜尋時效率仍然較低，比如要搜尋某個值，需要從頭節點開始遍歷。


:::danger
🌵陣列🌵
- 訪問快
- 插入和刪除效率低

🌵鏈結串列🌵
- 插入刪除效率高
- 搜尋效率低
:::

#### ⚔【樹】

能提高數據存儲、讀取的效率，比如利用二元排序樹(Binary Sort Tree)，既可以保證數據的搜尋速度，同時也可以保證數據的插入、刪除、修改的速度。

**為什麼呢？**

假設我要搜尋 `12` 這個元素的位置，我已經知道根節點為 7 ，我將 12 與 7 比較，發現 12 > 7 所以我只需要往右子樹去找，直接不需要去找左子樹，省下了不少時間。


## 二元樹

Binary Search Tree、Heap、Huffman Tree、BSP Tree這些通通都是二元樹，二元樹的應用相當廣泛，在今年前後端和資料工程師LeetCode 面試調查中一致選出幫助最大的演算法就是二元樹。

樹分很多種，二元樹是每個節點最多只有兩個分支的樹結構，節點左邊稱為左子樹，節點右邊稱為右子樹，二元樹的分支具有左右次序，不能隨意顛倒。

比如有一陣列 `[7, 3, 10, 1, 5, 9, 12]`，我們將 7 設為根節點，比 7 小的放在左子樹，比 7 大的元素放在右子樹，擺放過程如下：


1 < 7 且 1 < 3 放在最左，5 < 7 但 5 > 3 所以放在 3 的右子樹


9 > 7 但 9 < 10 放在 10 的左子樹，12 > 7 也 > 10 放在最右，此時我們的二元樹長成這個樣子：


### 定義與特性
1. 每個節點的分支數 <= 2。
2. 二元樹的節點個數是一個有限集合，或是沒有節點的空集合。二元樹的節點可以分成兩個沒有交集的子樹，稱為「左子樹」(Left Subtree)和「右子樹」(Right Subtree)。
3. 若該二元樹的所有葉子節點都在最後一層，並且節點總數為 `2^n^-1`，n 為層樹，則稱為**完滿二元樹(Full Binary Tree)**。

5. 若該二元樹的所有葉子節點都在最後一層或者倒數第二層，而且最後一層的葉子節點在左邊連續，倒數第二層的葉子節點在右邊連續，稱為**完整二元樹(Complete Binary Tree)**。

> 圖片來源 [資料結構的樹與二元樹](http://wayne.cif.takming.edu.tw/datastru/tree.pdf)

## 二元樹的遍歷

二元樹的遍歷分為三種順序：

* 前序：**先輸出父節點**，再遍歷左子樹和右子樹。
* 中序：先遍歷左子樹，**再輸出父節點**，再遍歷右子樹。
* 後序：先遍歷左子樹，再遍歷右子樹，**最後輸出父節點**。

**小結**：看輸出父節點的順序就能確定是**前序、中序**還是**後序**。

### 思路
1. 創建一顆二元樹
2. **前序遍歷**
2.1 先輸出當前節點(初始的時候是根節點)
2.2 如果左子節點不為空，則遞迴前序遍歷
2.3 如果右子節點不為空，則遞迴前序遍歷
3. **中序遍歷**
3.1 如果當前節點的左子節點不為空，則遞迴中序遍歷
3.2 輸出當前節點
3.3 如果當前節點的右子節點不為空，則遞迴中序遍歷
4. **後序遍歷**
4.1 如果當前節點的左子節點不為空，則遞迴後序遍歷
4.2 如果當前節點的右子節點不為空，則遞迴後序遍歷
4.3 輸出當前節點

### 程式碼實現

有一二元樹如圖所示，我們要對它進行前序、中序、後序遍歷


package BinaryTree;

public class BinaryTreeDemo {
    public static void main(String[] args) throws Exception {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吳用");
        HeroNode node3 = new HeroNode(3, "盧俊義");
        HeroNode node4 = new HeroNode(4, "林沖");
        
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        binaryTree.setRoot(root);

        System.out.println("===前序遍歷===");
        binaryTree.preOrder();
        System.out.println("===中序遍歷===");
        binaryTree.inOrder();
        System.out.println("===後序遍歷===");
        binaryTree.postOrder();
    }
}

class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void preOrder() {
        if(this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二元樹為空");
        }
    }

    public void inOrder() {
        if(this.root != null) {
            this.root.inOrder();
        } else {
            System.out.println("二元樹為空");
        }
    }

    public void postOrder() {
        if(this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二元樹為空");
        }
    }
}

// 先創建 HeroNode 節點
class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;
    public HeroNode(int no,String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode [no = " + no + ", name = " + name + " ]";
    }

    public void preOrder() {
        System.out.println(this);
        if(this.left != null) {
            this.left.preOrder();
        }
        if(this.right != null) {
            this.right.preOrder();
        }
    }

    public void inOrder() {
        if(this.left != null) {
            this.left.inOrder();
        }
        System.out.println(this);
        if(this.right != null) {
            this.right.inOrder();
        }
    }

    public void postOrder() {
        if(this.left != null) {
            this.left.postOrder();
        }
        if(this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }
}

output

===前序遍歷===
HeroNode [no = 1, name = 宋江 ]
HeroNode [no = 2, name = 吳用 ]
HeroNode [no = 3, name = 盧俊義 ]
HeroNode [no = 4, name = 林沖 ]
===中序遍歷===
HeroNode [no = 2, name = 吳用 ]
HeroNode [no = 1, name = 宋江 ]
HeroNode [no = 3, name = 盧俊義 ]
HeroNode [no = 4, name = 林沖 ]
===後序遍歷===
HeroNode [no = 2, name = 吳用 ]
HeroNode [no = 4, name = 林沖 ]
HeroNode [no = 3, name = 盧俊義 ]
HeroNode [no = 1, name = 宋江 ]

### 運算式的二元樹
補充一個運算式的二元樹，使用二元樹前序後序遍歷應該就能快速的得知前綴後綴如何表式。

中綴為：`[((6 + 4) / 2) * (9 + (4 - 3))]`

前序：`* / + 6 4 2 + 9 - 4 3` 即為前綴表示法
後序：`6 4 + 2 / 9 4 3 - + *` 即為後綴表示法

## 二元樹的搜尋
### 思路
#### 前序搜尋
1. 先判斷當前節點的 no 是否等於要搜尋的。
2. 如果相等 返回當前節點。
3. 如果不等，則判斷當前節點的左子節點是否為空，如果不為空，則遞迴前序搜尋。
4. 如果左遞迴搜尋，找到節點則返回，否則繼續判斷，當前節點的右子節點是否為空，如果不空，則繼續向右遞迴前序搜尋。

#### 中序搜尋
1. 判斷當前節點的左子節點是否為空，如果不為空，則遞迴中序搜尋。
2. 如果找到，則返回，如果沒找到就和當前節點比較，如果是則返回當前節點，否則繼續進行右遞迴的中序搜尋。
3. 如果右遞迴中序搜尋，找到就返回，否則返回 null。

#### 後序搜尋
1. 判斷當前節點的左子節點是否為空，如果不為空，則遞迴後序搜尋。
2. 如果找到，則返回，如果沒找到就判斷當前節點的右子節點是否為空，如果不為空則右遞迴進行後序搜尋，如果找到就返回。
3. 就和當前節點進行比較，比如，如果是則返回，否則返回 null。

### 程式碼實現

HeroNode 類別

// 前序遍歷搜尋
public HeroNode preOrderSearch(int no) {
    System.out.println("前序遍歷 1 次"); // 計算遍歷了幾次才找到
    
    if(this.no == no) {
        return this;
    }
    // 1.判斷當前節點的左子節點是否為空, 如果不為空則遞迴前序搜尋
    // 2.如果左遞迴前序搜尋, 找到節點就返回
    HeroNode resNode = null;
    if(this.left != null) {
        resNode = this.left.preOrderSearch(no);
    }

    if(resNode != null) { // 說明左子樹找到
        return resNode;
    }
    // 1.左遞迴前序搜尋, 找到節點就返回, 否則繼續判斷
    // 2.當前節點的右子節點是否為空, 如果不空, 則繼續向右遞迴前序搜尋
    if(this.right != null) {
        resNode = this.right.preOrderSearch(no);
    }
    return resNode;
}

// 中序遍歷搜尋
public HeroNode infixOrderSearch(int no) {
    // 判斷當前節點的左子節點是否為空, 如果不為空則遞迴中序搜尋
    HeroNode resNode = null;
    if(this.left != null) {
        resNode = this.left.infixOrderSearch(no);
    }
    if(resNode != null) { 
        return resNode;
    }
    
    System.out.println("中序遍歷 1 次"); // 計算遍歷了幾次才找到
    // 如果找到則返回, 沒找到就和當前節點比較, 如果是則返回當前節點
    if(this.no == no) {
        return this;
    }

    // 否則繼續右遞迴中序搜尋
    if(this.right != null) {
        resNode = this.right.infixOrderSearch(no);
    }
    return resNode;
}

// 後序遍歷搜尋
public HeroNode postOrderSearch(int no) {
    // 判斷當前節點的左子節點是否為空, 如果不為空則遞迴後序搜尋
    HeroNode resNode = null;
    if(this.left != null) {
        resNode = this.left.postOrderSearch(no);
    }
    if(resNode != null) { 
        return resNode;
    }

    // 否則繼續右遞迴後序搜尋
    if(this.right != null) {
        resNode = this.right.postOrderSearch(no);
    }

    if(resNode != null) { 
        return resNode;
    }
    
    System.out.println("後序遍歷 1 次"); // 計算遍歷了幾次才找到

    if(this.no == no) {
        return this;
    }

    return resNode;
}

BinaryTree 類別

// 前序搜尋
public HeroNode preOrderSearch(int no) {
    if(root != null) {
        return root.preOrderSearch(no);
    } else {
        return null;
    }
}

// 中序搜尋
public HeroNode infixOrderSearch(int no) {
    if(root != null) {
        return root.infixOrderSearch(no);
    } else {
        return null;
    }
}

// 後序搜尋
public HeroNode postOrderSearch(int no) {
    if(root != null) {
        return root.postOrderSearch(no);
    } else {
        return null;
    }
}

試著前序搜尋

System.out.println("~~~前序搜尋~~~");
HeroNode resNode = binaryTree.preOrderSearch(5);
if(resNode != null) {
    System.out.printf("訊息為 no = %d , name = %s\n",resNode.getNo(),resNode.getName());
} else {
    System.out.println("找不到資訊");
}

System.out.println("~~~中序搜尋~~~");
resNode = binaryTree.infixOrderSearch(5);
if(resNode != null) {
    System.out.printf("訊息為 no = %d , name = %s\n",resNode.getNo(),resNode.getName());
} else {
    System.out.println("找不到資訊");
}

System.out.println("~~~後序搜尋~~~");
resNode = binaryTree.postOrderSearch(5);
if(resNode != null) {
    System.out.printf("訊息為 no = %d , name = %s\n",resNode.getNo(),resNode.getName());
} else {
    System.out.println("找不到資訊");
}

output

~~~前序搜尋~~~
前序遍歷 1 次
前序遍歷 1 次
前序遍歷 1 次
前序遍歷 1 次
訊息為 no = 5 , name = 關勝
~~~中序搜尋~~~
中序遍歷 1 次
中序遍歷 1 次
中序遍歷 1 次
訊息為 no = 5 , name = 關勝
~~~後序搜尋~~~
後序遍歷 1 次
後序遍歷 1 次
訊息為 no = 5 , name = 關勝

## 二元樹的刪除

### 要求
1. 如果刪除的節點是葉子節點，則刪除該節點
2. 如果刪除的節點是非葉子節點，則刪除該子樹
3. 測試，刪除掉 5號葉子節點 和 3號子樹

### 思路
1. 考慮如果樹是空樹，或只有一個root節點，則等於將二元樹置空。
2. 因為二元樹是單向的，所以我們是判斷當前節點的子節點是否需要刪除節點，而不能去判斷當前這個節點是不是需要刪除節點。
3. 如果當前節點的左子節點不為空，並且左子節點就是要刪除節點，就將`this.left = null;` 並且就返回(結束遞迴刪除)。
4. 如果當前節點的右子節點不為空，並且右子節點就是要刪除節點，就將`this.right = null;` 並且就返回(結束遞迴刪除)。
5. 如果第三第四步都沒有刪除節點，就需要向左子樹進行遞迴刪除。
6. 如果第五步也沒有刪除節點，則應向右子樹進行遞迴刪除。

首先需要先處理第一點，如果這個二元樹並非空樹或者僅有一個root節點才需要去考慮 2 ~ 6 步。

### 程式碼實現

HeroNode 類加上一個刪除方法

// 遞迴刪除節點
public void delNode(int no) {
    // 如果當前節點的左子節點不為空，並且左子節點就是要刪除節點，就將 this.left = null; 並且就返回(結束遞迴刪除)
    if(this.left != null && this.left.no == no) {
        this.left = null;
        return;
    }
    // 如果當前節點的右子節點不為空，並且右子節點就是要刪除節點，就將this.right = null; 並且就返回(結束遞迴刪除)
    if(this.right != null && this.right.no == no) {
        this.right = null;
        return;
    }
    // 如果前面兩步都沒有刪除節點，就需要向左子樹進行遞迴刪除
    if(this.left != null) {
        this.left.delNode(no);
    }
    // 如果上一步也沒有刪除節點，則應向右子樹進行遞迴刪除
    if(this.right != null) {
        this.right.delNode(no);
    }
}

BinaryTree 類也加上一個刪除方法

// 刪除節點
public void delNode(int no) {
    if(root != null) {
        // 如果只有一個root節點, 需要判斷root是不是就是要刪除的節點
        if(root.getNo() == no) {
            root = null;
        } else {
            // 遞迴刪除
            root.delNode(no);
        }
    } else {
        System.out.println("空樹");
    }
}

來試試刪除葉子節點 和 非葉子節點有什麼區別：

public static void main(String[] args) throws Exception {
    BinaryTree binaryTree = new BinaryTree();
    HeroNode root = new HeroNode(1, "宋江");
    HeroNode node2 = new HeroNode(2, "吳用");
    HeroNode node3 = new HeroNode(3, "盧俊義");
    HeroNode node4 = new HeroNode(4, "林沖");
    HeroNode node5 = new HeroNode(5, "關勝");
    root.setLeft(node2);
    root.setRight(node3);
    node3.setRight(node4);
    node3.setLeft(node5);
    binaryTree.setRoot(root);

    System.out.println("===前序遍歷===");
    binaryTree.preOrder();
    binaryTree.delNode(5);
    System.out.println("===刪除 5 後前序遍歷===");
    binaryTree.preOrder();
    binaryTree.delNode(3);
    System.out.println("===刪除 3 後前序遍歷===");
    binaryTree.preOrder();
}

output

===前序遍歷===
HeroNode [no = 1, name = 宋江 ]
HeroNode [no = 2, name = 吳用 ]
HeroNode [no = 3, name = 盧俊義 ]
HeroNode [no = 5, name = 關勝 ]
HeroNode [no = 4, name = 林沖 ]
===刪除 5 後前序遍歷===
HeroNode [no = 1, name = 宋江 ]
HeroNode [no = 2, name = 吳用 ]
HeroNode [no = 3, name = 盧俊義 ]
HeroNode [no = 4, name = 林沖 ]
===刪除 3 後前序遍歷===
HeroNode [no = 1, name = 宋江 ]
HeroNode [no = 2, name = 吳用 ]