文章目錄
- 前言
- 1.什麼是樹？
- 1.1樹的概念
- 1.2樹的相關知識點
- 1.3樹的代碼表示
- 2.二叉樹
- 2.1概念
- 2.2特殊的二叉樹
- 2.3二叉樹的性質
- 2.4幾個選擇題
- 3.二叉樹的存儲結構
- 3.1順序存儲
- 3.2鍊式存儲
- 結語
前言
在之前的資料結構學習中，我們學習了順序表、連結清單、棧、隊列這幾種結構
它們都是用連結清單或者數組的方式來實作的，主要考察我們對結構體的運用
今天讓我們來學習一個新的資料結構，也就是下面這副圖裡面的樹
啊不好意思，圖拿錯了！????
是下面這個才對
1.什麼是樹？
1.1樹的概念
樹是一種非線性的資料結構，它是由n個有限節點組成的具有一定層次關系的集合。
把它叫做樹是因為它看起來的确像一個樹的根部
當然也可以了解為是樹幹在上，樹葉在下的結構
- 有一個特殊的節點，被稱為根節點，也就是樹的開頭
- 除了根節點外，其餘節點都是,個互不相交的集合。每一個集合都是一顆與樹的結構類似的子樹
- 每一個節點隻能有一個前驅，但是可以有很多個後驅
- 是以，樹是遞歸定義的
樹中的子節點不能有交集
- 上圖中的B節點不能有G這個孩子，因為G已經有父母C了
- 同理，G節點也不能同時擁有兩對父母
- 子節點之間也不能相連，如E和F不能相連
1.2樹的相關知識點
節點的度：一個節點含有的子樹的個數稱為該節點的度； 如下圖：A的度為6
葉節點或終端節點：度為0的節點稱為葉節點； 圖中B、C、H、I…等節點為葉節點
非終端節點或分支節點：度不為0的節點； 如上圖中D、E、F、G…等節點為分支節點
簡單的說，就是有娃的節點就是分支節點
雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖，D是H的父節點
孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：H是D的孩子節點
兄弟節點：具有相同父節點的節點互稱為兄弟節點； 如下圖：P、Q是兄弟節點【C語言】什麼是樹，二叉樹又是啥玩意
樹的度：一棵樹中，最大的節點的度稱為樹的度； 示例中樹的度為6（即A的度）
節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推
樹的高度或深度：樹中節點的最大層次； 示例中樹的高度為4
堂兄弟節點：雙親在同一層的節點互為堂兄弟；如下圖：H、I互為兄弟節點【C語言】什麼是樹，二叉樹又是啥玩意
節點的祖先：從根到該節點所經分支上的所有節點；示例中A是所有節點的祖先
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。示例中所有節點都是A的子孫
森林：由m（m>0）棵互不相交的樹的集合稱為森林
多個不相交的樹就是森林
【C語言】什麼是樹，二叉樹又是啥玩意
1.3樹的代碼表示
表示樹的方式有很多種，比如下面這種
#define N 5 //指定樹的度為5
struct TreeNode
{
int data;
struct TreeNode* subs[N];//用指針數組存放孩子節點的指針
}; 但這種方法不夠優，給大家展示一個用的最廣泛的方法——孩子兄弟表示法
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一個孩子結點
struct Node* _pNextBrother; // 指向其下一個兄弟結點
DataType _data; // 結點中的資料域
}; 通過這種方法，父親節點隻需要儲存它的第一個娃，其他娃就讓大娃的兄弟節點來找
也就是家長隻用管老大，老大管老二，老二管老三，依次往下……
實際寫代碼的結構大概是下圖這樣
2.二叉樹
在實際中，二叉樹是使用較多的一種樹的結構
2.1概念
二叉樹是度為2的樹，它是一個特殊的樹
- 二叉樹不存在度大于2的節點
- 二叉樹是有序樹，它的娃（子樹）有左右之分，次序不能颠倒
是以，二叉樹都是由下面各類節點組成的樹
2.2特殊的二叉樹
滿二叉樹：如果每一個層的節點數都達到最大值，那這個二叉樹就是滿二叉樹。也就是說：滿二叉樹的層數為k，且節點總數是2k-1
滿二叉樹的節點數是一個等比數列公式
2
+
2
1
+
2
2
+
.
.
.
+
2
k
−
1
=
1
∗
(
1
−
2
k
)
/
(
1
−
2
)
=
2
k
−
1
2^0+2^1+2^2+...+2^{k-1}=1*(1-2^k)/(1-2)=2^k -1
20+21+22+...+2k−1=1∗(1−2k)/(1−2)=2k−1
完全二叉樹：完全二叉樹是效率很高的資料結構。對于深度為K，有n個節點的二叉樹，當且僅當每一個節點都與深度為K的滿二叉樹中編号從1至n的節點一一對應時，稱為完全二叉樹。
簡單說來，完全二叉樹的最後一層不一定滿，但必須要從左到右連續
滿二叉樹是一個特殊的完全二叉樹
2.3二叉樹的性質
- 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有
2(i-1)
- 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是
2h-1
- 對任何一棵二叉樹, 如果度為0其葉結點個數為n0, 度為2的分支結點個數為n2，則有
n0 = n2+1
- 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，
h=log2(n+1)
- 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有節點從0開始編号，則對于序号為i的結點有：
- 若
i>0
(i-1)/2
- 若
2i+1<n
- 若
2i+2<n
2.4幾個選擇題
1. 某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為（ ）
A 不存在這樣的二叉樹
B 200 √
C 198
D 199
//葉子節點的數量 總比度為2的節點多1
2.在具有 2n 個結點的完全二叉樹中，葉子結點個數為（ ）
A n √
B n+1
C n-1
D n/2
//N0+N1+N2=2n
//2N0+N1-1=2n
//N1隻有0和1兩種可能，因為n為整數，2n為偶數，是以2N0=2n，N0=n
3.一棵完全二叉樹的節點數位為531個，那麼這棵樹的高度為（ ）
A 11
B 10 √
C 8
D 12
//假設高度是h
//完全二叉樹節點最多2^h -1
// 最少2^(h-1)-1 +1
//可以通過這兩個公式，推斷出h=10 3.二叉樹的存儲結構
二叉樹一般可以使用兩種結構存儲，一種順序結構，一種鍊式結構
3.1順序存儲
順序結構存儲就是使用數組來存儲
一般使用數組隻适合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。
現實使用中隻有堆才會使用數組來存儲
下一篇部落格會帶大家認識
這個特殊的樹形結構（和記憶體裡面那個堆????沒啥關系哈）堆
看到這張圖，你肯定想問，如果用數組結構存儲，那還怎麼還原出一顆樹????呢？
這裡我們需要了解實體存儲和邏輯結構的關系
二叉樹順序存儲在實體上是一個數組，在邏輯上是一顆二叉樹
那怎麼計算這種情況下的父親和娃呢？
- leftchild=parent*2+1
- rightchild=parent*2+2
- parent=(child-1)/2
怎麼樣，是不是忽然感覺妙級了？
3.2鍊式存儲
這就就沒啥好說的啦，使用一個簡單的二叉鍊就能構成二叉樹
typedef int BTDataType;
// 二叉鍊
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向目前節點左孩子
struct BinTreeNode* _pRight; // 指向目前節點右孩子
BTDataType _data; // 目前節點的值
} 結語
嘿嘿嘿，本篇部落格到這裡就結束啦！
下篇部落格将帶來堆的詳解
如果對你有幫助，還請點個????，萬分感謝！