本文已收錄於專欄 🌳《畫解資料結構》🌳

前言

  「 資料結構 」 和 「 演演算法 」 是密不可分的，兩者往往是「 相輔相成 」的存在，所以，在學習 「 資料結構 」 的過程中，不免會遇到各種「 演演算法 」。
  資料結構 常用的操作一般為：「 增 」「 刪 」「 改 」「 查 」。
  這篇文章，作者將用 「 X張動圖 」 來闡述一種 「 樹形 」 的資料結構

「 二元樹 」

  這篇文章的主要目的是講解二元樹的一些基礎概念，以及和二元樹相關的一些經典遍歷演演算法。但是實際學習過程還是需要看個人的毅力和堅持。下圖代表的是 LeetCode 經典的二元搜尋樹的題集，其中樹是很重要的一個章節，涉及了諸多演演算法，希望可以供讀者參考和學習。

點選我跳轉末尾 獲取 粉絲專屬 《演演算法和資料結構》原始碼。

一、樹的概念

1、樹的定義

1）樹

  樹是 $n(n\ge 0)$ 個結點的有限集合。當 $n>0$ 時，它是一棵非空樹，滿足如下條件：
    1）有且僅有一個特定的結點，稱為根結點 $Root$；
    2）除根結點外，其餘結點分為 $m$ 個互不相交的有限集合 $T_1$、$T_2$、$\dots \dots$、$T_m$，其中每一個 $T_i(1\le i\le m)$ 又是一棵樹，並且為 根結點 $Root$ 的子樹。如圖所示，代表的是一棵以 $a$ 為根結點的樹。

2）空樹

  當 $n=0$，也就是 $0$ 個結點的情況也是樹，它被稱為空樹。

3）子樹

  樹的定義用到了遞迴的思想。即樹的定義中還是用到了樹的概念，如圖所示，$T_1$ 和 $T_2$ 就是結點 $a$ 的子樹。結點 $d$、$g$、$h$、$i$ 組成的樹又是結點 $b$ 的子樹等等。

  子樹的個數沒有限制，但是它們一定是互不相交的，如下圖所示的就不是樹。因為在這兩個圖中，$a$ 的子樹都有相交的邊。

2、結點的定義

  樹的結點包含一個 資料域 和 $m$ 個 指標域 用來指向它的子樹。結點的種類分為：根結點、葉子結點、內部結點。結點擁有子樹的個數被稱為 結點的度。樹中各個結點度的最大值被稱為 樹的度。

1）根結點

  一棵樹的根結點只有一個。

2）葉子結點

  度為 0 的結點被稱為 葉子結點 或者 終端結點。葉子結點的不指向任何子樹。

3）內部結點

  除了根結點和葉子結點以外的結點，被稱為內部結點。

  如上圖所示，紅色結點 為根結點，藍色結點 為內部結點，黃色結點 為葉子結點。

3、結點間關係

1）孩子結點

  對於某個結點，它的子樹的根結點，被稱為該結點的 孩子結點。

  如上圖所示，黃色結點 d 是 紅色結點 b 的孩子結點。

2）父結點

  而該結點被稱為孩子結點的 父結點。

  如上圖所示，藍色結點 a 是 紅色結點 b 的父結點。

3）兄弟結點

  同一父結點下的孩子結點，互相稱為 兄弟結點。

  如上圖所示，綠色結點 c 和 紅色結點 b 互為兄弟結點。

4、樹的深度

  結點的層次從根結點開始記為第 1 層，如果某結點在第 $i$ 層，則它的子樹的根結點就在 第 $i+1$ 層，樹中結點的最大層次稱為 樹的深度。
  如下圖所示，代表的是一棵深度為 4 的樹。

5、森林的定義

  森林是 $m$ 棵 互不相交的樹的集合，對於樹的每個結點而言，其子樹集合就是森林。
  如圖所示，$b$ 和 $c$ 兩棵子樹組成的集合就是一個森林。

二、樹的表示法

1、父親表示法

1）儲存方式

  除了根結點以外，樹上的每個結點都會 有且僅有 一個父結點。所以，我們可以將每個結點定義成結構體，總共兩個成員：資料域 和 父結點域。並且把每個結點連續的儲存到結構體陣列中， 父結點域 指向的是陣列下標，當沒有父結點時，值為 $-1$。

2）原始碼詳解

#define MAXN 1024          // (1)
#define DataType int       // (2)
typedef struct  {
    DataType data;         // (3)
    int parent;            // (4)
}TreeNode; 

typedef struct  {
    TreeNode nodes[MAXN];  // (5)
    int root;              // (6)
    int n;                 // (7)
}Tree;

• $(1)$ MAXN代表了最多允許的結點數量；
• $(2)$ DataType表示結點 資料域 的型別；
• $(3)$ data代表了樹結點TreeNode的 資料域；
• $(4)$ parent代表了樹結點的 父結點域，它是Tree這個結構體中nodes[]陣列的下標；
• $(5)$ nodes[MAXN]儲存了樹的所有結點，是一個陣列，可以通過下標進行索引；
• $(6)$ root代表了這棵樹的 根結點 的下標；
• $(7)$ n代表當前有多少 樹結點；

3）圖片剖析

  下圖代表了一棵完整的樹，[0]代表第 0 號結點，它的資料域為 $a$，其中 0 為陣列下標；[1]代表第 1 號結點，它的資料域為 $b$，以此類推。

  結構體陣列儲存如下：

下標	data	parent
0	$a$	$-1$
1	$b$	$0$
2	$c$	$0$
3	$d$	$1$
4	$e$	$2$
5	$f$	$2$
6	$g$	$3$
7	$h$	$3$
8	$i$	$3$

4）結構剖析

  這種儲存結構中，通過結點獲取 父結點 的時間複雜度為 $O(1)$。但是，如果想要知道某個結點有哪些孩子結點，則必須遍歷整棵樹才行。

2、孩子表示法

1）儲存方式

  父親表示法無法知道某個結點有哪些孩子結點，所以我們可以對它進行一個改進，將 孩子結點 儲存下來，並且需要記錄下每個結點有幾個孩子結點。
  也就是說，我們可以對每個結點定義成結構體，總共四個成員：資料域、孩子結點數量域、孩子結點陣列。

2）原始碼詳解

typedef struct  {
    DataType data;
    int childCount;     // (1)
    int childs[MAXN];   // (2)
}TreeNode; 

• $(1)$ childCount記錄下當前這個結點有多少個孩子結點；
• $(2)$ childs[i]則代表第 $i$ 個孩子結點在Tree的結點列表nodes[]中的下標；

3）圖片剖析

  同樣是這樣一棵樹，[0]代表第 0 號結點，它的資料域為 $a$，其中 0 為陣列下標；[1]代表第 1 號結點，它的資料域為 $b$，以此類推。

  得到的結構體陣列如下：

下標	data	childCount	childs
0	$a$	$2$	$[1,2]$
1	$b$	$1$	$[3]$
2	$c$	$2$	$[4,5]$
3	$d$	$3$	$[6,7,8]$
4	$e$	$0$	$[]$
5	$f$	$0$	$[]$
6	$g$	$0$	$[]$
7	$h$	$0$	$[]$
8	$i$	$0$	$[]$

4）結構剖析

  這種儲存結構中，通過結點獲取 孩子結點 的均攤時間複雜度為 $O(1)$。但是，如果想要知道某個結點有的父結點是哪個，則必須遍歷整棵樹才行。
  所以，我們一般可以將 父親表示法 和 孩子表示法 混用，這樣，在知道某個結點的情況下，都能快速得到它的 父結點 和 子結點。
  但是這種表示法的空間時間複雜度為 $O(n^2)$，當 $n$ 較大時，並不是很友好。

3、左兒子右兄弟

1）儲存方式

  對於任意一棵樹，每個結點的 第一個孩子結點 如果存在就一定是唯一的，它的 右兄弟結點 如果存在也是唯一的。因此，對於每個結點，我們可以設定兩個域，分別代表 第一個孩子結點 和 右兄弟結點。

2）原始碼詳解

typedef struct  {
    DataType data;
    int left;     // (1)
    int right;    // (2)
}TreeNode; 

• $(1)$ left代表該結點的 第一個孩子結點 在Tree的結點列表nodes[]中的下標；
• $(2)$ right代表該結點的 右兄弟結點 在Tree的結點列表nodes[]中的下標；；

3）圖片剖析

  還是這樣一棵樹，[0]代表第 0 號結點，它的資料域為 $a$，其中 0 為陣列下標；[1]代表第 1 號結點，它的資料域為 $b$，以此類推。

  得到的結構體陣列如下（其中 $-$ 代表空）：

下標	data	left	right
0	$a$	$1$	$-$
1	$b$	$3$	$2$
2	$c$	$4$	$-$
3	$d$	$6$	$-$
4	$e$	$-$	$5$
5	$f$	$-$	$-$
6	$g$	$-$	$7$
7	$h$	$-$	$8$
8	$i$	$-$	$-$

4）結構剖析

  這種結構，解決了空間時間複雜度的問題，當知道某個結點時，首先存取 $left$ 結點，然後一直存取 $right$ 結點直到空，就能獲取當前結點的所有孩子結點。如果想獲取 父結點，可以再增加一個parent父結點域。
  這種表示法的另外一個好處是：將任意的樹轉換成了二元樹。這樣就可以利用二元樹的性質來處理這棵樹了。
  二元樹才是本文的重點，接下來重點介紹二元樹的內容。

三、二元樹的概念

1、二元樹的性質

  二元樹是一種樹，它有如下幾個特徵：
    1）每個結點最多 2 棵子樹，即每個結點的孩子結點個數為 0、1、2；
    2）這兩棵子樹是有順序的，分別叫：左子樹 和 右子樹；
    3）如果只有一棵子樹的情況，也需要區分順序，如圖所示：

  $b$ 為 $a$ 的左子樹；

  $c$ 為 $a$ 的右子樹；

2、特殊二元樹

1）斜樹

  所有結點都只有左子樹的二元樹被稱為左斜樹。

  所有結點都只有右子樹的二元樹被稱為右斜樹。

  斜樹有點類似線性表，所以線性表可以理解為一種特殊形式的樹。

2）滿二元樹

  對於一棵二元樹，如果它的所有根結點和內部結點都存在左右子樹，且所有葉子結點都在同一層，這樣的樹就是滿二元樹。

  滿二元樹有如下幾個特點：
    1）葉子結點一定在最後一層；
    2）非葉子結點的度為 2；
    3）深度相同的二元樹，滿二元樹的結點個數最多，為 $2^h-1$（其中 $h$ 代表深度）。

2）完全二元樹

  對一棵具有 $n$ 個結點的二元樹按照層序進行編號，如果編號 $i$ 的結點和同樣深度的滿二元樹中的編號 $i$ 的結點在二元樹中位置完全相同，則被稱為 完全二元樹。

  滿二元樹一定是完全二元樹，而完全二元樹則不一定是滿二元樹。
  完全二元樹有如下幾個特點：
    1）葉子結點只能出現在最下面兩層。
    2）最下層的葉子結點一定是集中在左邊的連續位置；倒數第二層如果有葉子結點，一定集中在右邊的連續位置。
    3）如果某個結點度為 1，則只有左子樹，即 不存在只有右子樹 的情況。
    4）同樣結點數的二元樹，完全二元樹的深度最小。

  如下圖所示，就不是一棵完全二元樹，因為 5 號結點沒有右子樹，但是 6 號結點是有左子樹的，不滿足上述第 2 點。

3、二元樹的性質

  接下來我們來看下，二元樹有哪些重要的性質。

1）性質1

  【性質1】二元樹的第 $i(i\ge 1)$ 層上至多有 $2^{i-1}$ 個結點。

  既然是至多，就只需要考慮滿二元樹的情況，對於滿二元樹而言，當前層的結點數是上一層的兩倍，第一層的結點數為 1，所以第 $i$ 的結點數可以通過等比數列公式計算出來，為 $2^{i-1}$。

2）性質2

  【性質2】深度為 $h$ 的二元樹至多有$2^h-1$ 個結點。

  對於任意一個深度為 $h$ 的二元樹，滿二元樹的結點數一定是最多的，所以我們可以拿滿二元樹進行計算，它的每一層的結點數為 $1$、$2$、$4$、$8$、…、$2^{h-1}$。
  利用等比數列求和公式，得到總的結點數為：
$$1+2+4+...+2^{h-1}=2^h-1$$

3）性質3

  【性質3】對於任意一棵二元樹 $T$，如果葉子結點數為 $x_0$，度為 2 的結點數為 $x_2$，則$$x_0=x_2+1$$

  令 $x_1$ 代表度 為 1 的結點數，總的結點數為 $n$，則有：
$$n=x_0+x_1+x_2$$
  任意一個結點到它孩子結點的連線我們稱為這棵樹的一條邊，對於任意一個非空樹而言，邊數等於結點數減一，令邊數為 $e$，則有：
$$e=n-1$$

  對於度為 1 的結點，可以提供 1 條邊，如圖中的黃色結點；對於度為 2 的結點，可以提供 2 條邊，如圖中的紅色結點。所以邊數又可以通過度為 1 和 2 的結點數計算得出：$$e=x_1+2x_2$$  聯立上述三個等式，得到：$$e=n-1=x_0+x_1+x_2-1=x_1+2x_2$$  化簡後，得證：
$$x_0=x_2+1$$

4）性質4

  【性質4】具有 $n$ 個結點的完全二元樹的深度為 $\lfloor lo{g}_{2}n\rfloor +1$。

  由【性質2】可得，深度為 $h$ 的二元樹至多有$2^h-1$ 個結點。所以，假設一棵樹的深度為 $h$，它的結點數為 $n$，則必然滿足：
$$n\le 2^h-1$$  由於是完全二元樹，它一定比深度為 $h-1$ 的結點數要多，即：
$$2^{h-1}-1<n$$  將上述兩個不等式，稍加整理，得到：
$$2^{h-1}\le n<2^h$$  然後，對不等式兩邊取以2為底的對數，得到： $$h-1\le lo{g}_{2}n<h$$  這裡，由於 $h$ 一定是整數，所以有：$$h=\lfloor lo{g}_{2}n\rfloor +1$$

四、二元樹的儲存

1、順序表儲存

  二元樹的順序儲存就是指利用陣列對二元樹進行儲存。結點的儲存位置即陣列下標，能夠體現結點之間的邏輯關係，比如父結點和孩子結點之間的關係，左右兄弟結點之間的關係 等等。

1）完全二元樹

  來看一棵完全二元樹，我們對它進行如下儲存。

  編號代表了陣列下標的絕對位置，對映後如下：

下標	0	1	2	3	4	5	6	7	8	9	10	11	12
$data$	$-$	$a$	$b$	$c$	$d$	$e$	$f$	$g$	$h$	$i$	$j$	$k$	$l$

  這裡為了方便，我們把陣列下標為 0 的位置給留空了。這樣一來，當知道某個結點的下標 $x$，就可以知道它左右兒子的下標分別為 $2x$ 和 $2x+1$；反之，當知道某個結點的下標 $x$，也能知道它父結點的下標為 $\lfloor \frac{x}{2}\rfloor$。

2）非完全二元樹

  對於非完全二元樹，只需要將對應不存在的結點設定為空即可。

  編號代表了陣列下標的絕對位置，對映後如下：

下標	0	1	2	3	4	5	6	7	8	9	10	11	12
$data$	$-$	$a$	$b$	$c$	$d$	$e$	$f$	$g$	$-$	$-$	$-$	$k$	$l$

3）稀疏二元樹

  對於較為稀疏的二元樹，就會有如下情況出現，這時候如果用這種方式進行儲存，就比較浪費記憶體了。

  編號代表了陣列下標的絕對位置，對映後如下：

下標	0	1	2	3	4	5	6	7	8	9	10	11	12
$data$	$-$	$a$	$b$	$c$	$d$	$-$	$-$	$g$	$h$	$-$	$-$	$-$	$-$

  於是，我們可以採取連結串列進行儲存。

2、連結串列儲存

  二元樹每個結點至多有兩個孩子結點，所以對於每個結點，設定一個 資料域 和 兩個 指標域 即可，指標域 分別指向 左孩子結點 和 右孩子結點。

typedef struct TreeNode {
    DataType data;
    struct TreeNode *left;   // (1)
    struct TreeNode *right;  // (2)
}TreeNode;

• $(1)$ left指向左孩子結點；
• $(2)$ right指向右孩子結點；

五、二元樹的遍歷

  二元樹的遍歷是指從根結點出發，按照某種次序依次存取二元樹中的所有結點，使得每個結點存取一次且僅被存取一次。
  對於線性表的遍歷，要麼從頭到尾，要麼從尾到頭，遍歷方式較為單純，但是樹不一樣，它的每個結點都有可能有兩個孩子結點，所以遍歷的順序面臨著不同的選擇。
  二元樹的常用遍歷方法有以下四種：前序遍歷、中序遍歷、後序遍歷、層序遍歷。
  我們用 void visit(TreeNode *root)這個函數代表存取某個結點，這裡為了簡化問題，存取結點的過程就是列印對應資料域的過程。如下程式碼所示：

void visit(TreeNode *root) {
    printf("%c", root->data);
}

1、 前序遍歷

1）演演算法描述

  【前序遍歷】如果二元樹為空，則直接返回。否則，先存取根結點，再遞迴前序遍歷左子樹，再遞迴前序遍歷右子樹。

  前序遍歷的結果如下：$abdghcefi$。

2）原始碼詳解

void preorder(TreeNode *root) {
    if(root == NULL) {
        return ;            // (1)
    }
    visit(root);            // (2)
    preorder(root->left);   // (3)
    preorder(root->right);  // (4)
}

• $(1)$ 待存取結點為空時，直接返回；
• $(2)$ 先存取當前樹的根；
• $(3)$ 再前序遍歷左子樹；
• $(4)$ 最後前序遍歷右子樹；

2、 中序遍歷

1）演演算法描述

  【中序遍歷】如果二元樹為空，則直接返回。否則，先遞迴中序遍歷左子樹，再存取根結點，再遞迴中序遍歷右子樹。

  中序遍歷的結果如下：$gdhbaecif$。

2）原始碼詳解

void inorder(TreeNode *root) {
    if(root == NULL) {
        return ;            // (1)
    }
    inorder(root->left);    // (2)
    visit(root);            // (3)
    inorder(root->right);   // (4)
}

• $(1)$ 待存取結點為空時，直接返回；
• $(2)$ 先中序遍歷左子樹；
• $(3)$ 再存取當前樹的根；
• $(4)$ 最後中序遍歷右子樹；

3、 後序遍歷

1）演演算法描述

  【後序遍歷】如果二元樹為空，則直接返回。否則，先遞迴後遍歷左子樹，再遞迴後序遍歷右子樹，再存取根結點。

  後序遍歷的結果如下：$ghdbeifca$。

2）原始碼詳解

void postorder(TreeNode *root) {
    if(root == NULL) {
        return ;            // (1)
    }
    postorder(root->left);  // (2)
    postorder(root->right); // (3)
    visit(root);            // (4)
}

• $(1)$ 待存取結點為空時，直接返回；
• $(2)$ 先後序遍歷左子樹；
• $(3)$ 再後序遍歷右子樹；
• $(4)$ 再存取當前樹的根；

4、 層序遍歷

1）演演算法描述

  【層序遍歷】如果二元樹為空，則直接返回。否則，依次從樹的第一層開始，從上至下逐層遍歷。在同一層中，按從左到右的順序對結點逐個存取。

  層序遍歷就是一個廣度優先搜尋，對廣搜有興趣的小夥伴，可以參考如下文章：夜深人靜寫演演算法（十）- 單向廣搜。

---

  關於 二元樹 的內容到這裡就結束了。如果還有不懂的問題，可以 「 通過作者電腦版主頁 」找到作者的「 聯絡方式 」 ，隨時線上溝通。
  有關🌳《畫解資料結構》🌳 的原始碼均開源，連結如下：《畫解資料結構》

---

  相信看我文章的大多數都是「 大學生 」，能上大學的都是「 精英 」，那麼我們自然要「 精益求精 」，如果你還是「 大一 」，那麼太好了，你擁有大把時間，當然你可以選擇「 刷劇 」，然而，「 學好演演算法 」，三年後的你自然「 不能同日而語 」。
  那麼這裡，我整理了「 幾十個基礎演演算法 」 的分類，點選開啟：

🌌《演演算法入門指引》🌌
  如果連結被遮蔽，或者有許可權問題，可以私聊作者解決。
  大致題集一覽：

  為了讓這件事情變得有趣，以及「 照顧初學者 」，目前題目只開放最簡單的演演算法 「 列舉系列 」 （包括：線性列舉、雙指標、字首和、二分列舉、三分列舉），當有 一半成員刷完 「 列舉系列 」 的所有題以後，會開放下個章節，等這套題全部刷完，你還在群裡，那麼你就會成為「 夜深人靜寫演演算法 」專家團 的一員。
  不要小看這個專家團，三年之後，你將會是別人 望塵莫及 的存在。如果要加入，可以聯絡我，考慮到大家都是學生， 沒有「 主要經濟來源 」，在你成為神的路上，「 不會索取任何 」。

---

🔥讓天下沒有難學的演演算法🔥
C語言免費動漫教學，和我一起打卡！ 🌞《光天化日學C語言》🌞
入門級C語言真題彙總 🧡《C語言入門100例》🧡
幾張動圖學會一種資料結構 🌳《畫解資料結構》🌳
組團學習，抱團生長 🌌《演演算法入門指引》🌌
競賽選手金典圖文教學 💜《夜深人靜寫演演算法》💜

粉絲專屬福利

語言入門：《光天化日學C語言》(範例程式碼)
語言訓練：《C語言入門100例》試用版
資料結構：《畫解資料結構》原始碼
演演算法入門：《演演算法入門》指引
演演算法進階：《夜深人靜寫演演算法》演演算法模板

  

👇🏻 驗證碼 可通過搜尋下方 公眾號 獲取👇🏻