前言

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

「 二叉樹 」

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

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

一、樹的概念

1、樹的定義

1）樹

??樹是 n ( n ≥ 0 ) n(n \ge 0) n(n≥0) 個結點的有限集合，當 n > 0 n \gt 0 n>0 時，它是一棵非空樹，滿足如下條件：
????1）有且僅有一個特定的結點，稱為根結點 R o o t Root Root；
????2）除根結點外，其余結點分為 m m m 個互不相交的有限集合 T 1 T_1 T1?、 T 2 T_2 T2?、 … … …… ……、 T m T_m Tm?，其中每一個 T i ( 1 ≤ i ≤ m ) T_i (1 \le i \le m) Ti?(1≤i≤m) 又是一棵樹，并且為 根結點 R o o t Root Root 的子樹，如圖所示，代表的是一棵以 a a a 為根結點的樹，

2）空樹

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

3）子樹

??樹的定義用到了遞回的思想，即樹的定義中還是用到了樹的概念，如圖所示， T 1 T_1 T1? 和 T 2 T_2 T2? 就是結點 a a a 的子樹，結點 d d d、 g g g、 h h h、 i i i 組成的樹又是結點 b b b 的子樹等等，

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

2、結點的定義

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

1）根結點

??一棵樹的根結點只有一個，

2）葉子結點

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

3）內部結點

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

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

3、結點間關系

1）孩子結點

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

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

2）父結點

??而該結點被稱為孩子結點的 父結點，

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

3）兄弟結點

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

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

4、樹的深度

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

5、森林的定義

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

二、樹的表示法

1、父親表示法

1）存盤方式

??除了根結點以外，樹上的每個結點都會 有且僅有 一個父結點，所以，我們可以將每個結點定義成結構體，總共兩個成員：資料域 和 父結點域，并且把每個結點連續的存盤到結構體陣列中， 父結點域 指向的是陣列下標，當沒有父結點時，值為 ? 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 ) (1) (1) MAXN代表了最多允許的結點數量；
• ( 2 ) (2) (2) DataType表示結點 資料域 的型別；
• ( 3 ) (3) (3) data代表了樹結點TreeNode的 資料域；
• ( 4 ) (4) (4) parent代表了樹結點的 父結點域，它是Tree這個結構體中nodes[]陣列的下標；
• ( 5 ) (5) (5) nodes[MAXN]存盤了樹的所有結點，是一個陣列，可以通過下標進行索引；
• ( 6 ) (6) (6) root代表了這棵樹的 根結點 的下標；
• ( 7 ) (7) (7) n代表當前有多少 樹結點；

3）圖片剖析

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

??結構體陣列存盤如下：

4）結構剖析

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

2、孩子表示法

1）存盤方式

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

2）原始碼詳解

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

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

3）圖片剖析

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

??得到的結構體陣列如下：

4）結構剖析

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

3、左兒子右兄弟

1）存盤方式

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

2）原始碼詳解

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

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

3）圖片剖析

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

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

4）結構剖析

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

三、二叉樹的概念

1、二叉樹的性質

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

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

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

2、特殊二叉樹

1）斜樹

??所有結點都只有左子樹的二叉樹被稱為左斜樹，

??所有結點都只有右子樹的二叉樹被稱為右斜樹，

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

2）滿二叉樹

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

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

2）完全二叉樹

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

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

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

3、二叉樹的性質

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

1）性質1

??【性質1】二叉樹的第 i ( i ≥ 1 ) i (i \ge 1) i(i≥1) 層上至多有 2 i ? 1 2^{i-1} 2i?1 個結點，

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

2）性質2

??【性質2】深度為 h h h 的二叉樹至多有 2 h ? 1 2^{h}-1 2h?1 個結點，

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

3）性質3

??【性質3】對于任意一棵二叉樹 T T T，如果葉子結點數為 x 0 x_0 x0?，度為 2 的結點數為 x 2 x_2 x2?，則 x 0 = x 2 + 1 x_0 = x_2 + 1 x0?=x2?+1

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

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

4）性質4

??【性質4】具有 n n n 個結點的完全二叉樹的深度為 ? l o g 2 n ? + 1 \lfloor log_2n \rfloor + 1 ?log2?n?+1，

??由【性質2】可得，深度為 h h h 的二叉樹至多有 2 h ? 1 2^{h}-1 2h?1 個結點，所以，假設一棵樹的深度為 h h h，它的結點數為 n n n，則必然滿足：
n ≤ 2 h ? 1 n \le 2^{h}-1 n≤2h?1??由于是完全二叉樹，它一定比深度為 h ? 1 h-1 h?1 的結點數要多，即：
2 h ? 1 ? 1 < n 2^{h-1}-1 \lt n 2h?1?1<n??將上述兩個不等式，稍加整理，得到：
2 h ? 1 ≤ n < 2 h 2^{h-1} \le n \lt 2^h 2h?1≤n<2h??然后，對不等式兩邊取以2為底的對數，得到： h ? 1 ≤ l o g 2 n < h h-1 \le log_2n \lt h h?1≤log2?n<h??這里，由于 h h h 一定是整數，所以有： h = ? l o g 2 n ? + 1 h = \lfloor log_2n \rfloor + 1 h=?log2?n?+1

四、二叉樹的存盤

1、順序表存盤

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

1）完全二叉樹

??來看一棵完全二叉樹，我們對它進行如下存盤，

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

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

2）非完全二叉樹

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

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

3）稀疏二叉樹

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

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

??于是，我們可以采取鏈表進行存盤，

2、鏈表存盤

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

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

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

五、二叉樹的遍歷

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

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

1、 前序遍歷

1）演算法描述

??【前序遍歷】如果二叉樹為空，則直接回傳，否則，先訪問根結點，再遞回前序遍歷左子樹，再遞回前序遍歷右子樹，

??前序遍歷的結果如下： a b d g h c e f i abdghcefi abdghcefi，

2）原始碼詳解

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

• ( 1 ) (1) (1) 待訪問結點為空時，直接回傳；
• ( 2 ) (2) (2) 先訪問當前樹的根；
• ( 3 ) (3) (3) 再前序遍歷左子樹；
• ( 4 ) (4) (4) 最后前序遍歷右子樹；

2、 中序遍歷

1）演算法描述

??【中序遍歷】如果二叉樹為空，則直接回傳，否則，先遞回中序遍歷左子樹，再訪問根結點，再遞回中序遍歷右子樹，

??中序遍歷的結果如下： g d h b a e c i f gdhbaecif gdhbaecif，

2）原始碼詳解

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

• ( 1 ) (1) (1) 待訪問結點為空時，直接回傳；
• ( 2 ) (2) (2) 先中序遍歷左子樹；
• ( 3 ) (3) (3) 再訪問當前樹的根；
• ( 4 ) (4) (4) 最后中序遍歷右子樹；

3、 后序遍歷

1）演算法描述

??【后序遍歷】如果二叉樹為空，則直接回傳，否則，先遞回后遍歷左子樹，再遞回后序遍歷右子樹，再訪問根結點，

??后序遍歷的結果如下： g h d b e i f c a ghdbeifca ghdbeifca，

2）原始碼詳解

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

• ( 1 ) (1) (1) 待訪問結點為空時，直接回傳；
• ( 2 ) (2) (2) 先后序遍歷左子樹；
• ( 3 ) (3) (3) 再后序遍歷右子樹；
• ( 4 ) (4) (4) 再訪問當前樹的根；

4、 層序遍歷

1）演算法描述

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

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

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

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

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

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

粉絲專屬福利

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

??