1. 樹的概念與結構

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

• 有?個特殊的結點，稱為根結點，根結點沒有前驅結點。

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

注意：

• 樹形結構中，?樹之間不能有交集，否則就不是樹形結構。（如果存在相交就是圖了）
• 除了根結點外，每個結點有且僅有?個父節點
• ?棵N個結點的樹有N-1條邊（箭頭）

2. 樹的相關術語

父結點/雙親結點：若一個結點含有子結點，則這個結點稱為其子結點的父結點；如上圖：A是B的父結點

子結點/孩子結點：一個結點含有的子樹的根結點稱為該結點的子結點；如上圖：B是A的孩子結點

結點的度：一個結點有幾個孩子，他的度就是多少；比如A的度為6，F的度為2，K的度為0

樹的度：一棵樹中，最大的結點的度稱為樹的度；如上圖：樹的度為 6

葉子結點/終端結點：度為 0 的結點稱為葉結點；如上圖：B、C、H、I… 等結點為葉結點

分支結點/非終端結點：度不為 0 的結點；
如上圖：D、E、F、G… 等結點為分支結點

兄弟結點：具有相同父結點的結點互稱為兄弟結點（親兄弟）；如上圖：B、C 是兄弟結點

結點的層次：從根開始定義起，根為第 1 層，根的子結點為第 2 層，以此類推；

樹的高度或深度：樹中結點的最大層次；如上圖：樹的高度為 4

結點的祖先：從根到該結點所經分支上的所有結點；如上圖：A 是所有結點的祖先

路徑：一條從樹中任意節點出發，沿父節點-子節點連接，達到任意節點的序列；比如A到Q的路徑為：A-E-J-Q；H到Q的路徑H-D-A-E-J-Q

子孫：以某結點為根的子樹中任一結點都稱為該結點的子孫。如上圖：所有結點都是A的子孫

森林：由 m（m>0） 棵互不相交的樹的集合稱為森林；

3. 樹的表示

樹結構相對于線性表就比較復雜了，要存儲和表示起來就比較麻煩了，實際中樹有很多種表示方法。如：雙親表示法、孩子表示法、孩子兄弟表示法等等。其中最常用的是孩子兄弟表示法。
孩子兄弟表示法中，所定義的結點類型大致是這樣的：

struct TreeNode
{struct Node* child;   //第一個孩子結點struct Node* brother;  //指向下一個兄弟結點DataType data;             //結點中的數據域
};

4. 樹形結構實際運用場景

文件系統是計算機存儲和管理文件的一種方式，它利用樹形結構來組織和管理文件和文件夾。在文件系統中，樹結構被廣泛應用，它通過父結點和子結點之間的關關系來表示不同層級的文件和文件夾之間的關聯。

5. 二叉樹

5.1 二叉樹的概念與結構

在樹形結構中，最常?的就是?叉樹，?棵?叉樹是結點的?個有限集合，該集合由?個根結點加上兩棵別稱為左?樹和右?樹的?叉樹組成或者為空。

從上圖可以看出?叉樹具備以下特點：

1. ?叉樹不存在度?于 2 的結點
2. ?叉樹的?樹有左右之分，次序不能顛倒，因此?叉樹是有序樹

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

5.2 特殊的二叉樹

5.2.1 滿二叉樹

?個?叉樹，如果每?個層的結點數都達到最?值，則這個?叉樹就是滿?叉樹。也就是說，如果?個?叉樹的層數為 K ，且結點總數是$2^k?1$ ，則它就是滿?叉樹。

5.2.2 完全二叉樹

完全二叉樹 是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。

對于深度為 K 的，有 n 個結點的二叉樹，當且僅當其每一個結點都與深度為 K 的滿二叉樹中編號從 1 至 n 的結點一一對應時稱之為完全二叉樹。

要注意的是，滿二叉樹 是一種特殊的完全二叉樹，完全二叉樹是從左到右的。

5.2.3 二叉樹的性質

• 性質一：若規定根結點的層數為$1$，則一棵非空二叉樹的第i層上最多有$2i?1$個結點。
• 性質二：若規定根結點的層數為$1$，則深度為h的二叉樹的最大結點數為$2h?1$個。
• 性質三：對任何一棵二叉樹，如果度為0的葉結點個數為$n0$，度為2的分支結點個數為$n2$，則有$n0=n2+1$。
• 性質四：若規定根結點的層數為$1$，則具有N個結點的滿二叉樹的深度$h=log2(N+1)$。
• 性質五：若規定結點層數為$1$，具有$n$個結點的滿二叉樹的深度
• 性質六：對于具有$N$個結點的完全二叉樹，如果按照從上至下、從左至右的數組順序對所有結點從0開始編號，則對于序號為i的結點：
  • 若 i > 0，則該結點的父結點序號為：( i - 1) / 2；若 i = 0，則無父結點。
  • 若2i + 1 < N，則該結點的左孩子序號為：2i + 1；若2i + 1 >= N，則無左孩子。
  • 若2i + 2 < N，則該結點的右孩子序號為：2i + 2；若2i + 2 >= N，則無右孩子。

5.3 二叉樹的存儲結構

5.3.1 順序結構

順序結構存儲就是使用數組來存儲，一般使用數組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，完全二叉樹更適合使用順序結構存儲。

現實中通常把堆(一種二叉樹)使用順序結構的數組來存儲，需要注意的是這里的堆和操作系統虛擬進程地址空間中的堆是兩回事，一個是數據結構，一個是操作系統中管理內存的一塊區域分段。

5.3.2 鏈式結構

二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹,即月用鏈來指示元素的邏輯關系。通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址。鏈式結構又分為二叉鏈和三叉鏈，當前我們學習中一般都是二叉鏈。后面學到高階數據結構如紅黑樹等會用到三叉鏈。