【數據結構】樹（Tree）

???專欄：數據結構? ? ?

? ? ? ? ? 🧑?🎓個人主頁：SWsunlight

?一、基本概念：

1、定義：

?編輯

2、樹的成分：

3、樹的性質：

二、存儲方式：

?編輯

雙親表示法：

孩子表示法：

孩子兄弟表示法（左孩子右兄弟）：

?三、二叉樹：

概念：

存儲方式：

1、順序存儲（順序表）?

2、鏈式存儲（鏈表）

?一、基本概念：

1、定義：

????????樹是一種非線性的數據結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合。為了使其抽象變得具體、易理解，且?因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的樹

如下圖：可以將最上面想象成樹根，開始發散，然后就分化枝條 👉到最后沒有枝條（黑色線）連接的是葉子(葉子節點)??

下圖就是典型的樹結構，樹枝是不會有葉子的，所以只有分到最后一步了才是葉子；

注意：你看見過樹的枝條會和另一根枝條相交么？？正常情況的樹不會的；換一個思路：可以理解為這是一個家族族譜，最上面的節點就是老祖，他生了孩子，孩子又繼續生孩子，到你這一代即（葉子）? 你想一下：家庭關系能亂掉么？？要是隨便一個祖先都能相交，豈不是倫理問題了！！！亂了，一切都亂了！！！！恐怕這個世界都瘋了！！！

圖中文字很好理解吧！一個人肯定只有一個爹，當然有個例外——老祖，它的父親我們找不到，暫且沒有

總結：

樹是一種非線性的數據結構，它表現的關系是一對多

它是由n（n>=0）個結點組成的有限集，當n = 0時此時只有一個根節點，稱為空樹。

在任意一棵非空樹中應滿足：

1.有且僅有一個特殊的根節點，根節點沒有前驅結點

2.每一個非根結點有且只有一個父親結點

? ?除了根結點外，每個子結點可以分為多個不相交的子樹，并且子樹是不相交的

3.樹是遞歸定義的

4.一顆N個結點的樹有N-1條

2、樹的成分：

前言：接下里講述的各種名稱是根據選則參考系來說的（例子為開頭那張樹的圖）我們可以選整體一顆樹來論，然后在樹里面又有許多子樹

總結：任何一棵樹包含：根和子樹——>{根+N棵子樹（N>=0）};

根節點：類比樹根，，沒有前驅節點，即沒有父親節點的節點，有且只有一個。所有節點通過直接或間接方式都能找到此根節點。如：A就是這顆樹的根節點
節點的度：一個節點含有孩子的個數（或者說子樹的個數，是我生的孩子（二代），即這個節點有幾個孩子）。? ?? ? ? 如：A的度為3 、B的度為2、E的度為0、J的度為0；
葉節點/終端節點：度為0的節?，類比樹葉?????? 。? ? ? ? ? ? ????????????如：J、F、K、L、H、I
非終端節點/分支節點：度不為0的節點。? ? ? ? ? ?如：B、C、D、E、G
父親節點/雙親節點：若一個節點含有子節點。? ? 如：A是B和C、D的父親
子節點/孩子節點：一個節點含有子樹的根節點（有父親）。? ? ? ?如：B是A的孩子（子）節點，若是將B看成一顆子樹的根節點那么 E是B的孩子節點
兄弟節點：具有同一個父親節點（親兄弟）。? ? ? ? ? ?如：E和F是兄弟節點
堂兄弟節點：雙親節點在同一成的節點互為堂兄弟。? ? ? ? ? ? ? 如：E與G、H、I節點互為堂兄弟
節點的祖先：從根節點到該節點所徑分支上（唯一路徑上）的所有節點（“直系親屬”）如下：紅色圈就是一個路徑，J的祖先就是E、B、A ；? 而A是所有節點的祖
子孫：以某個節點為根的子樹種，任意一個節點都是該節點（根）的子孫。? ? ? ? ? ? ? ? ?如：B的子孫包括E、F、J
樹的度：一顆樹中，最大的?節點的度（生的孩子最多個數）。? ? ? ? ? ? ? ? ? ?如：上圖的樹的度為：3
路徑和路徑長度：樹中兩個結點之間的路徑是由這兩個結點之間所經過的結點序列構成的,而路徑長度是路徑上所經過的邊的個數（就是連接線的個數）。
樹的層次：從根開始定義，根結點為第1層,它的子結點為第2層,以此類推?
樹的高度/深度：
???????深度：是從根結點開始自頂向下逐層累加的
高度：是從葉結點開始自底向上逐層累加的。
樹的高度(或深度)是樹中結點的最大層數
如：上圖的高度/深度是 4（與你怎么定義層數有關，第一層你是從0開始，還是從1開始計數，建議從1開始，因為開始時初始位置為0，若是0開始初始位置就是-1了）
森林：互不不想交的樹（多棵樹/多個根節點）? ? ? ? ? ? 如：并查集

標紅的是需要重點記住的

3、樹的性質：

結點數性質：樹中結點的個數 == 所有節點的度數+1（根節點）
層數性質：樹的高度（層數）等于樹中最大的層數，其中每一層包括所有結點中距離根結點最遠的結點。
度數性質：度為m的樹中，第i層的結點數最多為m^(i-1)。 i>=1;
結點數量與高度關系：一個高度為h的m叉樹最多有? (m^h-1)/(m-1)? 個結點。同樣，一個具有n個結點的m叉樹的最小高度為? ?logm(n*(m-1)

二、存儲方式：

(1)、雙親表示法（2）孩子表示法（3）孩子兄弟表示法

雙親表示法：

我們假設以一組連續空間（數組）存儲樹的結點，同時在每個結點中，附設一個指示器指示其雙親結點到在表中的位置。也就是說，每個結點除了知道自已是誰以外，還知道它的雙親在哪里。

其中data是數據域，存儲結點的數據信息。而parent是指針域，存儲該結點的雙親在數組中的下標。

//數組大小
#define MAX_Size 100
typedef int FrDataType;//結點的結構
typedef struct Node
{FrDataType data;int parent;
}Node;
//樹的結構
typedef struct Ptree {Node a[MAX_Size];//結點數組int r;//根的位置int n;//節點數}Ptree;

這樣的存儲結構，我們可以根據結點的parent 指針找到它的雙親結點，所用的時間復雜度為0(1)，當到parent為-1時，表示找到了根節點。但是要知道結點的孩子是什么，需要遍歷整個結構才行

孩子表示法：

把每個結點的孩子結點排列起來，以單鏈表作存儲結構，則n個結點有n個孩子鏈表，如果是葉子結點則將此單鏈表設為空。然后n個頭指針又組成一個順序表（線性表），采用順序存儲結構，存放進一個一維數組中，如圖所示 數據A的下標為0，然后他的孩子有2個，下標分別為1和2，將1和2，存到了右邊的數組中，再為下標1和下標2找孩子結點，下標為1的孩子只有一個，放到數組，以此類推

、

》》》設計兩種結點結構，一個是孩子鏈表的孩子結點。
其中child是數據域，用來存儲某個結點在表頭數組中的下標。next 是指針域，用來存儲指向某結點的下一個孩子結點的指針。

另一個是表頭數組的表頭結點。

其中data是數據域，存儲某結點的數據信息。firstchild 是頭指針域存儲該結點的孩子鏈表的頭指針。

//樹的孩子表示法結構定義
#define MAX_SIZE 100
typedef int FrDataType;
//孩子結點
typedef struct Node {int child;//記錄每個孩子下標struct Node* next;
}*ChildPtr;
//表頭結點
typedef struct {FrDataType data;ChildPtr firstchild;
}FrBox;
//樹結構
typedef struct Ptree{FrBox node[MAX_SIZE];//結點數組int r;//根的位置int	n;//和結點數
}Ptree;

孩子兄弟表示法（左孩子右兄弟）：

前面考慮了雙親和孩子。現在考慮兄弟來做；對于樹這樣的層級結構來說，只研究結點的兄弟是不行的，我們觀察后發現，任意一棵樹，它的結點的第一個孩子如果存在就是唯一的B，它的右兄弟（“兄弟”是兄弟節點不是堂兄）如果存在也是唯一的；

?結構如下：child指向左邊的第一個孩子，這么理解：后面我（父親）陸續的生娃，第二個娃交給老大帶，第三的娃交給老二帶（A的生的第一個娃就是B,后面又生了娃C，娃C就是娃B的右兄弟，C交給B來帶B->C，沒有兄弟了就指向NULL）依次類推：

?結構如下：


//左孩子右兄弟法  樹的定義
typedef int TrDataType;
typedef struct TreeNode
{TrDataType val;//數據struct TreeNode* leftchild;//左孩子struct TreeNode* rightBrother;//右兄弟}TreeNode;

這個其實就是二樹，我們用這個方法將其變成了二叉樹

?三、二叉樹：

概念：

? 定義：二叉樹是另一種樹形結構，其特點是每個結點至多只有兩棵子樹( 即二叉樹中不存在度大于2的結點)，并且二叉樹的子樹有左右之分，其次序不能任意顛倒，所以說是一顆有序樹；
與樹相似，二叉樹也以遞歸的形式定義。二叉樹是n (n≥0) 個結點的有限集合

二叉樹的組成均由以下幾種情況復合完成

?特殊的二叉樹：

滿二叉樹：每一個層的結點數都達到最大值（滿二叉樹是一種特殊的完全二叉樹）

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

二叉排序樹：左子樹上所有結點的關鍵字均小于根結點的關鍵字;右子樹上的所有結點的關鍵字均大于根結點的關鍵字;左子樹和右子樹又各是一棵二叉排序樹。

平衡二叉樹：樹上任一結點的左子樹和右子樹的深度之差不超過1。

?斜樹：所有的節點都只有左或者右子樹

二叉樹的性質：
任意一棵樹，若結點數量為n,則邊的數量為n ? 1。
非空二叉樹上的葉子結點數等于度為2的結點數加1，即no = n2 + 1 。
非空二叉樹上第k層上至多有2k ? 1個結點( k ≥ 1 ) 。
高度為h的二叉樹至多有2 h? 1個結點( h ≥ 1 ) 。
對完全二叉樹按從上到下、從左到右的順序依次編號1 , 2… ? , n 1,2…*,n1,2…?,n,則有以下關系:
i > 1時，結點i的雙親的編號為i / 2,即當i 為偶數時，它是雙親的左孩子;當i為奇數時，它是雙親的右孩子。
當2i ≤ n 時，結點i的左孩子編號為2i 否則無左孩子。
當2i + 1 ≤ n 時，結點i的右孩子編號為2i + 1，否則無右孩子。
結點i所在層次(深度)為{ l o g 2 i } +1。
具有n個( n > 0 ) 結點的完全二叉樹的高度為{ l o g ~2 n~ } +1。
? ? ? ? ? ? ? ? ? ? ? ??