二元樹

在電腦科學中，**二元樹**（英語：Binary tree）是每個節點最多只有兩個分支（即不存在分支度大於 2 的節點）的樹結構。通常分支被稱作「左子樹」或「右子樹」。二元樹的分支具有左右次序，不能隨意顛倒。

二元樹的第 $i$ 層至多擁有 $2^{i-1}$ 個節點；深度為 $k$ 的二元樹至多總共有 $2^{\begin{aligned}k+1\end{aligned}}-1$ 個節點（定義根節點所在深度 $k_{0}=0$ ），而總計擁有節點數符合的，稱為「滿二元樹」；深度為 $k$ 有 $n$ 個節點的二元樹，若且唯若其中的每一節點，都可以和深度 $k$ 的滿二元樹，序號 1 到 $n$ 的節點一對一對應時，稱為完全二元樹。對任何一棵非空的二元樹 $T$ ，如果其葉片（終端節點）數為 $n_{0}$ ，分支度為 2 的節點數為 $n_{2}$ ，則 $n_{0}=n_{2}+1$ 。

與普通樹不同，普通樹的節點個數至少為 1，而二元樹的節點個數可以為 0；普通樹節點的最大分支度沒有限制，而二元樹節點的最大分支度為 2；普通樹的節點無左、右次序之分，而二元樹的節點有左、右次序之分。

二元樹通常作為資料結構應用，典型用法是對節點定義一個標記函數，將一些值與每個節點相關聯。這樣標記的二元樹就可以實現二元搜尋樹和二元堆積，並應用於高效率的搜尋和排序。

## 圖論中的定義

二元樹是一個連通的無環圖，並且每一個頂點的度不大於 3。有根二元樹還要滿足根節點的度不大於 2。有了根節點之後，每個頂點定義了唯一的父節點，和最多 2 個子節點。然而，沒有足夠的資訊來區分左節點和右節點。如果不考慮連通性，允許圖中有多個連通分量，這樣的結構叫做森林。

## 性質

二元樹是一個有根樹，並且每個節點最多有 2 個子節點。非空的二元樹，若樹葉總數為 n0，分支度為 2 的總數為 n2，則 n0 = n2 + 1。

## 特殊類型

### 完美二元樹

一棵深度為 k，且有 $2^{\begin{aligned}k\end{aligned}}-1$ 個節點的二元樹，稱為完美二元樹（Perfect Binary Tree）。這種樹的特點是每一層上的節點數都是最大節點數。

#### 性質

對於一棵深度為 $k$ 的完美二元樹：

* 共有 $2^{k}-1$ 個結點
* 結點個數一定為奇數
* 第 $i$ 層有 $2^{i-1}$ 個結點
* 有 $2^{k-1}$ 個葉子

### 完全二元樹

在一顆二元樹中，若除最後一層外的其餘層都是滿的，並且最後一層要麼是滿的，要麼在右邊缺少連續若干節點，則此二元樹為完全二元樹（Complete Binary Tree）。具有 n 個節點的完全二元樹的深度為 $log_{2}n+1$ 。深度為 k 的完全二元樹，至少有 $2^{\begin{aligned}k-1\end{aligned}}$ 個節點，至多有 $2^{\begin{aligned}k\end{aligned}}-1$ 個節點。

## 儲存

在程式設計語言中能用多種方法來構造二元樹。

### 順序儲存表示

二元樹可以用陣列或連結串列來儲存，若是滿二元樹就能緊湊排列而不浪費空間。如果某個節點的索引為 i，（假設根節點的索引為 0）則在它左子節點的索引會是 $2i+1$ ，以及右子節點會是 $2i+2$ ；而它的父節點（如果有）索引則為 _$\left\lfloor {\frac {i-1}{2}}\right\rfloor $_ 。這種方法更有利於緊湊儲存和更好的存取的局部性，特別是在前序遍歷中。然而，它需要連續的儲存空間，這樣在儲存高度為 _h_ 的 _n_ 個節點所組成的一般樹時，將浪費很多空間。在最糟糕的情況下，如果深度為 h 的二元樹其每個節點都只有右孩子，則該儲存結構需要佔用 $2^{h}-1$ 的空間，實際上卻有 h 個節點，浪費了不少空間，是順序儲存結構的一大缺點。

#### 儲存結構

#### 基本操作

### 二元連結串列儲存表示

在使用記錄或記憶體位址指標的程式設計語言中，二元樹通常用樹結點結構來儲存。有時也包含指向唯一的父節點的指標。如果一個結點的子結點個數小於 2，一些子結點指針可能為空值，或者為特殊的哨兵結點。 
使用連結串列能避免順序儲存浪費空間的問題，演算法和結構相對簡單，但使用二元連結串列，由於缺乏父鏈的指引，在找回父節點時需要重新掃描樹得知父節點的節點位址。

#### 儲存結構

#### 基本操作

### 三元連結串列儲存表示

改進於二元連結串列，增加父節點的指引，能更好地實現節點間的存取，不過演算法相對複雜。
當二元樹用三元連結串列表示時，有 N 個結點，就會有 N+2 個空指針。

#### 儲存結構

#### 基本操作

## 遍歷

我們經常希望存取樹中的每一個結點並且檢視它的值。有很多常見的順序來存取所有的結點，而且每一種都有有用的性質。

### 深度優先遍歷

在深度優先順序中，我們希望從根結點存取最遠的結點。和圖的深度優先搜尋不同的是，不需記住存取過的每一個結點，因為樹中不會有環。前序，中序和後序遍歷都是深度優先遍歷的特例。

#### 前（先）序、中序、後序遍歷

遍歷二元樹：L、D、R 分別表示遍歷左子樹、存取根結點和遍歷右子樹，則先 (根) 序遍歷二元樹的順序是 DLR，中 (根) 序遍歷二元樹的順序是 LDR，後 (根) 序遍歷二元樹的順序是 LRD。還有按層遍歷二元樹。這些方法的時間複雜度都是 O (n)，n 為結點個數。

如果 T2 是由有序樹 T 轉換而來的二元樹，那麼 T 中結點的前序就是 T2 中結點的前序，T 中結點的後序就是 T2 中結點的中序。任何一棵二元樹的葉結點在先序、中序和後序遍歷中的相對次序不發改變。設 n,m 為一棵二元樹上的兩個結點，在中序遍歷時，n 在 m 前的條件是 n 在 m 的左方。前序序列和中序序列相同的二元樹為空樹或任一結點均無左孩子的非空二元樹；中序序列和後序序列相同的二元樹為空樹或任一結點均無右孩子的非空二元樹；前序序列和後序序列相同的二元樹為空樹或僅有一個結點的二元樹。

假設我們有一個包含值的 `value` 和指向兩個子結點的 `left` 和 `right` 的樹結點結構。我們可以寫出這樣的過程：

```
visit(node)
    print node.value
    if node.left  != null then visit(node.left)
    if node.right != null then visit(node.right)
```

這樣會用前序列印出樹中的值。在前序，每個結點在存取它的子結點之前存取。類似地，如果列印語句在最後，每個結點在存取他的子節點之後存取，樹中的值會用後序來列印。在這兩種情況中，左子樹中的值比右子樹中得值先列印。

```
visit(node)
    if node.left  != null then visit(node.left)
    print node.value
    if node.right != null then visit(node.right)
```

最後，上面的中序遍歷，每個結點在存取左子樹和右子樹之間存取。這在遍歷二元搜尋樹時很常用，因為它能用遞增的順序來遍歷所有的值。

為什麼呢？如果 _n_ 是二元搜尋樹的結點，那麼 _n_ 的左子樹的所有結點的值都比 n 的值要小，而且 _n_ 的右子樹的所有節點的值都比 n 的值要大。因此，如果我們順序遍歷左子樹，然後存取 _n_，然後順序遍歷右子樹。我們就已經循序存取了整個樹。

後序遍歷虛擬碼如下：

```
visit(node)
    if node.left  != null then visit(node.left)
    if node.right != null then visit(node.right)
    print node.value
```

 
以上的遞迴演算法使用與樹的高度成比例的棧空間。如果我們在每個結點中儲存指向父結點的指標，那樣可以使用反覆運算演算法，只使用常數空間實現所有這些遍歷。然而，指向父結點的指標佔用更多的空間。這只在需要指向父節點的指標或棧空間有限時才使用。例如，
這是一個中序遍歷的反覆運算演算法：

```
visit(root)
    prev    := null
    current := root
    next    := null
    
    while current != null
        if prev == current.parent
            prev := current
            next := current.left
        if next == null or prev == current.left
            print current.value
            prev := current
            next := current.right
        if next == null or prev == current.right
            prev := current
            next := current.parent
        current := next
```

 

### 廣度優先遍歷

和深度優先遍歷不同，廣度優先遍歷會先存取離根節點最近的節點。二元樹的廣度優先遍歷又稱按層次遍歷。演算法藉助佇列實現。

## 轉換自多叉樹

一般有序樹可對映為二元樹，但反之未必成立。

n 叉樹轉換為二元樹的方法：二元樹中結點 x 的左子結點為 n 叉樹中結點 x 的左子結點；二元樹中結點 x 的右子結點為 n 叉樹中結點 x 的第一個右邊的同級結點 y。

二元樹若且唯若根節點沒有右子結點時可轉換為 n 叉樹。

例如，在左邊的樹中，A 有 6 個子結點 {B,C,D,E,F,G}。它能被轉換成右邊的二元樹。

 

* 將一棵樹轉換為二元樹的方法：
1. 在兄弟之間加一連線；
2. 對每個結點，除了其左孩子外，去除其與其餘孩子之間的聯繫；
3. 以樹的根結點為軸心，將整樹順時針轉 45 度。

### 樹的二元連結串列標記法（孩子兄弟標記法）

樹的二元連結串列標記法（孩子兄弟標記法）是樹和二元樹轉換的媒介。

#### 儲存結構

#### 基本操作

## 線索二元樹

線索二元樹（英語：threaded binary tree，保留遍歷時結點在任一序列的前驅和後繼的資訊）：若結點有左子樹，則其 lchild 域指示其左孩子，否則令 lchild 域指示其前驅；若結點有右子樹，則其 rchild 域指示其右孩子，否則令 rchild 指示其後繼。還需在結點結構中增加兩個標誌域 LTag 和 RTag。LTag=0 時，lchild 域指示結點的左孩子，LTag=1 時，lchild 域指示結點的前驅；RTag=0 時，rchild 域指示結點的右孩子，RTag=1 時，rchild 域指示結點的後繼。以這種結點結構構成的二元連結串列作為二元樹的儲存結構，叫做線索連結串列，其中指向結點前驅和後繼的指標叫做線索，加上線索的二元樹稱為線索二元樹。對二元樹以某種次序遍歷使其變為線索二元樹的過程叫做線索化。若對二元樹進行中序遍歷，則所得的線索二元樹稱為中序線索二元樹，線索連結串列稱為為中序線索連結串列。線索二元樹是一種物理結構。

在中序線索樹找結點後繼的規律是：若其右標誌為 1，則右鏈為線索，指示其後繼，否則遍歷其右子樹時存取的第一個結點（右子樹最左下的結點）為其後繼；找結點前驅的規律是：若其左標誌為 1，則左鏈為線索，指示其前驅，否則遍歷左子樹時最後存取的一個結點（左子樹中最右下的結點）為其前驅。 
在後序線索樹中找到結點的後繼分三種情況：

1. 若結點是二元樹的根，則其後繼為空；
2. 若結點是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其後繼即為雙親結點；
3. 若結點是其雙親的左孩子，且其雙親有右子樹，則其後繼為雙親右子樹上按後序遍歷列出的第一個結點。

### 二元線索儲存表示

#### 儲存結構

二元樹的二元線索儲存表示：在線索連結串列上添加一個頭結點，並令其 lchild 域的指標指向二元樹的根結點，其 rchild 域的指標指向中序遍歷時存取的最後一個結點。令二元樹中序序列中的第一個結點的 lchild 域指標和最後一個結點的 rchild 域的指標均指向頭結點，這樣就建立了一個雙向線索連結串列。二元樹常採用二元連結串列方式儲存。

#### 基本操作

## 外部連結

* binary trees（頁面存檔備份，存於網際網路檔案館） entry in the FindStat（頁面存檔備份，存於網際網路檔案館）資料庫
* Gamedev.net introduction on binary trees（頁面存檔備份，存於網際網路檔案館）
* 二元樹歸納證明（頁面存檔備份，存於網際網路檔案館）
* Balanced binary search tree on array How to create bottom-up an Ahnentafel list, or a balanced binary search tree on array（頁面存檔備份，存於網際網路檔案館）
* Binary trees and Implementation of the same with working code examples