初階數據結構	相關知識點	可以通過點擊	以下鏈接進行學習	一起加油！
時間與空間復雜度的深度剖析	深入解析順序表:探索底層邏輯	深入解析單鏈表:探索底層邏輯	深入解析帶頭雙向循環鏈表:探索底層邏輯	深入解析棧:探索底層邏輯
深入解析隊列:探索底層邏輯	深入解析循環隊列:探索底層邏輯

本篇將從樹與二叉樹相關概念進行入手，幫助我們接下二叉樹更進一步的學習。

🌈個人主頁：是店小二呀
🌈C語言筆記專欄：C語言筆記
🌈C++筆記專欄： C++筆記
🌈初階數據結構筆記專欄： 初階數據結構筆記

🌈喜歡的詩句:無人扶我青云志 我自踏雪至山巔

一、樹概念及結構

樹是一種非線性的數據結構，它是由n(n>=0)個有限節點組成一個具有層次關系的集合，然而樹在實踐中價值不大，但是二叉樹實踐價值比較大(這種集合稱為樹的理由，是它是根朝上，而葉朝下，看起來很像樹)

• 有一個特殊的節點，稱為根節點，根節點沒有前驅節點
• 除根節點外，其余節點被分成M(M>0)個互不相交的集合T1、T2、....、Tm，其中每一個集合Ti(1<=i<=m)又是一顆結構與樹類似的子樹。每顆子樹的根節點有且只有一個前驅，可有0個或多個后繼。
• 樹是遞歸定義，與此同時需要注意。在樹形結構中子樹之間不能有交集，否則就不是樹形結構

1.1 樹的相關概念

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

二、樹的存儲表示

由于樹狀結構相對線性表復雜，存儲方式也更加麻煩，既要保存值域，也要保存好結點和結點之間的關系。

以下根據之前知識得到的幾種方法

• 每個孩子都有一個地址，可以通過指針數組存儲數據(空間是固定，申請新空間有代價和空間情況問題出現)
• 對于第一種方法優化，將指針數組改用為順序表存儲孩子，解決了空間固定的問題
• 推薦常用的解法:左孩子右兄弟法(老大帶著老二，老二帶著老三，不用雙親累)

typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一個孩子結點struct Node* _pNextBrother; // 指向其下一個兄弟結點DataType _data; // 結點中的數據域
};

當然不局限以上幾種方式，還有雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。我們這里就簡單的了解其中最常用的孩子兄弟表示法

三、二叉樹概念

一顆二叉樹是節點的一個有限集合，該集合可能有兩種情況

1. 空樹
2. 由一個根節點加上兩顆別稱為左子樹和右子樹的二叉樹組成(子樹可能為空樹)

從圖中可以得出兩個結論:

1. 二叉樹不存在度大于2的結點

2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

注意:對于任意的二叉樹都是通過下列幾種情況組成的(空樹的情況最容易忘記)

3.1 現實中的二叉樹(見到都要拜幾下)

四、特殊的二叉樹

• 滿二叉樹:一個二叉樹，如果每一個層的節點數都達到最大值，則這個二叉樹為滿二叉樹。換言之一個二叉樹的層次為K，且節點總數是2^K-1，則它就是滿二叉樹
• 完全二叉樹:完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出的。對于高度為K，有n個節點的二叉樹，當且僅當每一個節點都與高度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。

簡單概括下:

• 滿二叉樹的每一層都是滿的

• 完全二叉樹如果高度是n，那么前n-1個是滿的，最后一層不一定滿，但是從左到右必須是連續

• 完全二叉樹是效率很高的數據結構，滿二叉樹是一種特殊的完全二叉樹

• 滿二叉樹是完全二叉樹的充分必要條件

4.1 不屬于完全二叉樹的情況

這種就是普通的二叉樹，從左到右不是連續的。

五、二叉樹的存儲結構

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

5.1 順序存儲

順序結構存儲就是使用數組來存儲，一般使用數組只適合表示完全二叉樹，因為不是滿二叉樹會有空間的浪費，對此現實中使用中只有堆才會使用數組來存儲。二叉樹順序存儲在物理上是一個數組，在邏輯上是一顆二叉樹，在接下來做題我們需要根據物理上是數組，邏輯上是二叉樹配合去解出一道題目。

5.2 父子節點間下標規律關系(重要)

• leftchild = parent * 2 + 1;

• rightchild = paretn * 2 +2;

• parent = (child - 1) / 2;(不區分左右孩子)

• 對于第三點，個人推理下，leftchild下標拆為leftchild- 1和1，對于leftchild-1為parent下標兩倍，對于(child - 1) / 2運算將leftchild拆出來為1部分單獨除于2取整數為0，leftchild -1部分可以看成leftchild，而且rightchild與leftchild相差1，由于rightchild = leftchild - 1和通過上面leftchild - 1 ~= leftchild，可以推理出rightchild = leftchild(在進行/2運算，取整數情況下)

5.3 鏈式存儲

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

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{struct BinTreeNode* _pLeft; // 指向當前節點左孩子struct BinTreeNode* _pRight; // 指向當前節點右孩子BTDataType _data; // 當前節點值域
}
// 三叉鏈
struct BinaryTreeNode
{struct BinTreeNode* _pParent; // 指向當前節點的雙親struct BinTreeNode* _pLeft; // 指向當前節點左孩子struct BinTreeNode* _pRight; // 指向當前節點右孩子BTDataType _data; // 當前節點值域
}；

5.4 小總結

順序結構存儲就是通過數組進行存儲，一般使用數組只適合完全二叉樹，非完全二叉樹就不適合數組結構存儲，普通二叉樹只適合鏈式結構存儲。但是在現實中使用堆才會使用數組來存儲，大部分還是通過鏈式結構存儲。

原因在于:

1. 首先我們要知道，二叉樹擁有其特殊的邏輯結構，不同于其他數據結構適合堆數據的增刪查改，因為在于開辟的空間消耗大，邏輯也更加復雜，如果使用如此復雜的結構去存儲數據，不是沒有多少價值的，這樣子不如一開始就采用順序表進行存儲數據。同時一般而言，二叉樹的結構是遞歸式，用非遞歸實現更加麻煩，
2. 普通二叉樹中可能存儲元素密度很低，連續存儲的結構會造成大量的空間浪費
3. 堆是根據"堆屬性"來排序，"堆屬性"決定了樹中結點的位置(在下面堆的介紹有說明)

---

以上就是本篇文章的所有內容，在此感謝大家的觀看！這里是店小二初階數據結構筆記，希望對你在學習初階數據結構中有所幫助！