前言

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

「 二叉樹 」

??這篇文章的主要目的是講解二叉樹的一些基礎概念，以及和二叉樹相關的一些經典遍歷演算法，但是實際學習程序還是需要看個人的毅力和堅持，下圖代表的是 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）存盤方式

??對于任意一棵樹，每個結點的 第一個孩子結點 如果存在就一定是唯一的，它的 右兄弟結點 如果存在也是唯一的，

• 如果還有不懂的問題，可以通過 「 博客主頁 」找到作者的「 聯系方式 」 ，線上溝通交流，

• 有關🌳《畫解資料結構》🌳 的原始碼均開源，鏈接如下：《畫解資料結構》

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《畫解資料結構》🌳
閉關刷 LeetCode，劍指大廠Offer！ 🌌《LeetCode 刷題指引》🌌
LeetCode 太簡單？演算法學起來！ 💜《夜深人靜寫演算法》💜