一、樹的概念和結構

1.1 樹的概念

樹是一種非線性的數據結構，它是由 n（n>=0）個有限結點組成一個具有層次關系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

• 有一個特殊的結點，稱為根結點，根節點沒有前驅結點
• 除根節點外，其余結點被分成 M (M>0) 個互不相交的集合T1、T2、……、Tm，其中每一個集合 Ti (1<= i <= m) 又是一棵結構與樹類似的子樹。每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼
• 因此，樹是遞歸定義的。

注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構。

1.2 樹的結構 & 相關名詞解釋

樹中的一些名詞解釋：

• 節點的度：一個節點的子樹 (子節點) 個數稱為該節點的度； 如上圖：A的度為3
• 葉節點 (終端節點)：度為0的節點稱為葉節點； 如上圖：J、F、K、L、H、I 節點為葉節點
• 非終端節點 (分支節點)：度不為0的節點； 如上圖：B、C、D、E、G 節點為分支節點
• 雙親節點 (父節點)：若一個節點有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點
• 孩子節點 (子節點)：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點
• 兄弟節點：具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C、D是兄弟節點
• 樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為3
• 節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
• 樹的高度 (深度)：樹中節點的最大層次； 如上圖：樹的高度為4，空樹的高度是0，只有根節點的樹高度為1
• 堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：F、G互為堂兄弟節點
• 節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先，K的祖先是A、C、G
• 子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。如上圖：所有節點都是A的子孫
• 森林：由 m (m>0) 棵互不相交的樹的集合稱為森林（并查集就是一個森林）

1.3 樹的表示

樹結構相對線性表就比較復雜了，要存儲表示起來就比較麻煩了，既然保存值域，也要保存結點和結點之間的關系。實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法、孩子兄弟表示法等。我們這里就簡單的了解其中最常用的孩子兄弟表示法。

定義樹的結構，首先需要說明樹的度是多少，否則很難去定義。

struct TreeNode
{
    int data; // 數據域
	struct TreeNode* subs[3]; // 此樹的度為3
};

如果沒有說明樹的度是多少，還可以用順序表去存儲。

struct TreeNode
{
    int data; // 數據域
    SeqList subs; // 順序表中存儲的是樹節點指針
    // C++可以這樣寫：vector<struct TreeNode*> subs;
};

再介紹一種雙親表示法，樹的結構中，往下走，孩子節點可能有很多，但往上走，每個節點的雙親結點只有一個。

struct TreeNode
{
    int data; // 數據域
    struct TreeNode* parent; // 記錄該節點的雙親結點
};

上述方法都不是很實用，最實用的表示方法是孩子兄弟表示法。左孩子右兄弟。

typedef int DataType;
struct Node
{
    DataType _data;             // 結點中的數據域
	struct Node* _firstChild;   // 指向第一個孩子結點（即最左邊的孩子節點）
	struct Node* _pNextBrother; // 指向右邊的第一個兄弟結點
};

1.4 樹的應用

表示文件系統的目錄樹結構

二、二叉樹的概念 & 存儲結構（重要）

2.1 二叉樹的概念

一棵二叉樹是結點的一個有限集合，該集合：

由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成，或者為空

觀察上圖，二叉樹的特點：

• 二叉樹不存在度大于2的結點 (每個節點最多有兩個孩子)。
• 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹。

注意：對于任意的二叉樹都是由以下幾種情況復合而成的：

2.2 特殊的二叉樹

滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為 K，且結點總數是 2k - 1 ( 20 + 21 + 22 + … + 2k-1 )，則它就是滿二叉樹。

完全二叉樹：

• 完全二叉樹是效率很高的數據結構。
• 一個深度為 K 的有 n 個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，當且僅當其每一個結點都與深度為 K 的滿二叉樹中編號從 1 至 n 的結點一一對應時稱之為完全二叉樹。注：滿二叉樹是一種特殊的完全二叉樹。
• 前 k 層都是滿的，最后一層不一定滿，但最后一層從左到右必須是連續的。
• 深度為 k 的完全二叉樹的節點個數最多為 2k - 1，最少為 2k-1 - 1 + 1（前k層節點個數總和+1，因為第k層至少有一個），所以節點個數范圍是：[ 2k-1, 2k - 1 ]

2.3 二叉樹的性質

1.若規定根節點的層數為1，則一棵非空二叉樹的第 i 層上最多有 2i-1 個結點。

2.若規定根節點的層數為1，則**高度(深度)為 h 的二叉樹的「最大結點數」**是 2h - 1。

3.對任何一棵二叉樹，如果度為 0 的葉結點個數為 n0，度為 2 的分支結點個數為 n2，則有 n0＝n2 ＋1（度為 0 的節點 比 度為 2 的節點 多一個）

4.若規定根節點的層數為 1，具有 n 個結點的「滿二叉樹」的高度(深度) h = log2(n+1)。 (log以2為底，n+1為對數)

5.對于具有 n 個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有節點從 0 開始編號，則對于序號為 i 的結點有：

• 若 i > 0，i 位置節點的雙親序號：(i - 1) / 2；i=0，i 為根節點編號，無雙親節點
• 若 2i + 1 < n，左孩子序號：2i + 1，2i + 1 >= n否則無左孩子
• 若 2i + 2 < n，右孩子序號：2i + 2，2i + 2 >= n否則無右孩子

2.4 二叉樹的存儲結構

二叉樹一般可以使用兩種結構來存儲，一種順序結構，一種鏈式結構。

順序存儲

順序存儲就是使用數組來存儲，而「數組」一般只適合表示「滿二叉樹」或「完全二叉樹」，因為不是完全二叉樹會有「空間的浪費」。在實際使用中，只有「堆」才會使用數組來存儲。二叉樹的順序存儲在物理上是一個數組，在邏輯上是一顆二叉樹。

在數組中用下標來表示樹中的父子關系，滿足以下關系：

leftchild = parent * 2 + 1

rightchild = parent * 2 + 2

parent = (child - 1) / 2

鏈式存儲

二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素間的邏輯關系。通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來記錄該結點左孩子和右孩子所在的鏈結點的存儲地址。鏈式結構又分為二叉鏈和三叉鏈，目前我們學的一般都是二叉鏈（紅黑樹等才會用到三叉鏈）

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
	BTDataType data; // 數據域
	struct BinaryTreeNode* leftchild;  // 指向當前節點的左孩子
	struct BinaryTreeNode* rightchild; // 指向當前節點的右孩子
};
// 三叉鏈
struct BinaryTreeNode
{
	BTDataType data; // 數據域
	struct BinaryTreeNode* leftchild;  // 指向當前節點的左孩子
	struct BinaryTreeNode* rightchild; // 指向當前節點的右孩子
	struct BinaryTreeNode* parent;     // 指向當前節點的雙親
};