???內(nèi)容專欄：《數(shù)據(jù)結(jié)構(gòu)與算法專欄》
??本文概括： 二叉樹是一種常見的數(shù)據(jù)結(jié)構(gòu)，它在計算機科學(xué)中廣泛應(yīng)用。本博客將介紹什么是二叉樹、二叉樹的順序與鏈式結(jié)構(gòu)以及它的基本操作，幫助讀者理解和運用這一重要概念。
??本文作者： 花 蝶
??發(fā)布時間：2023.6.5
一、樹的概念及結(jié)構(gòu)
1.1 樹的概念
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。
??現(xiàn)實生活中的樹：
??數(shù)據(jù)結(jié)構(gòu)中的樹：將生活中的樹倒置，形成一種結(jié)構(gòu)。
??樹的一些相關(guān)概念：
節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度； 如上圖：
A的為6
葉節(jié)點或終端節(jié)點：度為0的節(jié)點稱為葉節(jié)點； 如上圖：B、C、H、I…等節(jié)點為葉節(jié)點
非終端節(jié)點或分支節(jié)點：度不為0的節(jié)點； 如上圖：D、E、F、G…等節(jié)點為分支節(jié)點
雙親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點； 如上圖：A是B的父節(jié)點
孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點； 如上圖：B是A的孩子節(jié)點
兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點； 如上圖：B、C是兄弟節(jié)點
樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度； 如上圖：樹的度為6
節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推
樹的高度或深度：樹中節(jié)點的最大層次； 如上圖：樹的高度為4
堂兄弟節(jié)點：雙親在同一層的節(jié)點互為堂兄弟；如上圖：H、I互為兄弟節(jié)點
節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點；如上圖：A是所有節(jié)點的祖先
子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。如上圖：所有節(jié)點都是A的子孫
森林：由m（m>0）棵互不相交的樹的集合稱為森林
1.2 樹的結(jié)構(gòu)特點
- 有一個特殊的節(jié)點，稱為
根節(jié)點，根節(jié)點沒有前驅(qū)節(jié)點（即樹的最頂端的節(jié)點） - 除根節(jié)點外，其余節(jié)點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點有且只有一個前驅(qū)節(jié)點，可以有0個或多個后繼節(jié)點。任何一顆樹都是由根節(jié)點和若干個子樹構(gòu)成。子樹又是由一個父節(jié)點及若干個子樹構(gòu)成。直到走到葉子節(jié)點沒有子樹為止。
- 因此，樹是遞歸定義的。
??注意：樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)。
1.3 樹的表示
樹結(jié)構(gòu)相對線性表就比較復(fù)雜了，要存儲表示起來就比較麻煩了，既要保存數(shù)據(jù)，也要保存結(jié)點和結(jié)點之間的關(guān)系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。
我們這里就簡單的了解其中最常用的孩子兄弟表示法。
??代碼如下：
struct Node
{
struct Node* _firstChild1; // 第一個孩子結(jié)點
struct Node* _pNextBrother; // 指向其下一個兄弟結(jié)點
int _data; // 結(jié)點中的數(shù)據(jù)域
};
其下圖邏輯就是孩子指針指向下一個孩子結(jié)點，進行層次遍歷，兄弟指針指向其兄弟結(jié)點。
1.4 樹在實際中的應(yīng)用（文件系統(tǒng)的樹狀目錄結(jié)構(gòu)）
二、二叉樹概念及結(jié)構(gòu)
2.1 二叉樹概念
一棵二叉樹是結(jié)點的一個有限集合，該集合為空或者由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉樹組成。
2.2 二叉樹結(jié)構(gòu)圖
從上圖可以看出：
1.== 二叉樹不存在度大于2的結(jié)點==
2.== 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹==
?? 注意：對于任意的二叉樹都是由以下幾種情況復(fù)合而成的：
2.3 特殊的二叉樹
前期數(shù)據(jù)結(jié)構(gòu)中特殊的二叉樹中我們先講兩種：滿二叉樹和完全二叉樹。
1.
滿二叉樹：一個二叉樹，如果每一個層的結(jié)點數(shù)都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為n，且結(jié)點總數(shù)是2? - 1，則它就是滿二叉樹。
2.完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時稱之為完全二叉樹。 要注意的是**滿二叉樹是一種特殊的完全二叉樹**。
簡單點說，滿二叉樹的每一層都是滿的，而完全二叉樹的前h - 1層是滿的，最后一層可以不滿，但必須保證連續(xù)。
PS1：假設(shè)一顆滿二叉樹，高度為h，節(jié)點數(shù)量有多少個呢？
其實很簡單，第一層，有20個、第二層，有21個，第三層，有22個、…… 第h層，有2h-1個，這里我們把1到h層的個數(shù)全部加起來，就有
F(h)= 20 + 21 + 22 + ……+ 2h-1 = 2h - 1 ，這本質(zhì)其實就是一個等比數(shù)列的求和。
PS2:高度為h的完全二叉樹的節(jié)點范圍是多少呢？
我們知道，一個完全二叉樹節(jié)點最多的情況就是一個滿二叉樹，即最多的節(jié)點就是2h - 1個，那么最少呢，最少就是前一層是滿的，外加最后一層最少必須為1個，套用前面的求和結(jié)果，最少的節(jié)點就是F(h - 1) = 2h-1 - 1，所以節(jié)點的范圍用區(qū)間表示為[ 2h-1 ，2h - 1]
2.4 二叉樹的性質(zhì)
- 若規(guī)定根節(jié)點的層數(shù)為
1，則一棵非空二叉樹的第i層上最多有2^(i - 1)個結(jié)點.- 若規(guī)定根節(jié)點的層數(shù)為
1，則深度為h的二叉樹的最大結(jié)點數(shù)是2^h - 1- 對任何一棵二叉樹, 如果度為
0其葉結(jié)點個數(shù)為n?, 度為2的分支結(jié)點個數(shù)為n?,則有n?＝n? ＋1- 若規(guī)定根節(jié)點的層數(shù)為
1，具有n個結(jié)點的滿二叉樹的深度，h=log?（n + 1）. (ps：h=log?（n + 1） 是log以2為底，n+1為對數(shù))- 對于具有n個結(jié)點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點從0開始編號，則對于序號為i的結(jié)點有：
- 若 i >0，i位置節(jié)點的雙親序號：(i-1)/2；i=0，i為根節(jié)點編號，無雙親節(jié)點
- 若2i+1 < n，左孩子序號：2i+1，2i+1>=n否則無左孩子
- 若2i+2 < n，右孩子序號：2i+2，2i+2>=n否則無右孩子
2.5 二叉樹的存儲結(jié)構(gòu)
二叉樹一般可以使用兩種結(jié)構(gòu)存儲，一種順序結(jié)構(gòu)，一種鏈式結(jié)構(gòu)。
- 順序存儲
順序結(jié)構(gòu)存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲，關(guān)于堆我們后面的章節(jié)會專門講解。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。
??順序存儲形態(tài)圖：
結(jié)論：完全二叉樹才適合順序存儲，因為非完全二叉樹存在大量的空間浪費。
PS：根據(jù)上圖完全二叉樹的順序存儲，我們可以通過下標建立父親與孩子之間的關(guān)系：
通過父親下標求孩子：
leftChild = parent * 2 + 1
rightChild = parent * 2 + 1
通過孩子小標找父親：
parent = （child - 1）/ 2
- 鏈式存儲
二叉樹的鏈式存儲結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個結(jié)點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址 。鏈式結(jié)構(gòu)又分為二叉鏈和三叉鏈，當前我們學(xué)習(xí)中一般都是二叉鏈，后面課程學(xué)到高階數(shù)據(jù)結(jié)構(gòu)如紅黑樹等會用到三叉鏈。
??鏈式存儲形態(tài)圖：
三、二叉樹的順序結(jié)構(gòu)及實現(xiàn)
3.1 二叉樹的順序結(jié)構(gòu)
普通的二叉樹是不適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結(jié)構(gòu)存儲?，F(xiàn)實中我們通常把堆(一種二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進程地址空間中的堆是兩回事，一個是數(shù)據(jù)結(jié)構(gòu)，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。
3.2 堆的概念及結(jié)構(gòu)
??堆的性質(zhì)：
- 大根堆(大堆)： 樹中任意一個父節(jié)點都大于等于其子節(jié)點；
- 小根堆(小堆)： 樹中任意一個父節(jié)點都小于等于其子節(jié)點。
- 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值。
- 堆總是一顆完全二叉樹。
3.3 堆的實現(xiàn)
因為堆是一顆完全二叉樹，完全二叉樹更適合順序結(jié)構(gòu)存儲，所有我們這里可以用順序表來實現(xiàn)，實現(xiàn)方法類似于之前使用過的順序表，代碼如下：
typedef int HPdataType;
typedef struct Heap
{
HPdataType* arr; //動態(tài)數(shù)組
int size; //有效元素個數(shù)
int capacity; //數(shù)組容量
}Heap;
堆的插入
這里我們拿小堆來實現(xiàn)，大堆的話，大家可以自己操作進行類比。
如果我們要在堆中插入數(shù)據(jù)，那么其實我們本質(zhì)上是在數(shù)組的最后面進行插入元素，如下圖，假設(shè)在小堆的基礎(chǔ)上繼續(xù)插入50，它仍舊是一個堆。
如果在小堆的基礎(chǔ)上面，繼續(xù)往后插入一個元素6呢？我們可以發(fā)現(xiàn)，如果插入之后，就滿足不了小堆的性質(zhì)了，因為
6比28要小，
勢必會影響到根節(jié)點到當前節(jié)點路徑中的所有節(jié)點，所以我們需要找到當前插入節(jié)點的父親節(jié)點，乃至祖先節(jié)點，那么如何根據(jù)孩子去找父親呢？前面我們講到一個關(guān)系公式，parent = （child - 1）/ 2，邏輯中是二叉樹，實際中我們就可以這樣通過下標在數(shù)組中去訪問父親
路徑中可能有多個節(jié)點需要被調(diào)整，所以我們需要不斷更新child和parent的下標位置
向上調(diào)整算法
以小堆為例，如果孩子節(jié)點小于父親節(jié)點就進行兩兩交換，直到調(diào)整到根節(jié)點后，確保滿足完整堆的性質(zhì)。
??ps：
- 向上調(diào)整算法一般適合于堆的插入操作
- 前提是左右子樹必須為大堆 or 小堆
- 一個節(jié)點(根節(jié)點、葉子節(jié)點)可以看作是大堆 or 小堆
??代碼如下：
//向上調(diào)整
void AdjustUp(HPdataType* a,int child)
{
//根據(jù)孩子找父親
int parent = (child - 1) / 2;
//孩子下標小于等于0就結(jié)束
while (child > 0)
{
//小堆情況下 孩子小于父親就交換
if (a[child] < a[parent])
{
HPdataType tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
//更新節(jié)點，繼續(xù)往上迭代找
child = parent;
parent = (child - 1) / 2;
}
else
{
//孩子大于等于父親就結(jié)束循環(huán)
break;
}
}
}
//堆的插入
void HeapPush(Heap* php, HPdataType x)
{
assert(php);
if (php->capacity == php->size)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPdataType* a = (HPdataType*)realloc(php->arr,sizeof(HPdataType)* newcapacity);
if (a == NULL)
{
perror("malloc fail");
return;
}
php->arr = a;
php->capacity = newcapacity;
}
php->arr[php->size] = x;
php->size++;
//為了保證堆的性質(zhì)，需要進行向上調(diào)整
AdjustUp(php->arr,php->size - 1);
}
堆的刪除
對于堆的刪除操作，我們不是刪除堆的最后一個元素，因為毫無意義，而是刪除堆頂元素，我們可以進行先刪除堆頂，然后把后面的元素挪動往前覆蓋， 挪動后并不能保證它具有堆的性質(zhì)，因為挪動后父子之間的關(guān)系全變了，因此我們需要重新建堆。但是這樣的代價太大了，我們接下來尋找最優(yōu)解法。
我們盡量不改變堆頂元素下面所有節(jié)點之間的位置，讓堆頂元素與最后一個元素進行交換，然后進行刪除，可能交換之后的堆頂元素影響堆的性質(zhì)，于是我們可以進行向下調(diào)整。
向下調(diào)整算法
以小堆為例，如果孩子節(jié)點小于等于父親節(jié)點就進行兩兩交換，直到調(diào)整到葉子節(jié)點，確保滿足完整堆的性質(zhì)。
??ps：
- 前提是左右子樹必須為大堆 or 小堆
??代碼如下：
//向下調(diào)整
void AdjustDown(int* a,int n,int parent)
{
//根據(jù)父親找孩子
int child = parent * 2 + 1;//假設(shè)左孩子最小
while (child < n)
{
//小堆情況下
//如果右孩子存在的情況下必須保證小于n
if (child + 1 < n && a[child + 1] < a[child])
{
//如果右孩子小于左孩子
//那么就把下標位置給到右孩子
child++;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
//繼續(xù)往下迭代走
parent = child;
child = parent * 2 + 1;
}
else
{
//孩子大于父親，符合小堆性質(zhì)，跳出循環(huán)
break;
}
}
}
//堆的刪除操作
void HeapPop(Heap* php)
{
assert(php);
assert(!HeapEmpty(php));
//首尾元素交換
Swap(&php->arr[0], &php->arr[php->size - 1]);
php->size--;
AdjustDown(php->arr, php->size, 0);
}
那么向上調(diào)整算法和向下調(diào)整算法，他們的時間復(fù)雜度是多少呢？看時間復(fù)雜度我們需要看最壞的情況，即需要調(diào)整完全二叉樹的高度次，前面我們計算過高度為h的完全二叉樹的節(jié)點范圍是[ 2h-1 ，2h - 1]，那么根據(jù) N = 2h-1 計算出h = logN + 1， N = 2h - 1 計算出h = log(N+1)，所以他們的時間復(fù)雜度都為logN
堆的創(chuàng)建
??前面我們提起的向上調(diào)整算法和向下調(diào)整算法，前提都是左右子樹為大堆或者小堆。如果對于任意的完全二叉樹，即根節(jié)點的左右子樹不滿足堆的性質(zhì)，該怎么調(diào)整成堆呢？
下面我們給出一個數(shù)組，這個數(shù)組邏輯上可以看做一顆完全二叉樹，但是還不是一個堆，現(xiàn)在我們通過算法，把它構(gòu)建成一個堆。根節(jié)點左右子樹不是堆，我們怎么調(diào)整呢？這里我們從倒數(shù)的第一個非葉子節(jié)點的子樹開始調(diào)整，一直調(diào)整到根節(jié)點的樹，就可以調(diào)整成堆。
3.4 堆的應(yīng)用
Top-K問題
TOP-K問題：即求數(shù)據(jù)結(jié)合中前K個最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。比如：專業(yè)前10名、世界500強、富豪榜、游戲中前100的活躍玩家等。
對于Top-K問題，能想到的最簡單直接的方式就是排序，但是：如果數(shù)據(jù)量非常大，排序就不太可取了(可能數(shù)據(jù)都不能一下子全部加載到內(nèi)存中)。最佳的方式就是用堆來解決，基本思路如下：
-
1.用數(shù)據(jù)集合中前K個元素來建堆
前k個最大的元素，則建小堆
前k個最小的元素，則建大堆
用剩余的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素(覆蓋) -
2.將剩余N-K個元素依次與堆頂元素比完之后，堆中剩余的K個元素就是所求的前K個最小或者最大的元素。
??代碼如下：
//創(chuàng)造數(shù)據(jù)
void CreateDate()
{
int n = 10000;
srand(time(NULL));
FILE* fin = fopen("data.txt", "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
int i = 0;
for (i = 0; i < n; i++)
{
fprintf(fin, "%d\n", rand() % 1000);
}
fclose(fin);
}
void PrintTopK(int k)
{
FILE* fout = fopen("data.txt", "r");
if (fout == NULL)
{
perror("fopen error");
return;
}
int* kminheap = (int)malloc(sizeof(int) * k);
if (kminheap == NULL)
{
perror("malloc fail\n");
return;
}
//讀取前k個數(shù)到數(shù)組中
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &kminheap[i]);
}
//前k個數(shù)建立小堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(kminheap, k, i);
}
//剩余的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素(覆蓋)
int val = 0;
while (!feof(fout))
{
fscanf(fout, "%d", &val);
if (val > kminheap[0])
{
kminheap[0] = val;
//向下調(diào)整
AdjustDown(kminheap, k, 0);
}
}
//打印剩余K個元素就是最大值
for (int i = 0; i < k; i++)
{
printf("%d ", kminheap[i]);
}
}
int main()
{
//CreateDate();
PrintTopK(5);
}
為了方便，可以在寫完整個代碼之后，F(xiàn)5測試一遍，創(chuàng)造一次數(shù)據(jù)之后，將CreareDate()執(zhí)行一次，再到文件當中給隨便5個數(shù)據(jù)增大幾位，這樣就方便測試，自己寫的代碼對不對。
打印自己的代碼之后，確實找出了剩余K個元素，并且是最大值。
堆排序
堆排序即利用堆的思想來進行排序，總共分為兩個步驟：
-
-
建堆
| 排升序 | 建大堆 |
| 排降序 | 建小堆 |
一般利用向下調(diào)整算法建堆，思想是倒著調(diào)整，不是從根節(jié)點開始，而是從第一個非葉子節(jié)點開始調(diào)整(最后一個節(jié)點的父親)，(也可以用向上調(diào)整算法建堆，但是效率不如向下調(diào)整算法建堆，具體實現(xiàn)見下面的代碼和建堆時間復(fù)雜度的分析。)
-
建堆
-
-
利用堆刪除思想來進行排序
??堆刪除中用到了向下調(diào)整，那么我們這里還是以小堆為例，建出小堆之后，數(shù)組中的首尾數(shù)據(jù)進行交換，最小的數(shù)據(jù)(堆頂)放到了最后的位置，除去最后一個數(shù)據(jù)，對堆進行向下調(diào)整，再把堆頂(此時是次小的數(shù)據(jù))，與倒數(shù)第二個位置的數(shù)據(jù)交換……以此類推，整個調(diào)整完后，數(shù)組中的數(shù)據(jù)依次排列就是一個降序。
??如果是大堆的話，按照以上思想類比，整個調(diào)整完后，數(shù)組中的數(shù)據(jù)依次排列就是一個升序。
-
利用堆刪除思想來進行排序
??代碼實現(xiàn)如下：
堆排序時間復(fù)雜度為：O(N + N*logN)
//向上調(diào)整
void AdjustUp(HPdataType* a, int child)
{
//根據(jù)孩子找父親
int parent = (child - 1) / 2;
//孩子下標小于等于0就結(jié)束
while (child > 0)
{
//小堆情況下 孩子小于父親就交換
if (a[child] < a[parent])
{
HPdataType tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
//更新節(jié)點，繼續(xù)往上迭代找
child = parent;
parent = (child - 1) / 2;
}
else
{
//孩子大于等于父親就結(jié)束循環(huán)
break;
}
}
}
//向下調(diào)整
void AdjustDown(int* a,int n,int parent)
{
//根據(jù)父親找孩子
int child = parent * 2 + 1;//假設(shè)左孩子最小
while (child < n)
{
//小堆情況下
//如果右孩子存在的情況下必須保證小于n
if (child + 1 < n && a[child + 1] < a[child])
{
//如果右孩子小于左孩子
//那么就把下標位置給到右孩子
child++;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
//繼續(xù)往下迭代走
parent = child;
child = parent * 2 + 1;
}
else
{
//孩子大于父親，符合小堆性質(zhì)，跳出循環(huán)
break;
}
}
}
//交換
void Swap(HPdataType* p1, HPdataType* p2)
{
HPdataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void heapSort(int* a, int n)
{
//法一：向上調(diào)整建堆(可以想象堆插入的過程，調(diào)整前元素前面已經(jīng)滿足堆的性質(zhì))
/*for(int i = 1;i < n;i++)
{
AdjustUp(a, i);
}*/
//法二：向下調(diào)整建堆(從最后一個葉子節(jié)點的父親開始倒著調(diào)整,因為葉子節(jié)點本來就可以看成堆)
//O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
//首尾交換再向下調(diào)整
//O(N*logN)
int end = n - 1;
while(end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
int main()
{
int a[] = {8,40,91,14,39,72,4,81};
heapSort(a, sizeof(a) / sizeof(int));
}
3.5 建堆時間復(fù)雜度
??向下調(diào)整建堆時間復(fù)雜度：O(N)
??向上調(diào)整建堆時間復(fù)雜度：O(N*logN)
ps：可以推算一下堆排序的時間復(fù)雜度，計算過程與向上調(diào)整建堆類似。
按照這樣的推理計算，我們很明顯觀察到向下調(diào)整算法建堆比向上調(diào)整算法建堆效率要高的多，所以以我們以后選擇向下調(diào)整算法建堆會更好！
四、二叉樹鏈式結(jié)構(gòu)及實現(xiàn)
4.1 前置說明
在學(xué)習(xí)二叉樹的基本操作前，需先要創(chuàng)建一棵二叉樹，然后才能學(xué)習(xí)其相關(guān)的基本操作。由于現(xiàn)在大家對二
叉樹結(jié)構(gòu)掌握還不夠深入，為了降低大家學(xué)習(xí)成本，此處手動快速創(chuàng)建一棵簡單的二叉樹，快速進入二叉樹
操作學(xué)習(xí)，等二叉樹結(jié)構(gòu)了解的差不多時，我們反過頭再來研究二叉樹真正的創(chuàng)建方式。
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail\n");
return NULL;
}
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}
??注意：上述代碼并不是創(chuàng)建二叉樹的方式，真正創(chuàng)建二叉樹方式后面詳解重點講解。
再看二叉樹基本操作前，再回顧下二叉樹的概念，二叉樹是：
- 空樹
- 非空：根節(jié)點，根節(jié)點的左子樹、根節(jié)點的右子樹組成的。
從概念中可以看出，二叉樹定義是遞歸式的，因此后面基本操作中基本都是按照該概念實現(xiàn)的。
4.2 二叉樹的遍歷
學(xué)習(xí)二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。所謂
二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點進行相應(yīng)的操作，并且每個節(jié)點只操作一次。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎(chǔ)。
前中后序遍歷
按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷：
- 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之前?！?code>根->左子樹->右子樹】
- 中序遍歷(Inorder Traversal)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之中（間）?！?code>左子樹->根->右子樹】
- 后序遍歷(Postorder Traversal)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之后。【
左子樹->右子樹->根】
??ps：N代表空樹訪問
前序遍歷結(jié)果：
1 -> 2 -> 3 -> N -> N -> N -> 4 -> 5 -> N -> N -> 6 -> N -> N
中序遍歷結(jié)果：N -> 3 -> N -> 2 -> N -> 1 -> N -> 5 -> N -> 4 -> N -> 6 -> N
后序遍歷結(jié)果：N -> N -> 3 -> N -> 2 -> N -> N -> 5 -> N -> N -> 6 -> 4 -> 1
??前序遍歷代碼如下：
//前序遍歷
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
int main()
{
BTNode* root = CreatBinaryTree();
PrevOrder(root);
}
打印結(jié)果：
??遞歸展開圖：
??中序遍歷代碼如下：
//中序遍歷
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
int main()
{
BTNode* root = CreatBinaryTree();
InOrder(root);
}
打印結(jié)果：
??后序遍歷代碼如下：
//后序遍歷
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
int main()
{
BTNode* root = CreatBinaryTree();
PostOrder(root);
}
打印結(jié)果：
遍歷時間復(fù)雜度為O(N)，空間復(fù)雜度是O(h)，h是高度，范圍是[logN,N]
??ps：中序遍歷和后序遍歷遞歸展開圖，小伙伴們可以嘗試自己畫一畫，博主這里就不放了。
層序遍歷
?? 除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設(shè)二叉樹的根節(jié)點所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點出發(fā)，首先訪問第一層的樹根節(jié)點，然后從左到右訪問第2層上的節(jié)點，接著是第三層的節(jié)點，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點的過程就是層序遍歷。
隊列實現(xiàn)（先進先出）：當樹的根節(jié)點不為空時，讓其先進入隊列，在隊列不為空的情況下，輸出隊頭的元素， 同時且節(jié)點孩子存在的情況下入隊列。
我們這里拷貝之前隊列講解的代碼
Queue.h文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//鏈式隊列
typedef struct BinaryTreeNode* QDataType;
//每個節(jié)點
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QueueNode;
//整個隊列的結(jié)構(gòu)
typedef struct Queue
{
QueueNode* phead;//記錄鏈表頭
QueueNode* ptail;//記錄鏈表尾
int size;//隊列的大小
}Queue;
//隊列的初始化
void QueueInit(Queue* pqe);
//隊列的銷毀
void QueueDestroy(Queue* pqe);
//隊尾入隊列
void QueuePush(Queue* pqe, QDataType x);
//隊頭出隊列
void QueuePop(Queue* pqe);
//獲取隊頭的數(shù)據(jù)
QDataType QueueFront(Queue* pqe);
//獲取隊尾的數(shù)據(jù)
QDataType QueueBack(Queue* pqe);
//獲取隊列中有效數(shù)據(jù)個數(shù)
int QueueSize(Queue* pqe);
//判斷隊列是否為空
bool QueueEmpty(Queue* pqe);
Queue.c文件
#include"Queue.h"
//隊列的初始化
void QueueInit(Queue* pqe)
{
assert(pqe);
pqe->phead = pqe->ptail = NULL;
pqe->size = 0;
}
//隊列的銷毀
void QueueDestroy(Queue* pqe)
{
assert(pqe);
QueueNode* cur = pqe->phead;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pqe->phead = pqe->ptail = NULL;
pqe->size = 0;
}
//隊尾入隊列
void QueuePush(Queue* pqe, QDataType x)
{
assert(pqe);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail\n");
return;
}
newnode->data = x;
newnode->next = NULL;
//分為空節(jié)點和非空節(jié)點
if (pqe->phead == NULL)
{
//ptial為斷言，為了避免phead與ptail同時指向NULL
assert(pqe->ptail == NULL);
pqe->phead = pqe->ptail = newnode;
}
else
{
pqe->ptail->next = newnode;
pqe->ptail = newnode;
}
pqe->size++;
}
//隊頭出隊列
void QueuePop(Queue* pqe)
{
assert(pqe);
assert(!QueueEmpty(pqe));
//分為一個節(jié)點和多個節(jié)點
if (pqe->phead->next == NULL)
{
free(pqe->phead);
pqe->phead = pqe->ptail = NULL;
}
else
{
QueueNode* next = pqe->phead->next;
free(pqe->phead);
pqe->phead = next;
}
pqe->size--;
}
//獲取隊頭的數(shù)據(jù)
QDataType QueueFront(Queue* pqe)
{
assert(pqe);
assert(!QueueEmpty(pqe));
return pqe->phead->data;
}
//獲取隊尾的數(shù)據(jù)
QDataType QueueBack(Queue* pqe)
{
assert(pqe);
assert(!QueueEmpty(pqe));
return pqe->ptail->data;
}
//獲取隊列中有效數(shù)據(jù)個數(shù)
int QueueSize(Queue* pqe)
{
assert(pqe);
return pqe->size;
}
//判斷隊列是否為空
bool QueueEmpty(Queue* pqe)
{
assert(pqe);
//return pqe->phead == NULL && pqe->ptail == NULL;
return pqe->size == 0;
}
test.c文件
#include "Queue.h"
// 層序遍歷
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
//根節(jié)點入隊列
if (root != NULL)
QueuePush(&q, root);
//隊列不為空
while (!QueueEmpty(&q))
{
//輸出隊頭的元素
BTNode* front = QueueFront(&q);
printf("%d ", front->data);
QueuePop(&q);
//左孩子和右孩子都存在，就入隊列
if (front->left != NULL)
QueuePush(&q, front->left);
if (front->right != NULL)
QueuePush(&q, front->right);
}
QueueDestroy(&q);
}
判斷二叉樹是否是完全二叉樹
// 判斷二叉樹是否是完全二叉樹(層序遍歷思想)
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root == NULL)
QueuePush(&q, root);
//隊列不為空
while (!QueueEmpty(&q))
{
//節(jié)點入隊列
BTNode* front = QueueFront(&q);
QueuePop(&q);
//遇到空樹就跳出循環(huán)
if (front == NULL)
break;
//左右子樹入隊列
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
//繼續(xù)往后尋找，只要遇到非空說明不是完全二叉樹 返回false
//空樹后面還是空說明是完全二叉樹返回true
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
QueueDestroy(&q);
return false;
}
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
QueueDestroy(&q);
return true;
}
4.3 二叉樹的基本操作
求二叉樹的節(jié)點個數(shù)
// 二叉樹節(jié)點個數(shù)
//法一：遍歷計數(shù)(使用完后需要將size置為0)
//int size = 0;
//void BinaryTreeSize(BTNode* root)
//{
// if (root == NULL)
// return;
// size++;
//
// BinaryTreeSize(root->left);
// BinaryTreeSize(root->right);
//}
//法二：分治算法
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
return 0;
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
求二叉樹的葉子節(jié)點個數(shù)
// 二叉樹葉子節(jié)點個數(shù)
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
求二叉樹的高度
//二叉樹的高度
int BinaryTreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
int leftHeight = BinaryTreeHeight(root->left);
int RightHeight = BinaryTreeHeight(root->right);
return leftHeight > RightHeight ? leftHeight + 1 : RightHeight + 1;
}
二叉樹第k層節(jié)點個數(shù)
// 二叉樹第k層節(jié)點個數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
//層數(shù)都是從1開始
assert(k > 0);
//root 為空返回0
if (root == NULL)
return 0;
//root為空且k = 1時，返回1
if (k == 1)
return 1;
//分治：左子樹和右子樹
return BinaryTreeLevelKSize(root->left, k - 1)
+ BinaryTreeLevelKSize(root->right, k - 1);
}
二叉樹查找值為x的節(jié)點
// 二叉樹查找值為x的節(jié)點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
//分治
BTNode* ret1 = BinaryTreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2)
return ret2;
//子樹都沒找到返回空
return NULL;
}
4.4 經(jīng)典題型：二叉樹的構(gòu)建及遍歷
?? ?？途W(wǎng)鏈接
文章來源：http://www.zghlxwxcb.cn/news/detail-478657.html
#include <stdio.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail\n");
return NULL;
}
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
//構(gòu)建樹（前序遍歷）
BTNode* CreateTree(char* a,int* pi)
{
if(a[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = BuyNode(a[*pi]);
(*pi)++;
root->left = CreateTree(a,pi);
root->right = CreateTree(a,pi);
return root;
}
//中序遍歷輸出
void InOrder(BTNode* root)
{
if(root == NULL)
return;
InOrder(root->left);
printf("%c ",root->data);
InOrder(root->right);
}
int main() {
char str[100];
scanf("%s",str);
int i = 0;
BTNode* root = CreateTree(str,&i);
InOrder(root);
printf("\n");
return 0;
}
????本章節(jié)完，后續(xù)會補充二叉樹進階內(nèi)容知識，小伙伴們可以持續(xù)關(guān)注，若本篇文章對你有幫助的話，可以三連支持博主哦~，另外本篇內(nèi)容有編寫有誤的話，可以私聊博主進行糾正！文章來源地址http://www.zghlxwxcb.cn/news/detail-478657.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法篇】深入淺出——二叉樹（詳解）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
