---
# System prepended metadata

title: '[資演] 9- 樹'
tags: [資演]

---

# [資演] 9- 樹

###### tags: `資演`

現在我們要進入資結的重頭戲之一：**樹（tree）**。

前面我們學的都是所謂的**線性資料結構**。這是什麼意思呢？之前我們考慮的都是直直一串下去的東西，例如linked list，一個串著一個，一直連接下去，沒有任何分支，只有一條路徑，所以稱為線性資料結構。

如果我們想在資料結構裡面加入分支，那就必須使用**非線性**的資料結構。例如我們今天要介紹的樹，就是一種非線性的資料結構。

## 什麼是樹？
想想我們在現實生活中看到的樹，很少是直直一根長上去的，通常都有一些分岔的樹枝；並且通常在樹枝的末端會有葉子。

樹這種資料結構像是一個上下顛倒的樹，具有上下階層：
![](https://hackmd.io/_uploads/Bk8Gzwue9.png)


![](https://hackmd.io/_uploads/H1SQOb9e5.png)

要了解樹這種資料結構，我們必須先介紹幾個樹的術語：
* 節點（node）
* 邊（edge）
    節點與節點之間的連結稱為邊。
* 根節點 (root)
    最頂端的節點。每個樹只會有一個根節點。一個樹是由一個根節點和其後代所組成。
* 子節點（child node）
* 父節點（parent node）
* 兄弟節點（sibling）
    如圖中所示，L為EFG的父母節點，EFG為L的子節點，EFG互為兄弟關係。每個子節點只能有一個父節點，但一個父節點可以有很多個子節點。
* 子樹（subtree）
    以樹中的子節點作為根節點的樹稱為子樹。例如，圖上虛線框起來的三角形，就是一個子樹。
* 葉節點（leaf node）
    沒有子節點的節點，稱為葉節點。
* 分支度（degree）
    一個節點擁有的子節點數量稱為這個節點的degree。例如，圖中節點L的degree就是3。
* 分支（branch）
    一條從根節點到葉節點的完整路徑稱為分支。每條分支可以看成是一個linked list。
* 高度（height）
    在一個樹裡面最長的分支對應的節點數量稱為這個樹的高度。例如上圖的樹的高度就是5。

## 二元樹
二元樹（binary tree）是每個節點的degree小於或等於2的樹。每個節點最多只會有2個子節點，分別稱為left child和right child，有時候我們會暱稱為左小孩和右小孩。
![](https://hackmd.io/_uploads/rJA6Eqhl5.png)
當然，有左小孩和右小孩自然就會有左子樹和右子樹，也就是以左小孩和右小孩為根節點的子樹。

有一種特別的二元樹稱為**歪斜樹**（**skewed tree**）。這種樹看起來和linked list相當類似：
![](https://hackmd.io/_uploads/B1gII5nlq.png)
其中左歪斜樹只有左小孩，右歪斜樹只有右小孩，而這兩種樹是不一樣的樹。

另一個極端就是**完滿二元樹**（full binary tree）：
![](https://hackmd.io/_uploads/S1xB1s3gq.png)
如果一個完滿二元樹的高度是$h$，那他的節點數必須是$2^h - 1$，這樣才會是滿的。為什麼呢？考慮一個高度$h = 3$的完滿二元樹，這個樹有三個階層，每層的節點數目都是上一層的兩倍：
* 第1階：$1 = 2^{(1-1)}$ 個節點
* 第2階：$2 = 2^{(2-1)}$ 個節點
* 第3階：$4 = 2^{(3-1)}$ 個節點

如果推廣到第$n$階，則在第$n$階會有$2^{(n-1)}$個節點。全部加起來，一個高度為$h$的完滿二元樹的節點數目會是
$$
\sum ^{h}_{i = 1}2^{i-1} = 2^{h} - 1
$$

如果一個二元樹的所有節點都有兩個子節點，但它並不是完滿二元樹，如下圖所示：
![](https://hackmd.io/_uploads/rJ-G7shg5.png)
這種樹稱為完整二元樹（complete binary tree）。一個高度為$h$的完整二元樹，其節點數目會少於$2^{h} - 1$。

:::warning
注意完滿二元樹和完整二元樹的定義可能隨文獻改變，因此在遇到這些名詞時還是以當下使用的文獻的定義為主。
:::

## 二元樹的表示方法
和之前linked list類似地，我們必須先定義一個類別來生成節點：
```
class Node:
    def __init__(self, key):    
        self.left = None
        self.right = None
        self.val = key
```
![](https://hackmd.io/_uploads/r1yJHone5.png)

和linked list的狀況類似，我們甚至可以不定義一個樹的類別，只要有一個root來表示這棵樹即可，因為從這個root可以一代一代帶出所有的後代。

## 二元樹的走訪
樹的traversal有以下幾種：
* Pre-Order（前序）
* In-Order（中序）
* Post-Order（後序）
* Level-Order（層序）

其中，前序、中序和後序對應到的是圖的**深度優先搜尋** （Depth-first Search, **DFS**），層序則是對應到**廣度優先搜尋**（Breath-first Search, **BFS**），這些以後我們會再講到。所謂的前、中、後，指的是根節點對應到的順序：
* 前序：
    **根節點** -> 左子樹 -> 右子樹
* 中序：
    左子樹 -> **根節點** -> 右子樹
* 後序：
    左子樹 -> 右子樹 -> **根節點**
    
注意這三種都是先左後右。

而層序走訪概念上相對簡單，只要一層一層的走訪所有節點：
![](https://hackmd.io/_uploads/H1hsan2xq.png)
但是在我們的表示方法中，層序走訪非常難以直接實作。以下我們將介紹如何實作前序、中序和後序三種走訪方式。
### 前序走訪 Pre-Order traversal
```
def printPreorder(root):
    if root:
        print(root.val) # 造訪根結點
        printPreorder(root.left) # 走訪左子樹
        printPreorder(root.right) # 走訪右子樹
```
前序走訪所走訪到的二元樹節點，就會立刻顯示節點資料，走訪的順序是先向樹的左方走直到無法前進後，才轉往右方走。
### 中序走訪 In-Order traversal
```
def printInorder(root):
    if root:
        printInorder(root.left) # 走訪左子樹
        print(root.val) # 造訪根結點
        printInorder(root.right) # 走訪右子樹
```
中序走訪會先沿著二元樹的左方往下走，直到無法繼續前進後，顯示節點，退回到父節點（因為是子樹的根結點）顯示父節點，然後繼續往右走，如果右方都無法前進，顯示節點，再退回到上一層。
### 後序走訪 Post-Order traversal
```
def printPostorder(root):
    if root:
        printPostorder(root.left) # 走訪左子樹
        printPostorder(root.right) # 走訪右子樹
        print(root.val) # 造訪根結點
```
後序走訪方式剛好和前序走訪相反，它是等到節點的2個子節點都走訪過後才執行處理，顯示節點資料。
### 走訪範例
* 分別以前、中、後序走訪以下二元樹，會得到怎樣的順序呢？
    ![](https://hackmd.io/_uploads/Hk112p2gc.png)
    :::spoiler 前序
    1 -> 2 -> 4 -> 5 -> 3
    :::

    :::spoiler 中序
    4 -> 2 -> 5 -> 1 -> 3 
    :::

    :::spoiler 後序
    4 -> 5 -> 2 -> 3 -> 1
    :::

* 再大一點的樹呢？可以參考以下範例：
![](https://hackmd.io/_uploads/HyYGCThx9.png)

## 多元樹的二元樹表示法
我們可以用**左小孩右兄弟**（Left-child right-sibling, LCRS）表示法來用二元樹來表示一個多元樹（N-ary tree）。顧名思義，就是在這個表示法的二元樹上，一個節點的左小孩，在原本的樹中是他的小孩，而右小孩在原本的樹中是他的兄弟。以下圖為例，左半邊是原本的樹，右半邊是其LCRS表示法：
![](https://hackmd.io/_uploads/Sy0qg0hx5.png)

注意在LCRS表示法的二元樹的根節點並沒有右子樹，因為根節點沒有兄弟節點。


## 例題
因為樹本身的定義就帶有遞迴的意味，所以我們遇到樹的題目通常可以用遞迴去解。
* 比較兩個二元樹是不是一樣的
    ![](https://hackmd.io/_uploads/BJZpPCnl9.png)
    :::spoiler 解答
    這題我們可以用遞迴的方式去做：
    ```
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    
    
    class Solution(object):
        def isSameTree(self, p, q):
            if p and q:
                return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
            else:
                return p == q
    :::
* 翻轉二元樹
    給定一個二元樹的根節點`root`，把這棵二元樹的所有左右子節點交換。
    ![](https://hackmd.io/_uploads/SyRcz0nxq.png)
    :::spoiler 解答
    這題我們一樣可以用遞迴的方式去做：
    ```
    class Solution(object):
        def invertTree(self, root):
            if not root:
                return None
            else:
                x = root
                right = self.invertTree(x.right)
                left = self.invertTree(x.left)
                x.left = right
                x.right = left
                return x
        
    :::
* 對稱的二元樹
    給定一個二元樹的根節點`root`，檢查這個二元樹是不是對稱的。
    ![](https://hackmd.io/_uploads/rk0zVR3gq.png)
    ![](https://hackmd.io/_uploads/rkFmNRne5.png)
    :::spoiler 解答
    這題我們還是可以用遞迴的方式去做：
    ```
    class Solution:
        def isSymmetric(self, root):
            if root is None:
                return True
            else:
                return self.isMirror(root.left, root.right)
    
        def isMirror(self, left, right):
            if left is None and right is None:
                return True
            if left is None or right is None:
                return False
            if left.val == right.val:
                outPair = self.isMirror(left.left, right.right)
                inPair = self.isMirror(left.right, right.left)
                return outPair and inPiar
            else:
                return False
    :::