# [資演] 9- 樹
###### tags: `資演`
現在我們要進入資結的重頭戲之一：**樹（tree）**。
前面我們學的都是所謂的**線性資料結構**。這是什麼意思呢？之前我們考慮的都是直直一串下去的東西，例如linked list，一個串著一個，一直連接下去，沒有任何分支，只有一條路徑，所以稱為線性資料結構。
如果我們想在資料結構裡面加入分支，那就必須使用**非線性**的資料結構。例如我們今天要介紹的樹，就是一種非線性的資料結構。
## 什麼是樹？
想想我們在現實生活中看到的樹，很少是直直一根長上去的，通常都有一些分岔的樹枝；並且通常在樹枝的末端會有葉子。
樹這種資料結構像是一個上下顛倒的樹，具有上下階層：
要了解樹這種資料結構，我們必須先介紹幾個樹的術語：
* 節點（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，有時候我們會暱稱為左小孩和右小孩。
當然，有左小孩和右小孩自然就會有左子樹和右子樹，也就是以左小孩和右小孩為根節點的子樹。
有一種特別的二元樹稱為**歪斜樹**（**skewed tree**）。這種樹看起來和linked list相當類似：
其中左歪斜樹只有左小孩，右歪斜樹只有右小孩，而這兩種樹是不一樣的樹。
另一個極端就是**完滿二元樹**（full binary tree）：
如果一個完滿二元樹的高度是$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
$$
如果一個二元樹的所有節點都有兩個子節點，但它並不是完滿二元樹，如下圖所示：
這種樹稱為完整二元樹（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
```
和linked list的狀況類似，我們甚至可以不定義一個樹的類別，只要有一個root來表示這棵樹即可，因為從這個root可以一代一代帶出所有的後代。
## 二元樹的走訪
樹的traversal有以下幾種：
* Pre-Order（前序）
* In-Order（中序）
* Post-Order（後序）
* Level-Order（層序）
其中，前序、中序和後序對應到的是圖的**深度優先搜尋** （Depth-first Search, **DFS**），層序則是對應到**廣度優先搜尋**（Breath-first Search, **BFS**），這些以後我們會再講到。所謂的前、中、後，指的是根節點對應到的順序：
* 前序：
**根節點** -> 左子樹 -> 右子樹
* 中序：
左子樹 -> **根節點** -> 右子樹
* 後序：
左子樹 -> 右子樹 -> **根節點**
注意這三種都是先左後右。
而層序走訪概念上相對簡單，只要一層一層的走訪所有節點：
但是在我們的表示方法中，層序走訪非常難以直接實作。以下我們將介紹如何實作前序、中序和後序三種走訪方式。
### 前序走訪 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個子節點都走訪過後才執行處理，顯示節點資料。
### 走訪範例
* 分別以前、中、後序走訪以下二元樹，會得到怎樣的順序呢？
:::spoiler 前序
1 -> 2 -> 4 -> 5 -> 3
:::
:::spoiler 中序
4 -> 2 -> 5 -> 1 -> 3
:::
:::spoiler 後序
4 -> 5 -> 2 -> 3 -> 1
:::
* 再大一點的樹呢？可以參考以下範例：
## 多元樹的二元樹表示法
我們可以用**左小孩右兄弟**（Left-child right-sibling, LCRS）表示法來用二元樹來表示一個多元樹（N-ary tree）。顧名思義，就是在這個表示法的二元樹上，一個節點的左小孩，在原本的樹中是他的小孩，而右小孩在原本的樹中是他的兄弟。以下圖為例，左半邊是原本的樹，右半邊是其LCRS表示法：
注意在LCRS表示法的二元樹的根節點並沒有右子樹，因為根節點沒有兄弟節點。
## 例題
因為樹本身的定義就帶有遞迴的意味，所以我們遇到樹的題目通常可以用遞迴去解。
* 比較兩個二元樹是不是一樣的
:::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`，把這棵二元樹的所有左右子節點交換。
:::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`，檢查這個二元樹是不是對稱的。
:::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
:::
Sign in with Wallet
Connect another wallet