柚子快報(bào)邀請(qǐng)碼778899分享：c語(yǔ)言 手撕數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)
柚子快報(bào)邀請(qǐng)碼778899分享：c語(yǔ)言 手撕數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)
?
1.樹(shù)
樹(shù)的基本概念與結(jié)構(gòu)
樹(shù)是?種?線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)，它是由 n（n>=0） 個(gè)有限結(jié)點(diǎn)組成?個(gè)具有層次關(guān)系的集合。把它叫做樹(shù)是因?yàn)樗雌饋?lái)像?棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，?葉朝下的。
? 有?個(gè)特殊的結(jié)點(diǎn)，稱(chēng)為根結(jié)點(diǎn)，根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。
? 除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成 M(M>0) 個(gè)互不相交的集合 T1、T2、……、Tm ，其中每?個(gè)集合Ti(1 <= i <= m) ?是?棵結(jié)構(gòu)與樹(shù)類(lèi)似的?樹(shù)。每棵?樹(shù)的根結(jié)點(diǎn)有且只有?個(gè)前驅(qū)，可以有 0 個(gè)或多個(gè)后繼。因此，樹(shù)是遞歸定義的。
下面的A就是根節(jié)點(diǎn)，沒(méi)有前驅(qū)節(jié)點(diǎn)的
?非樹(shù)形結(jié)構(gòu)：
? ?樹(shù)是不相交的（如果存在相交就是圖了，圖以后得課程會(huì)有講解）
? 除了根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)有且僅有一個(gè)父節(jié)點(diǎn)
? 一棵N個(gè)節(jié)點(diǎn)的數(shù)有N-1條邊
樹(shù)相關(guān)術(shù)語(yǔ)
?
2.二叉樹(shù)
??結(jié)點(diǎn)/雙親結(jié)點(diǎn)：若?個(gè)結(jié)點(diǎn)含有?結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)稱(chēng)為其?結(jié)點(diǎn)的?結(jié)點(diǎn)； 如上圖：A是B的?結(jié)點(diǎn)
??結(jié)點(diǎn)/孩?結(jié)點(diǎn)：?個(gè)結(jié)點(diǎn)含有的?樹(shù)的根結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的?結(jié)點(diǎn)； 如上圖：B是A的孩?結(jié)點(diǎn)?結(jié)點(diǎn)的度：?個(gè)結(jié)點(diǎn)有?個(gè)孩?，他的度就是多少；?如A的度為6，F(xiàn)的度為2，K的度為0
?樹(shù)的度：?棵樹(shù)中，最?的結(jié)點(diǎn)的度稱(chēng)為樹(shù)的度； 如上圖：樹(shù)的度為 6
?葉?結(jié)點(diǎn)/終端結(jié)點(diǎn)：度為 0 的結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn)； 如上圖： B、C、H、I… 等結(jié)點(diǎn)為葉結(jié)點(diǎn)
?分?結(jié)點(diǎn)/?終端結(jié)點(diǎn)：度不為 0 的結(jié)點(diǎn)； 如上圖： D、E、F、G… 等結(jié)點(diǎn)為分?結(jié)點(diǎn)
?兄弟結(jié)點(diǎn)：具有相同?結(jié)點(diǎn)的結(jié)點(diǎn)互稱(chēng)為兄弟結(jié)點(diǎn)(親兄弟)； 如上圖： B、C 是兄弟結(jié)點(diǎn)
?結(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第 1 層，根的?結(jié)點(diǎn)為第 2 層，以此類(lèi)推；
?樹(shù)的?度或深度：樹(shù)中結(jié)點(diǎn)的最?層次； 如上圖：樹(shù)的?度為 4
?結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分?上的所有結(jié)點(diǎn)；如上圖： A 是所有結(jié)點(diǎn)的祖先
?路徑：?條從樹(shù)中任意節(jié)點(diǎn)出發(fā)，沿?節(jié)點(diǎn)-?節(jié)點(diǎn)連接，達(dá)到任意節(jié)點(diǎn)的序列；?如A到Q的路徑為： A-E-J-Q；H到Q的路徑H-D-A-E-J-Q
??孫：以某結(jié)點(diǎn)為根的?樹(shù)中任?結(jié)點(diǎn)都稱(chēng)為該結(jié)點(diǎn)的?孫。如上圖：所有結(jié)點(diǎn)都是A的?孫
?森林：由 m（m>0） 棵互不相交的樹(shù)的集合稱(chēng)為森林；
樹(shù)的表示
孩子兄弟表示法：
樹(shù)結(jié)構(gòu)相對(duì)線(xiàn)性表就?較復(fù)雜了，要存儲(chǔ)表?起來(lái)就?較?煩了，既然保存值域，也要保存結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系，實(shí)際中樹(shù)有很多種表??式如：雙親表?法，孩?表?法、孩?雙親表?法以及孩?兄弟表?法等。我們這?就簡(jiǎn)單的了解其中最常?的孩?兄弟表?法
struct TreeNode
{
struct Node* child; // 左邊開(kāi)始的第?個(gè)孩?結(jié)點(diǎn)
struct Node* brother; // 指向其右邊的下?個(gè)兄弟結(jié)點(diǎn)
int data; // 結(jié)點(diǎn)中的數(shù)據(jù)域
}
?
?
我們不用提前知道有多少個(gè)節(jié)點(diǎn)，通過(guò)這種結(jié)構(gòu)體我們就能找到所有的節(jié)點(diǎn)
樹(shù)形結(jié)構(gòu)實(shí)際運(yùn)用場(chǎng)景
?件系統(tǒng)是計(jì)算機(jī)存儲(chǔ)和管理?件的?種?式，它利?樹(shù)形結(jié)構(gòu)來(lái)組織和管理?件和?件夾。在?件系統(tǒng)中，樹(shù)結(jié)構(gòu)被?泛應(yīng)?，它通過(guò)?結(jié)點(diǎn)和?結(jié)點(diǎn)之間的關(guān)系來(lái)表?不同層級(jí)的?件和?件夾之間的關(guān)聯(lián)。
?
2.二叉樹(shù)
二叉樹(shù)是樹(shù)形結(jié)構(gòu)的一種
在樹(shù)形結(jié)構(gòu)中，我們最常?的就是?叉樹(shù)，?棵?叉樹(shù)是結(jié)點(diǎn)的?個(gè)有限集合，該集合由?個(gè)根結(jié)點(diǎn)加上兩棵別稱(chēng)為左?樹(shù)和右?樹(shù)的?叉樹(shù)組成或者為空
從上圖可以看出?叉樹(shù)具備以下特點(diǎn)：
?叉樹(shù)不存在度?于 2 的結(jié)點(diǎn) ?叉樹(shù)的?樹(shù)有左右之分，次序不能顛倒，因此?叉樹(shù)是有序樹(shù)
注意：對(duì)于任意的?叉樹(shù)都是由以下?種情況復(fù)合?成的
滿(mǎn)二叉樹(shù)
?個(gè)?叉樹(shù)，如果每?個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最?值，則這個(gè)?叉樹(shù)就是滿(mǎn)?叉樹(shù)。也就是說(shuō)，如果?個(gè)?叉樹(shù)的層數(shù)為 K ，且結(jié)點(diǎn)總數(shù)是 2k - 1 ，則它就是滿(mǎn)?叉樹(shù)。
完全二叉樹(shù)
完全?叉樹(shù)是效率很?的數(shù)據(jù)結(jié)構(gòu)，完全?叉樹(shù)是由滿(mǎn)?叉樹(shù)?引出來(lái)的。對(duì)于深度為 K 的，有 n 個(gè)結(jié)點(diǎn)的?叉樹(shù)，當(dāng)且僅當(dāng)其每?個(gè)結(jié)點(diǎn)都與深度為K的滿(mǎn)?叉樹(shù)中編號(hào)從 1 ? n 的結(jié)點(diǎn)??對(duì)應(yīng)時(shí)稱(chēng)之為完全?叉樹(shù)。要注意的是滿(mǎn)?叉樹(shù)是?種特殊的完全?叉樹(shù)。
假設(shè)二叉樹(shù)層次為K
除了第K層外，每層節(jié)點(diǎn)的個(gè)數(shù)達(dá)到了最大節(jié)點(diǎn)數(shù)，第K層節(jié)點(diǎn)個(gè)數(shù)不一定達(dá)到最大節(jié)點(diǎn)數(shù)
對(duì)于下面的圖，因?yàn)橥耆鏄?shù)節(jié)點(diǎn)的順序是從左到右的，
那么下面的就不是一個(gè)完全二叉樹(shù)
完全二叉樹(shù)就是從左到右節(jié)點(diǎn)依次增加
滿(mǎn)二叉樹(shù)是完全二叉樹(shù)的一種，但是完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)
當(dāng)完全二叉樹(shù)的節(jié)點(diǎn)最大時(shí)，那么這個(gè)完全二叉樹(shù)就是滿(mǎn)二叉樹(shù)了
滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù)
但是完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)
二叉樹(shù)的性質(zhì)
根據(jù)滿(mǎn)?叉樹(shù)的特點(diǎn)可知：
1）若規(guī)定根結(jié)點(diǎn)的層數(shù)為 1 ，則?棵?空?叉樹(shù)的第i層上最多有 2^(i-1) 個(gè)結(jié)點(diǎn)
2）若規(guī)定根結(jié)點(diǎn)的層數(shù)為 1 ，則深度為 h 的?叉樹(shù)的最?結(jié)點(diǎn)數(shù)是 2^h - 1
3）若規(guī)定根結(jié)點(diǎn)的層數(shù)為 1 ，具有 n 個(gè)結(jié)點(diǎn)的滿(mǎn)?叉樹(shù)的深度 ( log以2為底， n+1 為對(duì)數(shù))
對(duì)于這個(gè)性質(zhì)三來(lái)說(shuō)的話(huà)，2^h-1=n 那么我們就能得到性質(zhì)三
?
二叉樹(shù)存儲(chǔ)結(jié)構(gòu)
?叉樹(shù)?般可以使?兩種結(jié)構(gòu)存儲(chǔ)，?種順序結(jié)構(gòu)，?種鏈?zhǔn)浇Y(jié)構(gòu)。
順序結(jié)構(gòu)
順序結(jié)構(gòu)存儲(chǔ)就是使?數(shù)組來(lái)存儲(chǔ)，?般使?數(shù)組只適合表?完全?叉樹(shù)，因?yàn)椴皇峭耆?叉樹(shù)會(huì)有空間的浪費(fèi)，完全?叉樹(shù)更適合使?順序結(jié)構(gòu)存儲(chǔ)。
現(xiàn)實(shí)中我們通常把堆（?種?叉樹(shù)）使?順序結(jié)構(gòu)的數(shù)組來(lái)存儲(chǔ)，需要注意的是這?的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事，?個(gè)是數(shù)據(jù)結(jié)構(gòu)，?個(gè)是操作系統(tǒng)中管理內(nèi)存的?塊區(qū)域分段
鏈?zhǔn)浇Y(jié)構(gòu)
?叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，?鏈表來(lái)表??棵?叉樹(shù)，即?鏈來(lái)指?元素的邏輯關(guān)系。 通常的?法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針?lè)謩e?來(lái)給出該結(jié)點(diǎn)左孩?和右孩?所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址 。鏈?zhǔn)浇Y(jié)構(gòu)?分為?叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中?般都是?叉鏈。后?課程學(xué)到?階數(shù)據(jù)結(jié)構(gòu)如紅?樹(shù)等會(huì)?到三叉鏈。
3.實(shí)現(xiàn)順序結(jié)構(gòu)二叉樹(shù)
?般堆使?順序結(jié)構(gòu)的數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)，堆是?種特殊的?叉樹(shù)，具有?叉樹(shù)的特性的同時(shí)，還具備其他的特性
堆的概念與結(jié)構(gòu)
堆分為小堆和大堆?
小堆我們也稱(chēng)之為小根堆
堆具有以下性質(zhì)：
? 堆中某個(gè)結(jié)點(diǎn)的值總是不?于或不?于其?結(jié)點(diǎn)的值；
? 堆總是?棵完全?叉樹(shù)。
父節(jié)點(diǎn)比孩子節(jié)點(diǎn)大就是大根堆
子節(jié)點(diǎn)比父節(jié)點(diǎn)大就是小根堆
小根堆的堆頂是最小值
大根堆的堆頂是最大值
將堆中的數(shù)據(jù)存儲(chǔ)到數(shù)組中，數(shù)組不一定是有序的，因?yàn)閿?shù)的排序是從左到右的
對(duì)于下面的二叉樹(shù)
對(duì)于15，就是這個(gè)數(shù)組下標(biāo)為1的數(shù)據(jù)，根據(jù)性質(zhì)一我們得到(1-1)/2=0
那么這個(gè)節(jié)點(diǎn)的雙親節(jié)點(diǎn)的下標(biāo)是0，就是上面的10
對(duì)于56，就是這個(gè)數(shù)組下標(biāo)為2的數(shù)據(jù)，根據(jù)性質(zhì)一我們得到(2-1)/2=0
那么這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)是下標(biāo)為0的10
對(duì)于25，就是這個(gè)數(shù)下標(biāo)為3的數(shù)據(jù)，根據(jù)性質(zhì)一我們得到(3-1)/2=1
那么這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)是下標(biāo)為1的15
所以我們通過(guò)子節(jié)點(diǎn)下標(biāo)就能求出父節(jié)點(diǎn)
對(duì)于父節(jié)點(diǎn)：
左節(jié)點(diǎn)：2i+1
右節(jié)點(diǎn): 2i+2
如果右節(jié)點(diǎn)的2i+2超過(guò)了n，那么就越界了
堆的向上調(diào)整算法
我們向堆中插入一個(gè)數(shù)據(jù)16，但是插入之后就不是小堆了
所以我們要進(jìn)行調(diào)整了
?
我們通過(guò)(i-1)/2能夠找到剛剛插入的16的父節(jié)點(diǎn)56
找到之后我們進(jìn)行兩個(gè)數(shù)據(jù)的比較，誰(shuí)小誰(shuí)就進(jìn)行向上調(diào)整
那么我們就將16和56交換位置
然后16就從i=6的位置換到i=2的位置，
我們用16找到父節(jié)點(diǎn)10
進(jìn)行兩個(gè)數(shù)據(jù)的比較，因?yàn)?0<16，那么我們就不用做出調(diào)整了，最終的結(jié)果就是下圖
那么這個(gè)就是堆的向上調(diào)整算法
?如果插入的是6的話(huà)，那么最后的結(jié)果就是
?
向下調(diào)整算法
出堆：刪除數(shù)據(jù)
出的是堆頂?shù)臄?shù)據(jù)，就是下標(biāo)為0的數(shù)據(jù)，但是不好刪除
但是假如我們刪除的是最后一個(gè)數(shù)據(jù)的話(huà)就很好解決
直接size--
將70和10的位置進(jìn)行換一下，然后size--得到了：
那么現(xiàn)在我們只需要將這個(gè)堆變成小堆就行了
現(xiàn)在的70是父節(jié)點(diǎn)，我們通過(guò)2i+1得到左邊的子節(jié)點(diǎn)，比較左右的兩個(gè)子節(jié)點(diǎn)，挑選出小的，
然后將小的子節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行交換，那么最后我們就得到了：
對(duì)于25和30來(lái)說(shuō)的話(huà)，現(xiàn)在的70是父節(jié)點(diǎn)，因?yàn)槲覀兊男《研枰腹?jié)點(diǎn)小于子節(jié)點(diǎn)
那么我們需要挑選出小的子節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行交換
那么最后我們就得到了小堆
出堆的過(guò)程：先將下標(biāo)為0的數(shù)據(jù)和最后一個(gè)數(shù)據(jù)進(jìn)行交換，然后我們進(jìn)行size--刪除這個(gè)要?jiǎng)h除的數(shù)據(jù)
然后我們進(jìn)行一系列的操作將這個(gè)堆變成小堆
那么我們這里用到了向下調(diào)整算法
堆排序
排升序--大堆
排降序--小堆
//冒泡排序
//時(shí)間復(fù)雜度為O(N^2)
void BubbleSort(int* arr, int n)//數(shù)組以及數(shù)組中的有效數(shù)據(jù)個(gè)數(shù)
{
for (int i = 0; i < n; i++)
{
int exchange = 0;
for (int j = 0; j < n - i - 1; j++)
{
//升序
if (arr[j] > arr[j + 1])//大的在后面，那么我們就進(jìn)行交換
{
exchange = 1;
Swap(&arr[j], &arr[j + 1]);
}
}
if (exchange == 0)
{
//那么就說(shuō)明我們經(jīng)歷了一趟內(nèi)循環(huán)，我們的exchange并沒(méi)有改變，就說(shuō)明這個(gè)數(shù)組可能之前就是有序的
break;
}
}
}
/*
向上調(diào)整算法的時(shí)間復(fù)雜度和層次有關(guān)的
2^k-1=n n是總節(jié)點(diǎn)個(gè)數(shù)
那么k=log(n+1)
那么向上調(diào)整算法的最差的情況是log(N)
因?yàn)槲覀兿蛏险{(diào)整算法在這里的外面還有層循環(huán)，那么時(shí)間復(fù)雜度是Nlog(N)
向上調(diào)整算法的時(shí)間復(fù)雜度也是log(N)
那么這里的堆排序的時(shí)間復(fù)雜度是O(n*log n)
*/
//堆排序
//期望空間復(fù)雜度是O(1) ，不額外的開(kāi)辟空間
//時(shí)間復(fù)雜度是O()
void HeapSort(int* arr, int n)
{
//根據(jù)數(shù)組來(lái)建堆,那么我們就需要便利數(shù)組
//建小堆---降序
for (int i = 0; i < n; i++)
{
AdjustUp(arr, i);//我們給的參數(shù)是i,就是開(kāi)始 調(diào)整數(shù)字的 下標(biāo)，我們是從數(shù)組第一個(gè)元素進(jìn)行調(diào)整的，i=0開(kāi)始的
}
//循環(huán)將堆頂數(shù)據(jù)跟最后位置的數(shù)據(jù)（會(huì)變化，每次減小一個(gè)數(shù)據(jù)）進(jìn)行交換
int end = n - 1;//n是數(shù)組的有效個(gè)數(shù)，那么最后一個(gè)數(shù)據(jù)的下標(biāo)是n-1
while (end>0)//end會(huì)一直--，但是end必須大于0
{
Swap(&arr[0], &arr[end]);//將第一個(gè)數(shù)據(jù)和最后一個(gè)數(shù)據(jù)進(jìn)行交換
//那么我們就要對(duì)現(xiàn)在的剩下的堆進(jìn)行調(diào)整
//我們采用向下調(diào)整的方法
AdhustDown(arr, 0, end);//我們從根進(jìn)行調(diào)整，那么第二個(gè)參數(shù)就是0
//n-1=end,就是我們只需要對(duì)剩下的n-1個(gè)數(shù)據(jù)進(jìn)行向下調(diào)整，那么第三個(gè)參數(shù)就是我們調(diào)整的有效數(shù)據(jù)n-1個(gè)
end--;
}
}
/*
我們先用向上調(diào)整法將給的數(shù)組進(jìn)行建小堆的操作
然后建完小堆之后我們利用循環(huán)將堆頂?shù)臄?shù)據(jù)和最后一個(gè)數(shù)據(jù)進(jìn)行交換
循環(huán)停止的條件是end>0
在循環(huán)中，我們先利用交換函數(shù)將堆頂數(shù)據(jù)和堆尾數(shù)據(jù)進(jìn)行交換
然后利用我們的向下排序的方法進(jìn)行正確的小堆排序
然后進(jìn)行end--的操作
每次我們通過(guò)上面的操作就能將堆頂?shù)淖钚〉臄?shù)據(jù)放到后面，然后剩下的就是較大的數(shù)字
最后我們就實(shí)現(xiàn)了降序的操作
*/
向上調(diào)整法
//堆的向上調(diào)整算法
//下面的代碼是建小堆的
//如果我們要建大堆的話(huà)，我們需要將循環(huán)里面的條件語(yǔ)句的條件進(jìn)行改變
//if (arr[child] > arr[parent])
//將大的數(shù)據(jù)往上放
void AdjustUp(HPDataType* arr, int child)//調(diào)整的是一個(gè)數(shù)組，第二個(gè)參數(shù)是要調(diào)整的數(shù)據(jù)的下標(biāo)，將孩子往父親的位置進(jìn)行調(diào)整
{
int parent = (child - 1) / 2;//根據(jù)孩子求父親的下標(biāo)
//不需要等于，child只要走到根節(jié)點(diǎn)的位置，根節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)不需要交換
while (child > 0)//當(dāng)child<0我們就停止向上調(diào)整了，因?yàn)樯厦婢蜎](méi)有父節(jié)點(diǎn)了
{
if (arr[child] > arr[parent])//如果孩子比父親小的話(huà)，那么就進(jìn)行換位置
{
//使用交換函數(shù)進(jìn)行數(shù)據(jù)的交換
Swap(&arr[parent], &arr[child]);
child = parent;//進(jìn)行完上面的交換操作之后，我們之前的child已經(jīng)變成了parent了
//那么我們接著進(jìn)行判斷，判斷現(xiàn)在的位置和父節(jié)點(diǎn)的大小，
//我們利用現(xiàn)有的child進(jìn)行父節(jié)點(diǎn)的尋找
//現(xiàn)在的child就是之前我們的parent的位置,是下標(biāo)，child到了parent下標(biāo)的位置
//我們利用新的child找新的父節(jié)點(diǎn)
//child走到parent的位置，parent走到(child - 1) / 2這個(gè)位置
parent = (child - 1) / 2;
}
else//child位置的值比parent位置的值大
{
break;
//我們不不用調(diào)整了,直接跳出
}
}
}
/*
進(jìn)行交換函數(shù)之后，我們?cè)鹊腸hild變成了parent了，就是位置變了
然后我們這個(gè)位置的數(shù)據(jù)相較于上面的數(shù)據(jù)還是子節(jié)點(diǎn)
我們要利用這個(gè)子節(jié)點(diǎn)去尋找上面的父節(jié)點(diǎn)
child = parent;
parent = (child - 1) / 2;
這兩句代碼
假如我們插入的數(shù)據(jù)是6
那么我們進(jìn)行完交換函數(shù)之后這個(gè)6就是新的parent
但是對(duì)于現(xiàn)在6的父節(jié)點(diǎn)來(lái)說(shuō),6還是子節(jié)點(diǎn)，只不過(guò)子節(jié)點(diǎn)有了新的位置
我們一開(kāi)始的parent是下標(biāo)，那么現(xiàn)在的child就是之前我們的parent的位置
*/
向下調(diào)整法
//向下調(diào)整法
//如果我們建大堆的話(huà)，我們需要將循環(huán)內(nèi)條件語(yǔ)句的條件進(jìn)行改變
//如果右孩子比左孩子要大，我們就進(jìn)行child++操作
//if (child + 1 < n && arr[child] < arr[child + 1])
//除了要改變這個(gè)，我們還要if (arr[child] > arr[parent])
//將大的孩子放上面去
void AdhustDown(HPDataType*arr, int parent, int n)
//第一個(gè)數(shù)據(jù)是我們要調(diào)整的數(shù)組，第二個(gè)參數(shù)是父節(jié)點(diǎn)，就是我們開(kāi)始進(jìn)行調(diào)整的位置的下標(biāo)對(duì)應(yīng)的元素，第三個(gè)是數(shù)組中有效的元素個(gè)數(shù)
{
//我們已知Parent，那么我們能夠通過(guò)2i+1或者2i+2找到這個(gè)父節(jié)點(diǎn)的左右子節(jié)點(diǎn)
int child = parent * 2 + 1;//左孩子
while (child { //找左右孩子中最小的那個(gè)，我們與父節(jié)點(diǎn)進(jìn)行交換操作 if (child+1 { //假設(shè)我們的子節(jié)點(diǎn)只有一個(gè)左節(jié)點(diǎn)的話(huà)，那么我們就可以通過(guò)child+1 //這個(gè)條件避免child++，避免了越界訪(fǎng)問(wèn)，我們直接讓左節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行交換 //child+1必須小于n我們才能往下進(jìn)行調(diào)整操作，避免越界訪(fǎng)問(wèn) //假設(shè)左邊的是56，右邊的是15 child++;//我們進(jìn)行child++操作，然后child就跑到了15的位置，然后我們將15和父節(jié)點(diǎn)進(jìn)行交換 } if (arr[child] > arr[parent])//如果子節(jié)點(diǎn)小于父節(jié)點(diǎn)的話(huà)我們就進(jìn)行交換 { Swap(&arr[child], &arr[parent]); //交換完成之后我們讓parent走到child的位置 parent =child ; //child走到當(dāng)前位置的左孩子的位置 child = parent * 2 + 1; } else//如果Parent比child小的話(huà)，那么我們就沒(méi)必要向下進(jìn)行調(diào)整了 { break;//我們直接跳出 } } } 我們不僅能用向上調(diào)整算法建堆，還能用向下調(diào)整算法建堆，那么我們?cè)撛趺醋瞿?/p> 我們先從i這個(gè)位置開(kāi)始，就是最后一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)開(kāi)始進(jìn)行向下調(diào)整 下面的堆是我們最開(kāi)始的數(shù)組的樣子，就是保持無(wú)序的狀態(tài) 進(jìn)行完操作之后我們讓i--,那么i就跑到20的位置了 然后我們讓20向下調(diào)整，因?yàn)樽庸?jié)點(diǎn)都比20小，那么我們就不進(jìn)行操作了 因?yàn)?0比17大，那么我們將20往上放，17往下放 然后因?yàn)?9比17大，那么將17往下放 那么經(jīng)過(guò)這么一系列的操作，我們就得到了一個(gè)大堆 那么究竟是向上建堆好還是向下建堆好呢？ 關(guān)于計(jì)算向下和向下兩種調(diào)整算法建堆時(shí)間復(fù)雜度 向下調(diào)整算法建堆的時(shí)間復(fù)雜度 那么最后我們得到的 向下調(diào)整算法建堆時(shí)間復(fù)雜度是O(N) 向上調(diào)整算法建堆的時(shí)間復(fù)雜度 總結(jié) 向上調(diào)整： 節(jié)點(diǎn)數(shù)量多的層*調(diào)整次數(shù)多 節(jié)點(diǎn)數(shù)量少的層*調(diào)整的次數(shù)少 向下調(diào)整： 節(jié)點(diǎn)數(shù)量多的層*調(diào)整次數(shù)少 節(jié)點(diǎn)數(shù)量少的層*調(diào)整次數(shù)多 建議是使用向下調(diào)整算法進(jìn)行建堆 建堆的時(shí)間復(fù)雜度是O(N) 下面的調(diào)整得物時(shí)間復(fù)雜度是O(N*logN) 那么堆排序的時(shí)間復(fù)雜度是O(N*logN) TOP-K問(wèn)題 TOP-K問(wèn)題：即求數(shù)據(jù)結(jié)合中前K個(gè)最?的元素或者最?的元素，?般情況下數(shù)據(jù)量都?較?。 ?如：專(zhuān)業(yè)前10名、世界500強(qiáng)、富豪榜、游戲中前100的活躍玩家等。 對(duì)于Top-K問(wèn)題，能想到的最簡(jiǎn)單直接的?式就是排序，但是：如果數(shù)據(jù)量?常?，排序就不太可取了(可能數(shù)據(jù)都不能?下?全部加載到內(nèi)存中)。最佳的?式就是?堆來(lái)解決，基本思路如下： 找最大的前k個(gè)數(shù)據(jù)： 取到的數(shù)據(jù)和堆頂比較，比較堆頂數(shù)據(jù)，誰(shuí)大誰(shuí)就跟堆頂交換（堆向下進(jìn)行調(diào)整） 那么小堆中的k個(gè)數(shù)據(jù)就是N個(gè)數(shù)據(jù)中的最大的前k個(gè)數(shù)據(jù) 我們先拿k個(gè)數(shù)據(jù)進(jìn)行建堆，那么在建堆操作之后我們要將剩下的N-K個(gè)數(shù)據(jù)拿過(guò)來(lái)進(jìn)行向下調(diào)整的操作 那么這種排序的時(shí)間復(fù)雜度就是O(N) void CreateNDate() { // 造數(shù)據(jù) int n = 100000; srand(time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return; } for (int i = 0; i < n; ++i) { int x = (rand() + i) % 1000000; fprintf(fin, "%d\n", x); } fclose(fin); } void TOPK() { int k = 0; printf("請(qǐng)輸入k："); scanf_s("%d", &k); //從文件中讀取前k個(gè)數(shù)據(jù)，建堆 const char* file = "data.txt"; FILE* fout = fopen(file, "r"); if (fout == NULL)//打開(kāi)失敗 { perror("fopen fail!"); exit(1); } //創(chuàng)建一個(gè)大小為k的數(shù)組,建小堆，找前k個(gè)最大的數(shù)據(jù) int* minHeap = (int*)malloc(k*sizeof(int)); //往堆內(nèi)放數(shù)據(jù) if (minHeap == NULL) { perror("malloc fail!"); exit(2); } //循環(huán)讀取文件內(nèi)的數(shù)據(jù) //從文件中讀取前K個(gè)數(shù)據(jù)， for (int i = 0; i < k; i++) { //從fout進(jìn)行讀取，讀取的數(shù)據(jù)類(lèi)型是%d,將讀取到的數(shù)據(jù)往數(shù)組內(nèi)進(jìn)行存儲(chǔ) fscanf_s(fout, "%d", &minHeap[i]); } //向下調(diào)整算法，建小堆 //調(diào)整建堆//我們從最后一個(gè)數(shù)的父節(jié)點(diǎn)進(jìn)行調(diào)整，最后一個(gè)數(shù)的下標(biāo)是k-1 for (int i = (k - 1 - 1) / 2; i>= 0; i--) { AdhustDown(minHeap, i, k); //我們從最后一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)進(jìn)行向上調(diào)整操作 //一開(kāi)始我們的i就被定義成了這個(gè)父節(jié)點(diǎn)的下標(biāo)的大小 } //那么我們建好堆之后我們就接著讀取文件中剩下的N-K個(gè)數(shù)據(jù) //我們進(jìn)行循環(huán)讀取 int x = 0;//我們創(chuàng)建一個(gè)x變量，將每次讀取的數(shù)據(jù)存在x中與堆頂?shù)臄?shù)據(jù)進(jìn)行循環(huán)比較 while (fscanf(fout,"%d",&x)!=EOF)//直到讀到文件末尾 { //讀取到的數(shù)據(jù)與堆頂?shù)臄?shù)據(jù)進(jìn)行比較 //如果比對(duì)頂值大，交換入堆 if (x > minHeap[0]) { minHeap[0] = x;//直接將x放到堆頂 //經(jīng)過(guò)上面的操作之后，那么這個(gè)堆就不是一個(gè)小堆了 //我們利用向下調(diào)整算法重新將這個(gè)堆變成小堆 AdhustDown(minHeap, 0, k); } } //走到這里我們已經(jīng)讀完了,那么這個(gè)堆剩下的數(shù)據(jù)就是這個(gè)文件前K個(gè)最大的數(shù)據(jù)了 for (int i = 0; i < k; i++) { printf("%d ", minHeap[i]); } fclose(fout); } 找最小的前k個(gè)數(shù)據(jù) 建大堆 取到的數(shù)據(jù)和堆頂比較，比較堆頂數(shù)據(jù)，誰(shuí)小誰(shuí)就跟堆頂交換（堆向下進(jìn)行調(diào)整） void CreateNDate() { // 造數(shù)據(jù) int n = 100000; srand(time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return; } for (int i = 0; i < n; ++i) { int x = (rand() + i) % 1000000; fprintf(fin, "%d\n", x); } fclose(fin); } void TOPK() { int k = 0; printf("請(qǐng)輸入k："); scanf_s("%d", &k); //從文件中讀取前k個(gè)數(shù)據(jù)，建堆 const char* file = "data.txt"; FILE* fout = fopen(file, "r"); if (fout == NULL)//打開(kāi)失敗 { perror("fopen fail!"); exit(1); } //創(chuàng)建一個(gè)大小為k的數(shù)組,建小堆，找前k個(gè)最大的數(shù)據(jù) int* minHeap = (int*)malloc(k*sizeof(int)); //往堆內(nèi)放數(shù)據(jù) if (minHeap == NULL) { perror("malloc fail!"); exit(2); } //循環(huán)讀取文件內(nèi)的數(shù)據(jù) //從文件中讀取前K個(gè)數(shù)據(jù)， for (int i = 0; i < k; i++) { //從fout進(jìn)行讀取，讀取的數(shù)據(jù)類(lèi)型是%d,將讀取到的數(shù)據(jù)往數(shù)組內(nèi)進(jìn)行存儲(chǔ) fscanf_s(fout, "%d", &minHeap[i]); } //向下調(diào)整算法，建小堆 //調(diào)整建堆//我們從最后一個(gè)數(shù)的父節(jié)點(diǎn)進(jìn)行調(diào)整，最后一個(gè)數(shù)的下標(biāo)是k-1 for (int i = (k - 1 - 1) / 2; i>= 0; i--) { AdhustDown(minHeap, i, k); //我們從最后一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)進(jìn)行向上調(diào)整操作 //一開(kāi)始我們的i就被定義成了這個(gè)父節(jié)點(diǎn)的下標(biāo)的大小 } //那么我們建好堆之后我們就接著讀取文件中剩下的N-K個(gè)數(shù)據(jù) //我們進(jìn)行循環(huán)讀取 int x = 0;//我們創(chuàng)建一個(gè)x變量，將每次讀取的數(shù)據(jù)存在x中與堆頂?shù)臄?shù)據(jù)進(jìn)行循環(huán)比較 while (fscanf(fout,"%d",&x)!=EOF)//直到讀到文件末尾 { //讀取到的數(shù)據(jù)與堆頂?shù)臄?shù)據(jù)進(jìn)行比較 //如果比對(duì)頂值大，交換入堆 if (x < minHeap[0]) { minHeap[0] = x;//直接將x放到堆頂 //經(jīng)過(guò)上面的操作之后，那么這個(gè)堆就不是一個(gè)小堆了 //我們利用向下調(diào)整算法重新將這個(gè)堆變成小堆 AdhustDown(minHeap, 0, k); } } //走到這里我們已經(jīng)讀完了,那么這個(gè)堆剩下的數(shù)據(jù)就是這個(gè)文件前K個(gè)最大的數(shù)據(jù)了 for (int i = 0; i < k; i++) { printf("%d ", minHeap[i]); } fclose(fout); } 兩個(gè)代碼的最大的區(qū)別就是如果我們要找前k個(gè)最大的數(shù)據(jù) 那么我們就讓這個(gè)數(shù)和堆頂?shù)臄?shù)進(jìn)行比較，如果這個(gè)數(shù)大于堆頂?shù)臄?shù)的話(huà)，我們就將堆頂數(shù)據(jù)賦值為這個(gè)數(shù) 如果我們找前k個(gè)最大的數(shù)據(jù)的話(huà)，那么就是相反 誰(shuí)小就去堆頂 改變這個(gè)條件就行了 順序結(jié)構(gòu)的二叉樹(shù)的具體實(shí)現(xiàn) Heap.h #pragma once #include #include #include #include #include //定義堆的結(jié)構(gòu)---底層結(jié)構(gòu)是數(shù)組 typedef int HPDataType; typedef struct Heap { int* arr; int size;//有效的數(shù)據(jù)個(gè)數(shù) int capacity;//空間大小 }HP; //堆的初始化 void HPInit(HP*php); //堆的銷(xiāo)毀 void HPDestroy(HP* php); //插入數(shù)據(jù) void HPPush(HP* php, HPDataType x); //刪除數(shù)據(jù) void HPPop(HP* php); //取堆頂數(shù)據(jù) HPDataType HPTop(HP* php);//將堆頂數(shù)據(jù)拿出來(lái)，但是我們不出堆 //判斷堆是否為空 bool HPEmpty(HP* php); //交換函數(shù) void Swap(int* x, int* y);//一定要傳地址才能進(jìn)行交換了 //堆的向上調(diào)整算法 void AdjustUp(HPDataType* arr, int child);//調(diào)整的是一個(gè)數(shù)組，第二個(gè)參數(shù)是要調(diào)整的數(shù)據(jù)的下標(biāo)，將孩子往父親的位置進(jìn)行調(diào)整 //向下調(diào)整法 void AdhustDown(HPDataType* arr, int parent, int n); Heap.c #define _CRT_SECURE_NO_WARNINGS 1 #include "Heap.h" //堆的初始化 void HPInit(HP* php) { assert(php); php->arr = NULL; php->size = php->capacity = 0; } //堆的銷(xiāo)毀 void HPDestroy(HP* php) { assert(php); if (php->arr)//不為空的話(huà)我們就進(jìn)行銷(xiāo)毀操作 { free(php->arr); } php->arr = NULL; php->size = php->capacity = 0; } //交換函數(shù) void Swap(int* x, int* y)//一定要傳地址才能進(jìn)行交換了 { int tmp = *x; *x = *y; *y = tmp; } //堆的向上調(diào)整算法 //下面的代碼是建小堆的 //如果我們要建大堆的話(huà)，我們需要將循環(huán)里面的條件語(yǔ)句的條件進(jìn)行改變 //if (arr[child] > arr[parent]) //將大的數(shù)據(jù)往上放 void AdjustUp(HPDataType* arr, int child)//調(diào)整的是一個(gè)數(shù)組，第二個(gè)參數(shù)是要調(diào)整的數(shù)據(jù)的下標(biāo)，將孩子往父親的位置進(jìn)行調(diào)整 { int parent = (child - 1) / 2;//根據(jù)孩子求父親的下標(biāo) //不需要等于，child只要走到根節(jié)點(diǎn)的位置，根節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)不需要交換 while (child > 0)//當(dāng)child<0我們就停止向上調(diào)整了，因?yàn)樯厦婢蜎](méi)有父節(jié)點(diǎn)了 { if (arr[child] < arr[parent])//如果孩子比父親小的話(huà)，那么就進(jìn)行換位置 { //使用交換函數(shù)進(jìn)行數(shù)據(jù)的交換 Swap(&arr[parent], &arr[child]); child = parent;//進(jìn)行完上面的交換操作之后，我們之前的child已經(jīng)變成了parent了 //那么我們接著進(jìn)行判斷，判斷現(xiàn)在的位置和父節(jié)點(diǎn)的大小， //我們利用現(xiàn)有的child進(jìn)行父節(jié)點(diǎn)的尋找 //現(xiàn)在的child就是之前我們的parent的位置,是下標(biāo)，child到了parent下標(biāo)的位置 //我們利用新的child找新的父節(jié)點(diǎn) //child走到parent的位置，parent走到(child - 1) / 2這個(gè)位置 parent = (child - 1) / 2; } else//child位置的值比parent位置的值大 { break; //我們不不用調(diào)整了,直接跳出 } } } /* 進(jìn)行交換函數(shù)之后，我們?cè)鹊腸hild變成了parent了，就是位置變了 然后我們這個(gè)位置的數(shù)據(jù)相較于上面的數(shù)據(jù)還是子節(jié)點(diǎn) 我們要利用這個(gè)子節(jié)點(diǎn)去尋找上面的父節(jié)點(diǎn) child = parent; parent = (child - 1) / 2; 這兩句代碼 假如我們插入的數(shù)據(jù)是6 那么我們進(jìn)行完交換函數(shù)之后這個(gè)6就是新的parent 但是對(duì)于現(xiàn)在6的父節(jié)點(diǎn)來(lái)說(shuō),6還是子節(jié)點(diǎn)，只不過(guò)子節(jié)點(diǎn)有了新的位置 我們一開(kāi)始的parent是下標(biāo)，那么現(xiàn)在的child就是之前我們的parent的位置 */ //插入數(shù)據(jù) void HPPush(HP* php, HPDataType x) { assert(php); //在插入之前我們需要判斷底層空間是否足夠 if (php->size == php->capacity)//說(shuō)明空間是不夠的 { //空間不夠我們就進(jìn)行擴(kuò)容操作 int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity; HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType)); if (tmp == NULL) { perror("ralloc,fail!"); exit(1); } //申請(qǐng)成功 php->arr = tmp;//將申請(qǐng)到的空間給數(shù)組 php->capacity = newcapacity;//將capacity進(jìn)行更新 } //插入數(shù)據(jù) php->arr[php->size] = x; //一開(kāi)始的size是0，那么我們就往數(shù)組中下標(biāo)為0的位置進(jìn)行插入數(shù)據(jù) //我們要進(jìn)行堆的向上調(diào)整，保證這個(gè)堆是小堆 //我們這里是一個(gè)個(gè)數(shù)據(jù)進(jìn)行插入的，所以一開(kāi)始的size是0 AdjustUp(php->arr, php->size); php->size++; //插入完數(shù)據(jù)之后我們需要進(jìn)行size++操作，因?yàn)槲覀兌嗔艘粋€(gè)有效數(shù)據(jù) } //向下調(diào)整法 //如果我們建大堆的話(huà)，我們需要將循環(huán)內(nèi)條件語(yǔ)句的條件進(jìn)行改變 //如果右孩子比左孩子要大，我們就進(jìn)行child++操作 //if (child + 1 < n && arr[child] < arr[child + 1]) //除了要改變這個(gè)，我們還要if (arr[child] > arr[parent]) //將大的孩子放上面去 void AdhustDown(HPDataType*arr, int parent, int n) //第一個(gè)數(shù)據(jù)是我們要調(diào)整的數(shù)組，第二個(gè)參數(shù)是父節(jié)點(diǎn)，就是我們開(kāi)始進(jìn)行調(diào)整的位置的下標(biāo)對(duì)應(yīng)的元素，第三個(gè)是數(shù)組中有效的元素個(gè)數(shù) { //我們已知Parent，那么我們能夠通過(guò)2i+1或者2i+2找到這個(gè)父節(jié)點(diǎn)的左右子節(jié)點(diǎn) int child = parent * 2 + 1;//左孩子 while (child { //找左右孩子中最小的那個(gè)，我們與父節(jié)點(diǎn)進(jìn)行交換操作 if (child + 1 < n && arr[child] > arr[child + 1]) { //假設(shè)我們的子節(jié)點(diǎn)只有一個(gè)左節(jié)點(diǎn)的話(huà)，那么我們就可以通過(guò)child+1 //這個(gè)條件避免child++，避免了越界訪(fǎng)問(wèn)，我們直接讓左節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行交換 //child+1必須小于n我們才能往下進(jìn)行調(diào)整操作，避免越界訪(fǎng)問(wèn) //假設(shè)左邊的是56，右邊的是15 child++;//我們進(jìn)行child++操作，然后child就跑到了15的位置，然后我們將15和父節(jié)點(diǎn)進(jìn)行交換 } if (arr[child] < arr[parent])//如果子節(jié)點(diǎn)小于父節(jié)點(diǎn)的話(huà)我們就進(jìn)行交換 { Swap(&arr[child], &arr[parent]); //交換完成之后我們讓parent走到child的位置 parent =child ; //child走到當(dāng)前位置的左孩子的位置 child = parent * 2 + 1; } else//如果Parent比child小的話(huà)，那么我們就沒(méi)必要向下進(jìn)行調(diào)整了 { break;//我們直接跳出 } } } //刪除數(shù)據(jù) void HPPop(HP* php) { assert(php&&php->size);//傳的數(shù)據(jù)不能為0并且數(shù)組內(nèi)有效的數(shù)據(jù)要大于0我們才能進(jìn)行刪除操作 //現(xiàn)在第一步我們將堆頂?shù)臄?shù)據(jù)和最后一個(gè)數(shù)據(jù)進(jìn)行交換 Swap(&php->arr[0], &php->arr[php->size - 1]); //那么我們現(xiàn)在就已將將原先的堆頂數(shù)據(jù)刪除了 //下面我們就需要解決將交換數(shù)據(jù)后的堆變成一個(gè)有效的小堆 php->size--; //我們現(xiàn)在進(jìn)行堆頂?shù)南蛳抡{(diào)整操作 AdhustDown(php->arr, 0,php->size);//我們調(diào)整的是這個(gè)數(shù)組，我們從堆頂開(kāi)始進(jìn)行調(diào)整，堆頂對(duì)應(yīng)的下標(biāo)數(shù)據(jù)為0,我們還要將堆里面的有效數(shù)據(jù)個(gè)數(shù)傳過(guò)去 } //判斷堆是否為空 bool HPEmpty(HP* php) { assert(php); return php->size == 0;//如果size是0的話(huà)，那么這個(gè)堆就是空的，返回值就是true } //取堆頂數(shù)據(jù) HPDataType HPTop(HP* php) { assert(php&&php->size);//傳過(guò)來(lái)的數(shù)據(jù)不能為空并且堆里面要有數(shù)據(jù)存在 return php->arr[0];//直接返回堆頂元素 } test.c #define _CRT_SECURE_NO_WARNINGS 1 #include "Heap.h" //冒泡排序 //時(shí)間復(fù)雜度為O(N^2) void BubbleSort(int* arr, int n)//數(shù)組以及數(shù)組中的有效數(shù)據(jù)個(gè)數(shù) { for (int i = 0; i < n; i++) { int exchange = 0; for (int j = 0; j < n - i - 1; j++) { //升序 if (arr[j] > arr[j + 1])//大的在后面，那么我們就進(jìn)行交換 { exchange = 1; Swap(&arr[j], &arr[j + 1]); } } if (exchange == 0) { //那么就說(shuō)明我們經(jīng)歷了一趟內(nèi)循環(huán)，我們的exchange并沒(méi)有改變，就說(shuō)明這個(gè)數(shù)組可能之前就是有序的 break; } } } /* 向上調(diào)整算法的時(shí)間復(fù)雜度和層次有關(guān)的 2^k-1=n n是總節(jié)點(diǎn)個(gè)數(shù) 那么k=log(n+1) 那么向上調(diào)整算法的最差的情況是log(N) 因?yàn)槲覀兿蛏险{(diào)整算法在這里的外面還有層循環(huán)，那么時(shí)間復(fù)雜度是Nlog(N) 向上調(diào)整算法的時(shí)間復(fù)雜度也是log(N) 那么這里的堆排序的時(shí)間復(fù)雜度是O(n*log n) */ //堆排序 //期望空間復(fù)雜度是O(1) ，不額外的開(kāi)辟空間 //時(shí)間復(fù)雜度是O() void HeapSort(int* arr, int n) { //根據(jù)數(shù)組來(lái)建堆,那么我們就需要便利數(shù)組 //建小堆---降序 // 向上調(diào)整算法建堆 //for (int i = 0; i < n; i++) //{ // AdjustUp(arr, i);//我們給的參數(shù)是i,就是開(kāi)始 調(diào)整數(shù)字的 下標(biāo)，我們是從數(shù)組第一個(gè)元素進(jìn)行調(diào)整的，i=0開(kāi)始的 //} //向下調(diào)整算法建堆 //我們需要通過(guò)最后一個(gè)元素的下標(biāo)n-1找到他的父節(jié)點(diǎn)，從這個(gè)點(diǎn)開(kāi)始進(jìn)行操作 //父節(jié)點(diǎn)：（n-1 -1）/2 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdhustDown(arr, i, n);//我們從i這個(gè)位置開(kāi)始向下調(diào)整 //i一開(kāi)始的位置就是最后一個(gè)數(shù)據(jù)的父節(jié)點(diǎn)，我們從這個(gè)父節(jié)點(diǎn)開(kāi)始向下操作 } //循環(huán)將堆頂數(shù)據(jù)跟最后位置的數(shù)據(jù)（會(huì)變化，每次減小一個(gè)數(shù)據(jù)）進(jìn)行交換 int end = n - 1;//n是數(shù)組的有效個(gè)數(shù)，那么最后一個(gè)數(shù)據(jù)的下標(biāo)是n-1 while (end>0)//end會(huì)一直--，但是end必須大于0 { Swap(&arr[0], &arr[end]);//將第一個(gè)數(shù)據(jù)和最后一個(gè)數(shù)據(jù)進(jìn)行交換 //那么我們就要對(duì)現(xiàn)在的剩下的堆進(jìn)行調(diào)整 //我們采用向下調(diào)整的方法 AdhustDown(arr, 0, end);//我們從根進(jìn)行調(diào)整，那么第二個(gè)參數(shù)就是0 //n-1=end,就是我們只需要對(duì)剩下的n-1個(gè)數(shù)據(jù)進(jìn)行向下調(diào)整，那么第三個(gè)參數(shù)就是我們調(diào)整的有效數(shù)據(jù)n-1個(gè) end--; } } /* 我們先用向上調(diào)整法將給的數(shù)組進(jìn)行建小堆的操作 然后建完小堆之后我們利用循環(huán)將堆頂?shù)臄?shù)據(jù)和最后一個(gè)數(shù)據(jù)進(jìn)行交換 循環(huán)停止的條件是end>0 在循環(huán)中，我們先利用交換函數(shù)將堆頂數(shù)據(jù)和堆尾數(shù)據(jù)進(jìn)行交換 然后利用我們的向下排序的方法進(jìn)行正確的小堆排序 然后進(jìn)行end--的操作 每次我們通過(guò)上面的操作就能將堆頂?shù)淖钚〉臄?shù)據(jù)放到后面，然后剩下的就是較大的數(shù)字 最后我們就實(shí)現(xiàn)了降序的操作 */ void test01() { HP hp;//創(chuàng)建變量 //初始化 HPInit(&hp); int arr[] = { 17,20,10,13,19,15 }; for (int i = 0; i < 6; i++) { //將這個(gè)數(shù)組內(nèi)的數(shù)據(jù)循環(huán)入堆 HPPush(&hp, arr[i]); } //刪除數(shù)據(jù)（出堆） //HPPop(&hp); while (!HPEmpty(&hp))//堆不為空的話(huà)，那么我們就打印堆頂數(shù)據(jù) { printf("%d ", HPTop(&hp)); HPPop(&hp);//刪除堆頂數(shù)據(jù)，換下一個(gè)數(shù)據(jù) } //銷(xiāo)毀 HPDestroy(&hp); } void CreateNDate() { // 造數(shù)據(jù) int n = 100000; srand(time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return; } for (int i = 0; i < n; ++i) { int x = (rand() + i) % 1000000; fprintf(fin, "%d\n", x); } fclose(fin); } void TOPK() { int k = 0; printf("請(qǐng)輸入k："); scanf_s("%d", &k); //從文件中讀取前k個(gè)數(shù)據(jù)，建堆 const char* file = "data.txt"; FILE* fout = fopen(file, "r"); if (fout == NULL)//打開(kāi)失敗 { perror("fopen fail!"); exit(1); } //創(chuàng)建一個(gè)大小為k的數(shù)組,建小堆，找前k個(gè)最大的數(shù)據(jù) int* minHeap = (int*)malloc(k*sizeof(int)); //往堆內(nèi)放數(shù)據(jù) if (minHeap == NULL) { perror("malloc fail!"); exit(2); } //循環(huán)讀取文件內(nèi)的數(shù)據(jù) //從文件中讀取前K個(gè)數(shù)據(jù)， for (int i = 0; i < k; i++) { //從fout進(jìn)行讀取，讀取的數(shù)據(jù)類(lèi)型是%d,將讀取到的數(shù)據(jù)往數(shù)組內(nèi)進(jìn)行存儲(chǔ) fscanf_s(fout, "%d", &minHeap[i]); } //向下調(diào)整算法，建小堆 //調(diào)整建堆//我們從最后一個(gè)數(shù)的父節(jié)點(diǎn)進(jìn)行調(diào)整，最后一個(gè)數(shù)的下標(biāo)是k-1 for (int i = (k - 1 - 1) / 2; i>= 0; i--) { AdhustDown(minHeap, i, k); //我們從最后一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)進(jìn)行向上調(diào)整操作 //一開(kāi)始我們的i就被定義成了這個(gè)父節(jié)點(diǎn)的下標(biāo)的大小 } //那么我們建好堆之后我們就接著讀取文件中剩下的N-K個(gè)數(shù)據(jù) //我們進(jìn)行循環(huán)讀取 int x = 0;//我們創(chuàng)建一個(gè)x變量，將每次讀取的數(shù)據(jù)存在x中與堆頂?shù)臄?shù)據(jù)進(jìn)行循環(huán)比較 while (fscanf(fout,"%d",&x)!=EOF)//直到讀到文件末尾 { //讀取到的數(shù)據(jù)與堆頂?shù)臄?shù)據(jù)進(jìn)行比較 //如果比對(duì)頂值大，交換入堆 if (x < minHeap[0]) { minHeap[0] = x;//直接將x放到堆頂 //經(jīng)過(guò)上面的操作之后，那么這個(gè)堆就不是一個(gè)小堆了 //我們利用向下調(diào)整算法重新將這個(gè)堆變成小堆 AdhustDown(minHeap, 0, k); } } //走到這里我們已經(jīng)讀完了,那么這個(gè)堆剩下的數(shù)據(jù)就是這個(gè)文件前K個(gè)最大的數(shù)據(jù)了 for (int i = 0; i < k; i++) { printf("%d ", minHeap[i]); } fclose(fout); } int main() { //test01(); //給定一個(gè)數(shù)組，對(duì)數(shù)組中的數(shù)據(jù)進(jìn)行排序 //int arr[] = { 17,20,10,13,19,15 }; BubbleSort(arr, 6);//冒泡排序 //HeapSort(arr, 6);//堆排序 //for (int i = 0; i < 6; i++) //{ // // printf("%d ",arr[i]); //} //printf("\n"); //CreateNDate();//創(chuàng)建一個(gè)有10w個(gè)數(shù)據(jù)的文件 TOPK(); return 0; } 4.實(shí)現(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)二叉樹(shù) 遍歷規(guī)則 按照規(guī)則，?叉樹(shù)的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷： 1）前序遍歷(Preorder Traversal 亦稱(chēng)先序遍歷)：訪(fǎng)問(wèn)根結(jié)點(diǎn)的操作發(fā)?在遍歷其左右?樹(shù)之前 訪(fǎng)問(wèn)順序?yàn)椋焊Y(jié)點(diǎn)、左?樹(shù)、右?樹(shù) 2）中序遍歷(Inorder Traversal)：訪(fǎng)問(wèn)根結(jié)點(diǎn)的操作發(fā)?在遍歷其左右?樹(shù)之中（間） 訪(fǎng)問(wèn)順序?yàn)椋鹤?樹(shù)、根結(jié)點(diǎn)、右?樹(shù) 3）后序遍歷(Postorder Traversal)：訪(fǎng)問(wèn)根結(jié)點(diǎn)的操作發(fā)?在遍歷其左右?樹(shù)之后 訪(fǎng)問(wèn)順序?yàn)椋鹤?樹(shù)、右?樹(shù)、根結(jié)點(diǎn) 遍歷規(guī)則解釋?zhuān)?/p> 前序遍歷： 一開(kāi)始遍歷的是1，那么我們遍歷完1之后，進(jìn)行1的打印，然后箭頭移動(dòng)，箭頭指向了2，打印了2 因?yàn)?是個(gè)頭節(jié)點(diǎn)，那么我們繼續(xù)往下遍歷，箭頭指向了4，那么打印了4，最后箭頭指向了3，打印了3，規(guī)則就是先根再左右 最后打印的就是1 2 4 3 中序遍歷: 我們遍歷的順序是左子樹(shù)、根節(jié)點(diǎn)、右子樹(shù) 那么我們先遍歷左子樹(shù)，那么箭頭指向了2，那么對(duì)于2來(lái)說(shuō)，4是左子樹(shù)，那么箭頭來(lái)到了4 那么我們將4打印，那么對(duì)于4的話(huà)，已經(jīng)沒(méi)有子節(jié)點(diǎn)了，那么箭頭就回到了2 我們打印根節(jié)點(diǎn)2，打印完這個(gè)根節(jié)點(diǎn)，我們的箭頭就應(yīng)該指向以2為頂點(diǎn)的樹(shù)的右子樹(shù) 但是2沒(méi)有右子樹(shù) 所以我們的箭頭回到了1，對(duì)于1這個(gè)根節(jié)點(diǎn)來(lái)說(shuō)，左子樹(shù)已經(jīng)打印完了，我們就該開(kāi)始打印根節(jié)點(diǎn)1了，打印完根節(jié)點(diǎn)之后我們就開(kāi)始打印右節(jié)點(diǎn)了，那么箭頭就指向了3了 那么最后打印的就是4 2 1 3 后序遍歷： 后續(xù)遍歷的順序是左子樹(shù)、右子樹(shù)、根節(jié)點(diǎn) 一開(kāi)始的箭頭指向1,2是1的左子樹(shù)，因?yàn)?是2的左子樹(shù)，那么箭頭就來(lái)到了4的位置，將4進(jìn)行打印 因?yàn)?沒(méi)有右子樹(shù)，那么我們的箭頭就直接跳到了2這個(gè)根節(jié)點(diǎn)的位置了，將2進(jìn)行打印 對(duì)于1這顆二叉樹(shù)來(lái)說(shuō)的話(huà)，我們的左子樹(shù)已經(jīng)全部打印完成了，那么就開(kāi)始右子樹(shù)的打印了，箭頭指向了3的位置，將3打印完成之后，我們的箭頭回到根節(jié)點(diǎn)1的位置，最后打印根節(jié)點(diǎn) 那么最后打印的就是4 2 3 1 對(duì)于這個(gè)二叉樹(shù)來(lái)說(shuō)的話(huà) 前序遍歷：1 2 4 6 5 3 中序遍歷：4 6 2 5 1 3 后續(xù)遍歷：6 4 5 2 3 1 解釋前序遍歷的代碼中的遞歸 ? 我們用這張圖進(jìn)行解釋 一開(kāi)始我們的的root節(jié)點(diǎn)是1，判斷節(jié)點(diǎn)不為空，那么我們就進(jìn)行條件語(yǔ)句下面的代碼 我們將root節(jié)點(diǎn)內(nèi)的數(shù)據(jù)打印，就是1 然后我們進(jìn)入到了root的左節(jié)點(diǎn)的遞歸里面了，root→left是2 當(dāng)2是root節(jié)點(diǎn)時(shí) 我們先判斷傳過(guò)來(lái)的root不是空節(jié)點(diǎn) 那么我們將2進(jìn)行打印，然后右進(jìn)入到2的子節(jié)點(diǎn)的遞歸中，子節(jié)點(diǎn)就是4 當(dāng)4是root節(jié)點(diǎn)時(shí) 我們先判斷傳過(guò)來(lái)的root是不是空的，然后我們進(jìn)行打印4 我們進(jìn)入到了root→left 發(fā)現(xiàn)4沒(méi)有左節(jié)點(diǎn)，那么傳的就是空值，我們直接退出 4同樣沒(méi)有右節(jié)點(diǎn)，我們依然退出 那么我們就原路返回了 對(duì)于root=2時(shí)，我們的左節(jié)點(diǎn)遞歸已經(jīng)結(jié)束了，那么我們進(jìn)行2的右節(jié)點(diǎn)遞歸，但是2的右節(jié)點(diǎn)是空的，所以我們直接退出 那么2這個(gè)樹(shù)我們已經(jīng)遞歸完成了 我們就回到了1是root了 對(duì)于1來(lái)說(shuō)，左節(jié)點(diǎn)已經(jīng)遞歸完了，那么就進(jìn)行右節(jié)點(diǎn)的遞歸了 就是3 當(dāng)3是root的時(shí)候，我們將3進(jìn)行打印，打印完進(jìn)入左遞歸，是空值，返回 然后進(jìn)入右遞歸，是空值，返回 那么最后我們打印的就是1 2 4 3 整個(gè)遞歸的流程圖如下： 第四種遍歷方法：層序遍歷\ 對(duì)于這么一個(gè)二叉樹(shù)來(lái)說(shuō)，我們通過(guò)層序遍歷最后得到的是1 2 3 4 這里我們是不能通過(guò)遞歸來(lái)實(shí)現(xiàn)的 但是我們可以借助隊(duì)列來(lái)實(shí)現(xiàn)這么一個(gè)結(jié)構(gòu) 隊(duì)列的結(jié)構(gòu)是先進(jìn)先出 恰好我們隊(duì)列的底層結(jié)構(gòu)就是鏈表來(lái)實(shí)現(xiàn)的，和這里的鏈?zhǔn)蕉鏄?shù)一樣的 我們將之前寫(xiě)的Queue.c文件和Queue.h文件復(fù)制到我們鏈?zhǔn)蕉鏄?shù)的文件夾里面 typedef struct BinaryTreeNode* QDataType; struct BinaryTreeNode*這個(gè)就是我們要保存在隊(duì)列中的數(shù)據(jù)類(lèi)型 之前的在隊(duì)列中保存的數(shù)據(jù)類(lèi)型是int類(lèi)型 隊(duì)列中存儲(chǔ)的是堆節(jié)點(diǎn)的地址 那么存儲(chǔ)的就是節(jié)點(diǎn)的指針，那么我們將這個(gè)類(lèi)型重新定義 //層序遍歷---借助數(shù)據(jù)結(jié)構(gòu)（隊(duì)列） void Levelorder(BTNode* root) { //創(chuàng)建一個(gè)隊(duì)列結(jié)構(gòu) Queue q; QueueInit(&q);//進(jìn)行初始化 //第一步：讓根節(jié)點(diǎn)直接入隊(duì)列 QueuePush(&q,root);//往隊(duì)列中push根節(jié)點(diǎn) while (!Queuempty(&q))//只要隊(duì)列不為空，我們就一直取隊(duì)頭數(shù)據(jù) { //取隊(duì)頭數(shù)據(jù) BTNode*front=QueueFront(&q);//將隊(duì)頭取出，返回值是節(jié)點(diǎn)的地址 //打印對(duì)頭 printf("%d ", front->data); //讓隊(duì)頭出隊(duì)列 QueuePop(&q);//那么此時(shí)的隊(duì)列是空的 //將隊(duì)頭節(jié)點(diǎn)的左右孩子入隊(duì)列 if (front->left)//如果這個(gè)節(jié)點(diǎn)的左孩子不是空的，那么我們將這個(gè)節(jié)點(diǎn)往隊(duì)列中入 { QueuePush(&q, front->left); } if (front->right)//如果這個(gè)節(jié)點(diǎn)的右孩子不是空的，那么我們將這個(gè)節(jié)點(diǎn)往隊(duì)列中入 { QueuePush(&q, front->right); } } QueueDestroy(&q);//銷(xiāo)毀 } 判斷是否為完全二叉樹(shù) 除了最后一層，其它層的節(jié)點(diǎn)數(shù)達(dá)到最大，那么這個(gè)數(shù)就是完全二叉樹(shù) 這里涉及到每層，那么這里還是要借助隊(duì)列這么一個(gè)結(jié)構(gòu)的 我們先取根節(jié)點(diǎn)放進(jìn)隊(duì)列，隊(duì)列不為空，我們將隊(duì)列中的節(jié)點(diǎn)取出來(lái) 然后將這個(gè)節(jié)點(diǎn)的左右孩子一起放進(jìn)隊(duì)列中去 我們?cè)賹㈥?duì)頭取出，將隊(duì)頭的左右孩子放進(jìn)去，如果孩子為空放個(gè)NULL進(jìn)去 如果我們隊(duì)列剩下的都是NULL的話(huà)，我們將隊(duì)列中第一個(gè)NULL取出 那么我們?nèi)〉降臄?shù)據(jù)為空，取到為空的情況我們就跳出循環(huán) 那么最后就是這么個(gè)情況 如果我們的二叉樹(shù)現(xiàn)在是非完全二叉樹(shù)是個(gè)什么情況呢？ 那么會(huì)有很明顯的不同的 如果是完全二叉樹(shù)，跳出第一個(gè)循環(huán)之后，隊(duì)列中全是NULL節(jié)點(diǎn) 如果不是完全二叉樹(shù)，跳出一個(gè)循環(huán)之后，那么隊(duì)列還有一個(gè)非空節(jié)點(diǎn) 如果是上面這張圖的話(huà)，4是2的右節(jié)點(diǎn)，那么這個(gè)數(shù)就不是一個(gè)完全二叉樹(shù)，因?yàn)闆](méi)有遵循從左到右的原則 但是如果4是2的左節(jié)點(diǎn)的話(huà)，那么這個(gè)數(shù)就是一個(gè)完全二叉樹(shù) 二叉樹(shù)鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn) 這里我們用到了隊(duì)列里面的相關(guān)知識(shí) test.c #define _CRT_SECURE_NO_WARNINGS 1 #include"tree.h" BTNode* buyNode(BTDataType x)//創(chuàng)建一個(gè)節(jié)點(diǎn) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->left = newnode->right = NULL; return newnode; } void test01() { 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 = node3; node2->left = node4; /*node2->right = node5; node3->left = node6;*/ 前序遍歷 //PreOrder(node1);// 1 2 4 3 //printf("\n"); 中序遍歷 //InOrder(node1);// 4 2 1 3 二叉樹(shù)節(jié)點(diǎn)的個(gè)數(shù) //printf("size:%d\n", BinaryTreeSize(node1));//4 printf("size:%d\n", BinaryTreeSize(node2));//2 二叉樹(shù)葉子結(jié)點(diǎn)的個(gè)數(shù) //printf("leaf size:%d\n", BinaryTreeLeafSize(node1)); 第k層節(jié)點(diǎn)的個(gè)數(shù) //printf("k size:%d\n", BinaryTreeLevelKSize(node1, 3)); 二叉樹(shù)的高度 //printf("depth/height :%d\n", BinaryTreeDepth(node1)); 查找值為x的節(jié)點(diǎn) //BTNode*find=BinaryTreeFind(node1, 5); //printf("%s\n", find == NULL ? "沒(méi)找到":"找到了"); //層序遍歷 /*Levelorder(node1);*/ //判斷是否為完全二叉樹(shù) bool ret=BinaryTreeComplete(node1); printf("%s\n", ret == false ?"不是完全二叉樹(shù)" : "是完全二叉樹(shù)"); //二叉樹(shù)的銷(xiāo)毀 BinaryTreeDestory(&node1); } int main( ) { test01(); return 0; } tree.c #define _CRT_SECURE_NO_WARNINGS 1 #include"tree.h" #include"Queue.h" //前序遍歷 根左右 void PreOrder(BTNode* root)//我們傳個(gè)根節(jié)點(diǎn)就行了，我們是從根節(jié)點(diǎn)開(kāi)始遍歷的 { if (root == NULL) { return; } printf("%d ", root->data); PreOrder(root->left);//遍歷左子樹(shù) PreOrder(root->right);//遍歷右子樹(shù) } //中序遍歷 左根右 void InOrder(BTNode* root) { if (root == NULL) { return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); } //后序遍歷 左右根 void PostOrder(BTNode* root) { if (root == NULL) { return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); } // ?叉樹(shù)結(jié)點(diǎn)個(gè)數(shù) //第一種方法（不可行） //int size = 0; //void BinaryTreeSize(BTNode* root) //{ // if (root == NULL) // { // return 0; // } // //說(shuō)明當(dāng)前節(jié)點(diǎn)不為空 // size++; // //遍歷整個(gè)二叉樹(shù)的 左右節(jié)點(diǎn) // BinaryTreeSize(root->left); // BinaryTreeSize(root->right); // return size; // //} // 第二種方法（不可行，有弊端，每次調(diào)用函數(shù)要提前將size置為0） //void BinaryTreeSize(BTNode* root,int *psize) //{ // if (root == NULL) // { // return 0; // } // //說(shuō)明當(dāng)前節(jié)點(diǎn)不為空 // (*psize)++; // //遍歷整個(gè)二叉樹(shù)的 左右節(jié)點(diǎn) // BinaryTreeSize(root->left,psize); // BinaryTreeSize(root->right,psize); // // //不是空節(jié)點(diǎn)點(diǎn)我們就進(jìn)行計(jì)數(shù) // // /* // * 我們的想法（錯(cuò)的） // 如果我們?cè)诤瘮?shù)內(nèi)設(shè)置size的話(huà)，我們?cè)谶M(jìn)行完1 2 4 3 這個(gè)堆的時(shí)候 // 我們遞歸完左子樹(shù)，size++已將isze變?yōu)?了 // // 上面這種想法就是錯(cuò)的 // 但是當(dāng)我們開(kāi)始遞歸1的右子樹(shù)的時(shí)候，我們傳的size仍然是1， // // 解釋為什么： // 因?yàn)槲覀儌鞯膚size是值，不是地址 // 遞歸函數(shù)內(nèi)的size++并不能將size的大小直接改變 // 所以我們?cè)谟易訕?shù)的遞歸的時(shí)候我們的size就是1 // // 因?yàn)槲覀冊(cè)诿總€(gè)遞歸中的size都是傳的值，所以我們不能將size進(jìn)行改變 // */ // /* // ，假設(shè)我們每次傳的是值的話(huà)，我們將這塊地址取出來(lái)，這塊地址里面存的就是size，我們進(jìn)行++ // 不管是在左子樹(shù)還是右子樹(shù)的遞歸中，我們每次調(diào)用的時(shí)候，都要先取這個(gè)地址里面的數(shù)據(jù) // 這個(gè)數(shù)據(jù)是可以進(jìn)行改變的 // // 此次遞歸的psize地址指向的size的大小就是上次遞歸的size加加后的大小 // */ // //但是這種方法有個(gè)弊端，每次我們?cè)谡{(diào)用求節(jié)點(diǎn)個(gè)數(shù)的這個(gè)函數(shù)的時(shí)候 // //我們都要將size重新置為0 //} // 二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù) //第三種方法： int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right); } /* 堆：1 2 4 3 4的左子樹(shù)和右子樹(shù)都是0，那么我們就return 1 + 0+ 0 回到2，因?yàn)?的左節(jié)點(diǎn)4返回的指是1，但是沒(méi)有右節(jié)點(diǎn)，所以右節(jié)點(diǎn)返回的是0 那么對(duì)于2的話(huà)，return 1+ 1 +0 對(duì)于1的話(huà)，左節(jié)點(diǎn)2的返回值是2,1的右節(jié)點(diǎn)3的返回值因?yàn)闆](méi)有左右子節(jié)點(diǎn) 所以3的返回值是1 那么1的返回值就是1+2+1=4 那么這個(gè)4就是我們這個(gè)堆的節(jié)點(diǎn)數(shù) */ // ?叉樹(shù)葉?結(jié)點(diǎn)個(gè)數(shù) //所謂的葉子節(jié)點(diǎn)就是沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn) int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL)//說(shuō)明這個(gè)節(jié)點(diǎn)就是葉子節(jié)點(diǎn)，沒(méi)有子節(jié)點(diǎn) { return 1; } //進(jìn)行遞歸 return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); //直接將左子樹(shù)的葉子結(jié)點(diǎn)的個(gè)數(shù)和右子樹(shù)葉子節(jié)點(diǎn)的個(gè)數(shù)進(jìn)行返回 } // ?叉樹(shù)第k層結(jié)點(diǎn)個(gè)數(shù) //左子樹(shù)第k層節(jié)點(diǎn)的個(gè)數(shù)+右子樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù) int BinaryTreeLevelKSize(BTNode* root, int k) { //遞歸一定要有結(jié)束條件 if (root == NULL) { return 0; } //判斷是不是第k層 if (k == 1)//就是第k層 { return 1; } return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); } //這里我們采用的是傳值操作，左右子樹(shù)的操作不會(huì)因?yàn)閗受到影響 //?叉樹(shù)的深度/?度 int BinaryTreeDepth(BTNode* root) { if (root == NULL) { return 0; } //當(dāng)前節(jié)點(diǎn)不為空，那么我們對(duì)左子樹(shù)和右子樹(shù)進(jìn)行遍歷 int leftDep=BinaryTreeDepth(root->left); int rightDep = BinaryTreeDepth(root->right); return leftDep > rightDep ? leftDep + 1 : rightDep + 1; //因?yàn)槭莻€(gè)遞歸代碼，我們從左后一個(gè)節(jié)點(diǎn)進(jìn)行思考 /* 1 2 4 3 對(duì)于左子樹(shù)的話(huà)，4是最后一個(gè)節(jié)點(diǎn) 那么我們從4開(kāi)始 因?yàn)樽笥夜?jié)點(diǎn)都是空的，那么左節(jié)點(diǎn)和右節(jié)點(diǎn)的大小都是0 那么在返回的時(shí)候?qū)τ?的話(huà)，4這個(gè)節(jié)點(diǎn)返回了1 所以2的左節(jié)點(diǎn)返回值是1，因?yàn)橛夜?jié)點(diǎn)是空，返回0 那么對(duì)于1的話(huà)，2這個(gè)節(jié)點(diǎn)的返回值是1+1 對(duì)于1的話(huà)，左節(jié)點(diǎn)返回值是2，右節(jié)點(diǎn)是3 因?yàn)?這個(gè)節(jié)點(diǎn)的左右節(jié)點(diǎn)都是空，那么就返回1 那么因?yàn)樽蠊?jié)點(diǎn)返回的是2 右節(jié)點(diǎn)返回的是1 2>1 所以對(duì)于節(jié)點(diǎn)1的話(huà)，返回的值是1+2=3 那么最終的話(huà)我們的層數(shù)是3層 */ } // ?叉樹(shù)查找值為x的結(jié)點(diǎn) //找到對(duì)應(yīng)節(jié)點(diǎn)就返回這個(gè)節(jié)點(diǎn)，沒(méi)有找到就返回空 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { //要么出現(xiàn)在左子樹(shù)，要么出現(xiàn)在右子樹(shù) if (root == NULL) { return 0; } if (root->data == x) { return root; } //走到這這里說(shuō)明，root不為空，值不為x,那么我們繼續(xù)進(jìn)行遞歸 BTNode* leftFind=BinaryTreeFind(root->left, x); if (leftFind)//在左子樹(shù)中找到了這個(gè)節(jié)點(diǎn),我們就直接返回，就不用在右子樹(shù)中進(jìn)行尋找了 { return leftFind; } BTNode* rightFind = BinaryTreeFind(root->right, x); if (rightFind)//在左子樹(shù)中找到了這個(gè)節(jié)點(diǎn) { return rightFind; } //左子樹(shù)和右子樹(shù)都沒(méi)找到，那么我們直接返回NULL return NULL; } // ?叉樹(shù)銷(xiāo)毀 void BinaryTreeDestory(BTNode** root)//傳來(lái)的是root的地址，我們用二級(jí)指針進(jìn)行接收 { //銷(xiāo)毀一個(gè)堆的話(huà)，我們要先將左子樹(shù)和右子樹(shù)先銷(xiāo)毀，最后再將根進(jìn)行銷(xiāo)毀 if (*root == NULL)//已經(jīng)是空的，就沒(méi)必要進(jìn)行銷(xiāo)毀了 { return; } BinaryTreeDestory(&((*root)->left));//對(duì)*root進(jìn)行解引用我們才能找到left,這里的root是二級(jí)指針 //*root指向第一個(gè)節(jié)點(diǎn)的指針，再取成員left,然后對(duì)整體取地址 //上面的是左子樹(shù) BinaryTreeDestory(&((*root)->right));///右子樹(shù) //銷(xiāo)毀根節(jié)點(diǎn) free(*root); *root = NULL; /* 堆：1 2 4 3 當(dāng)節(jié)點(diǎn)在4的時(shí)候，我們對(duì)4的左節(jié)點(diǎn)和右節(jié)點(diǎn)都進(jìn)行遞歸了 因?yàn)槎际强盏?，我們返回到?這個(gè)節(jié)點(diǎn)，然后將4這個(gè)節(jié)點(diǎn)銷(xiāo)毀了 銷(xiāo)毀完就回到了2這個(gè)節(jié)點(diǎn)，因?yàn)?的左節(jié)點(diǎn)已經(jīng)銷(xiāo)毀了 那么就進(jìn)行2的右節(jié)點(diǎn)的銷(xiāo)毀了，右節(jié)點(diǎn)是空的，所以返回的是空 那么我們就將2銷(xiāo)毀了 2銷(xiāo)毀完就回到1這個(gè)節(jié)點(diǎn)了 對(duì)于1這個(gè)節(jié)點(diǎn)來(lái)說(shuō)的話(huà)，左節(jié)點(diǎn)2已經(jīng)銷(xiāo)毀完了 那么我們的頭結(jié)點(diǎn)就跑到了1的右節(jié)點(diǎn)3那里了 對(duì)于3這個(gè)頭結(jié)點(diǎn)來(lái)說(shuō)，左右節(jié)點(diǎn)都是空的，那么就直接返回，那么就進(jìn)行3這個(gè)節(jié)點(diǎn)的銷(xiāo)毀了 那么對(duì)于1的話(huà)，左右節(jié)點(diǎn)都銷(xiāo)毀了 那么就將銷(xiāo)毀1了 */ } //層序遍歷---借助數(shù)據(jù)結(jié)構(gòu)（隊(duì)列） void Levelorder(BTNode* root) { //創(chuàng)建一個(gè)隊(duì)列結(jié)構(gòu) Queue q; QueueInit(&q);//進(jìn)行初始化 //第一步：讓根節(jié)點(diǎn)直接入隊(duì)列 QueuePush(&q,root);//往隊(duì)列中push根節(jié)點(diǎn) while (!Queuempty(&q))//只要隊(duì)列不為空，我們就一直取隊(duì)頭數(shù)據(jù) { //取隊(duì)頭數(shù)據(jù) BTNode*front=QueueFront(&q);//將隊(duì)頭取出，返回值是節(jié)點(diǎn)的地址 //打印對(duì)頭 printf("%d ", front->data); //讓隊(duì)頭出隊(duì)列 QueuePop(&q);//那么此時(shí)的隊(duì)列是空的 //將隊(duì)頭節(jié)點(diǎn)的左右孩子入隊(duì)列 if (front->left)//如果這個(gè)節(jié)點(diǎn)的左孩子不是空的，那么我們將這個(gè)節(jié)點(diǎn)往隊(duì)列中入 QueuePush(&q, front->left); { } if (front->right)//如果這個(gè)節(jié)點(diǎn)的右孩子不是空的，那么我們將這個(gè)節(jié)點(diǎn)往隊(duì)列中入 { QueuePush(&q, front->right); } } QueueDestroy(&q);//銷(xiāo)毀 } //判斷二叉樹(shù)是否為完全二叉樹(shù) //借助隊(duì)列 bool BinaryTreeComplete(BTNode* root) { Queue q; QueueInit(&q);//進(jìn)行初始化 //將二叉樹(shù)根節(jié)點(diǎn)入隊(duì)列 QueuePush(&q, root);//往隊(duì)列中push根節(jié)點(diǎn) while (!Queuempty(&q))//隊(duì)列不為空，我們就循環(huán)取隊(duì)頭 { BTNode* front = QueueFront(&q);//將隊(duì)頭取出 QueuePop(&q);//讓隊(duì)頭出隊(duì)，保證下次取到的是最新的隊(duì)頭數(shù)據(jù) //如果我們?nèi)〉降膄ront是空的話(huà) if (front == NULL)//如果此時(shí)的隊(duì)頭是空的，那么我們就取不到左右孩子 { break; } //將隊(duì)頭的左右孩子取出放到隊(duì)列中 QueuePush(&q, front->left); QueuePush(&q, front->right); } //此時(shí)隊(duì)列不一定為空 while (!Queuempty(&q))//只要隊(duì)列不為空 { BTNode* front = QueueFront(&q);//取隊(duì)頭 QueuePop(&q);//出隊(duì)列 //如果我們?cè)陉?duì)列中剩下的節(jié)點(diǎn)中遇到了節(jié)點(diǎn)的話(huà)，那么這個(gè)樹(shù)就不是一個(gè)完全二叉樹(shù)了 if (front != NULL) { QueueDestroy(&q);//銷(xiāo)毀 return false; } } QueueDestroy(&q);//銷(xiāo)毀 //到這里就說(shuō)明沒(méi)有找到完全二叉樹(shù) return true; } /* 如果是完全二叉樹(shù)，跳出第一個(gè)循環(huán)之后，隊(duì)列中全是NULL節(jié)點(diǎn) 如果不是完全二叉樹(shù)，跳出一個(gè)循環(huán)之后，那么隊(duì)列還有一個(gè)非空節(jié)點(diǎn) */ tree.h #pragma once #include #include #include #include //定義二叉樹(shù)的鏈?zhǔn)浇Y(jié)構(gòu) //二叉樹(shù)節(jié)點(diǎn)的結(jié)構(gòu) typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left;//指向左孩子節(jié)點(diǎn)的指針 struct BinaryTreeNode* right;//指向右孩子節(jié)點(diǎn)的指針 }BTNode; //前序遍歷 void PreOrder(BTNode*root);//我們傳個(gè)根節(jié)點(diǎn)就行了，我們是從根節(jié)點(diǎn)開(kāi)始遍歷的 //中序遍歷 void InOrder(BTNode* root); //后序遍歷 void PostOrder(BTNode* root); // ?叉樹(shù)結(jié)點(diǎn)個(gè)數(shù) int BinaryTreeSize(BTNode* root); // ?叉樹(shù)結(jié)點(diǎn)個(gè)數(shù) //void BinaryTreeSize(BTNode* root, int* psize); // ?叉樹(shù)葉?結(jié)點(diǎn)個(gè)數(shù) int BinaryTreeLeafSize(BTNode* root); // ?叉樹(shù)第k層結(jié)點(diǎn)個(gè)數(shù) int BinaryTreeLevelKSize(BTNode* root, int k); //?叉樹(shù)的深度/?度 int BinaryTreeDepth(BTNode* root); // ?叉樹(shù)查找值為x的結(jié)點(diǎn) BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // ?叉樹(shù)銷(xiāo)毀 void BinaryTreeDestory(BTNode** root); //層序遍歷 void Levelorder(BTNode* root); //判斷二叉樹(shù)是否為完全二叉樹(shù) bool BinaryTreeComplete(BTNode* root); Queue.c #define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" //初始化 void QueueInit(Queue* pq) { assert(pq);//傳過(guò)來(lái)的不能是空指針 pq->phead = pq->ptail = NULL;//空的隊(duì)列 pq->size = 0; } //判斷隊(duì)列是否為空 bool Queuempty(Queue* pq) { assert(pq); return pq->phead == NULL && pq->ptail == NULL; //如果后面的表達(dá)式成立，那么就是真，返回的是true //就是說(shuō)如果這里的是空隊(duì)列的話(huà)，那么就返回的是true } //入隊(duì)列，隊(duì)尾 插入數(shù)據(jù) void QueuePush(Queue* pq, QDataType x) { assert(pq); //申請(qǐng)新節(jié)點(diǎn) QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//申請(qǐng)一個(gè)節(jié)點(diǎn)大小的空間 if (newnode == NULL) { perror("malloc dail!"); exit(1); } //對(duì)newnode進(jìn)行初始化操作 newnode->data = x; newnode->next = NULL; if (pq->phead == NULL)//說(shuō)明隊(duì)列為空 { pq->phead = pq->ptail = newnode;//那么此時(shí)的newnode不僅是頭結(jié)點(diǎn)也是尾節(jié)點(diǎn) } else//隊(duì)列不為空 { pq->ptail->next = newnode; //那么此時(shí)的newnode 就是新的ptail pq->ptail = newnode; } pq->size++; } //出隊(duì)列,隊(duì)頭 刪除數(shù)據(jù) 從頭結(jié)點(diǎn)開(kāi)始刪除數(shù)據(jù) void QueuePop(Queue* pq) { assert(pq); //隊(duì)列為空（不可刪除數(shù)據(jù)，因?yàn)闆](méi)有數(shù)據(jù)） //隊(duì)列不為空（可刪除數(shù)據(jù)） assert(!Queuempty(pq));//隊(duì)列為空白的話(huà)就報(bào)錯(cuò) //處理只有一個(gè)節(jié)點(diǎn)的情況，避免ptail變成野指針 //判斷只有一個(gè)節(jié)點(diǎn)的情況 if (pq->ptail == pq->phead)//頭尾指針相同，說(shuō)明只有一個(gè)節(jié)點(diǎn) { free(pq->phead);//隨便釋放 pq->phead = pq->ptail = NULL; } else//處理多個(gè)節(jié)點(diǎn)的情況 { //刪除隊(duì)頭元素 //那么我們現(xiàn)將下個(gè)節(jié)點(diǎn)的位置進(jìn)行保存 QueueNode* next = pq->phead->next; //存儲(chǔ)好之后我們直接將頭結(jié)點(diǎn)進(jìn)行釋放 free(pq->phead); pq->phead = next;//那么之前存的next就是新的頭結(jié)點(diǎn)了 } pq->size--; } //取隊(duì)頭數(shù)據(jù) QDataType QueueFront(Queue* pq)//返回隊(duì)頭數(shù)據(jù) { assert(pq); assert(!Queuempty(pq));//隊(duì)列不為空 return pq->phead->data;//將隊(duì)頭里面的數(shù)據(jù)直接返回就行了 } //取隊(duì)尾數(shù)據(jù) QDataType QueueBack(Queue* pq) { assert(pq); assert(!Queuempty(pq));//隊(duì)列不為空 return pq->ptail->data; } //隊(duì)列有效元素個(gè)數(shù) int QueueSize(Queue* pq) { assert(pq); //下面這種遍歷的話(huà)效率太低了 //int size = 0; 定義一個(gè)指針進(jìn)行遍歷 //QueueNode* pcur = pq->phead;//指向隊(duì)列的頭結(jié)點(diǎn) //while (pcur)//pcur不為空就往后走 //{ // size++; // pcur = pcur->next; //} //return size; return pq->size; } //隊(duì)列的銷(xiāo)毀 void QueueDestroy(Queue* pq) { assert(pq); //assert(!Queuempty(pq));//隊(duì)列不為空 //遍歷 QueueNode* pcur = pq->phead; while (pcur) { //銷(xiāo)毀之前先把下個(gè)節(jié)點(diǎn)進(jìn)行保存 QueueNode* next = pcur -> next; free(pcur); //將Pcur銷(xiāo)毀之后，那么之前保存的next就是新的頭結(jié)點(diǎn) pcur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } Queue.h #pragma once #include #include #include #include //定義隊(duì)列結(jié)構(gòu) //typedef int QDataType; typedef struct BinaryTreeNode* QDataType; //struct BinaryTreeNode*這個(gè)就是我們要保存在隊(duì)列中的數(shù)據(jù)類(lèi)型 //struct BinaryTreeNode*這個(gè)是個(gè)數(shù)據(jù)類(lèi)型，和之前的 //之前的在隊(duì)列中保存的數(shù)據(jù)類(lèi)型是int類(lèi)型 //因?yàn)槲覀冊(cè)趖ree.h中將結(jié)構(gòu)體類(lèi)型重命名了 //那么我們可以這么寫(xiě) //typedef struct BTNode* QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QueueNode; typedef struct Queue { QueueNode*phead;//指向頭節(jié)點(diǎn)的指針---隊(duì)頭--刪除數(shù)據(jù) QueueNode*ptail;//指向尾節(jié)點(diǎn)的指針---隊(duì)尾--插入數(shù)據(jù) int size;//保存隊(duì)列有效個(gè)數(shù) }Queue ; //初始化 void QueueInit(Queue* pq); //入隊(duì)列，隊(duì)尾 插入數(shù)據(jù) void QueuePush(Queue* pq, QDataType x); //出隊(duì)列,隊(duì)頭 刪除數(shù)據(jù) void QueuePop(Queue* pq); //判斷隊(duì)列是否為空 bool Queuempty(Queue* pq); //取隊(duì)頭數(shù)據(jù) QDataType QueueFront(Queue* pq); //取隊(duì)尾數(shù)據(jù) QDataType QueueBack(Queue* pq); //隊(duì)列有效元素個(gè)數(shù) int QueueSize(Queue* pq); //隊(duì)列的銷(xiāo)毀 void QueueDestroy(Queue* pq); 5.二叉樹(shù)算法題 1.單值二叉樹(shù) /** * Definition for a binary tree node.定義好的二叉樹(shù)節(jié) * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /*思路： 遞歸 我們用根節(jié)點(diǎn)先與左節(jié)點(diǎn)進(jìn)行比較，如果相同的話(huà) 我們進(jìn)行根節(jié)點(diǎn)和有幾點(diǎn)的比較 如果不行同的話(huà)，就return false 如果相同的話(huà)，我們就遞歸下去 */ //遞歸是要存在結(jié)束條件的 typedef struct TreeNode TreeNode; bool isUnivalTree(struct TreeNode* root) { //遞歸是要存在結(jié)束條件的 if(root==NULL) { return true; } //說(shuō)明此時(shí)root不為空，那么我們進(jìn)行左孩子和右孩子的比較 if(root->left&&root->left->val!=root->val) { //如果左孩子存在并且左孩子里面的值與根節(jié)點(diǎn)的值不等 return false; } //走到這里說(shuō)明根節(jié)點(diǎn)的值和左孩子的值是相同的 if(root->right&&root->right->val!=root->val) { //如果右孩子存在并且左孩子里面的值與根節(jié)點(diǎn)的值不等 return false; } //走到這里說(shuō)明根節(jié)點(diǎn)的值和左右孩子節(jié)點(diǎn)的值相同 //那么我們接著遞歸這整個(gè)二叉樹(shù)的左子樹(shù)和右子樹(shù) //左子樹(shù)和右子樹(shù)都滿(mǎn)足條件的話(huà)那么這個(gè)樹(shù)就是單值二叉樹(shù)了 return isUnivalTree(root->left)&&isUnivalTree(root->right); } ? 2.相同的樹(shù) /** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ //不僅要判斷節(jié)點(diǎn)值相不相等，而且還要判斷兩個(gè)二叉樹(shù)的結(jié)構(gòu)是不是一樣的 //這里我們不需要借助數(shù)組，也不需要借助數(shù)列 //我們采用遞歸的方式 //兩棵樹(shù)都為空樹(shù)的話(huà)，那么我們返回true //如果其中一個(gè)樹(shù)為空樹(shù)的話(huà)，那么就不相同 //想要判斷兩個(gè)二叉樹(shù)是不是相同的樹(shù)，那么我們就要進(jìn)行同步遞歸 typedef struct TreeNode TreeNode; bool isSameTree(struct TreeNode* p, struct TreeNode* q) //參數(shù)是指向兩個(gè)二叉樹(shù)根節(jié)點(diǎn)的指針 { //判斷是否為空樹(shù) if(p==NULL&&q==NULL) { return true;//兩個(gè)樹(shù)都是空的，那么我們直接返回true } //或者其中一個(gè)為空 if(p==NULL||q==NULL) { return false; } //走到這里就說(shuō)明都不為空,就說(shuō)明整體結(jié)構(gòu)是相同的，那么我們下面就對(duì)節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行判斷是否相同 if(p->val!=q->val) { return false; } //走到這里說(shuō)明兩個(gè)二叉樹(shù)結(jié)構(gòu)相同，值也相同 //那么我們就遞歸這兩個(gè)二叉樹(shù)的左子樹(shù)和右子樹(shù) return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right); //只要前面的左子樹(shù)返回的是true，那么我們才能進(jìn)行后面的右子樹(shù)的判斷 } 我們先判斷兩個(gè)數(shù)的結(jié)構(gòu)是否相同 再判斷節(jié)點(diǎn)的值是否相同 3.對(duì)稱(chēng)二叉樹(shù) /** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSameTree(struct TreeNode* p, struct TreeNode* q) //參數(shù)是指向兩個(gè)二叉樹(shù)根節(jié)點(diǎn)的指針 { //判斷是否為空樹(shù) if(p==NULL&&q==NULL) { return true;//兩個(gè)樹(shù)都是空的，那么我們直接返回true } //或者其中一個(gè)為空 if(p==NULL||q==NULL) { return false; } //走到這里就說(shuō)明都不為空,就說(shuō)明整體結(jié)構(gòu)是相同的，那么我們下面就對(duì)節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行判斷是否相同 if(p->val!=q->val) { return false; } //走到這里說(shuō)明兩個(gè)二叉樹(shù)結(jié)構(gòu)相同，值也相同 //那么我們就遞歸這兩個(gè)二叉樹(shù)的左子樹(shù)和右子樹(shù) return isSameTree(p->left,q->right)&&isSameTree(p->right,q->left); //只要前面的左子樹(shù)返回的是true，那么我們才能進(jìn)行后面的右子樹(shù)的判斷 } bool isSymmetric(struct TreeNode* root) { //將這個(gè)二叉樹(shù)看成是兩棵樹(shù) return isSameTree(root->left,root->right); } 我們將這么一棵二叉樹(shù)看成是兩個(gè)數(shù)，左子樹(shù)和右子樹(shù) 我們先調(diào)用上面相同樹(shù)的代碼 判斷這兩個(gè)數(shù)是否為空 然后因?yàn)槭菍?duì)稱(chēng)的，所以我們判斷左子樹(shù)的左節(jié)點(diǎn)和右子樹(shù)的右節(jié)點(diǎn) 以及右子樹(shù)的左節(jié)點(diǎn)和左子樹(shù)的右節(jié)點(diǎn)是否相等 滿(mǎn)足了這么幾個(gè)條件那么這個(gè)二叉樹(shù)就是對(duì)稱(chēng)二叉樹(shù)了 ? 4.另一棵樹(shù)的子樹(shù) ? /** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ typedef struct TreeNode TreeNode; bool isSameTree(struct TreeNode* p, struct TreeNode* q) //參數(shù)是指向兩個(gè)二叉樹(shù)根節(jié)點(diǎn)的指針 { //判斷是否為空樹(shù) if(p==NULL&&q==NULL) { return true;//兩個(gè)樹(shù)都是空的，那么我們直接返回true } //或者其中一個(gè)為空 if(p==NULL||q==NULL) { return false; } //走到這里就說(shuō)明都不為空,就說(shuō)明整體結(jié)構(gòu)是相同的，那么我們下面就對(duì)節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行判斷是否相同 if(p->val!=q->val) { return false; } //走到這里說(shuō)明兩個(gè)二叉樹(shù)結(jié)構(gòu)相同，值也相同 //那么我們就遞歸這兩個(gè)二叉樹(shù)的左子樹(shù)和右子樹(shù) return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right); //只要前面的左子樹(shù)返回的是true，那么我們才能進(jìn)行后面的右子樹(shù)的判斷 } bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { if(root==NULL)//如果root是空樹(shù)的話(huà)，那么我們就沒(méi)必要進(jìn)行比較了 { return false; } if(isSameTree(root,subRoot))//判斷這兩個(gè)樹(shù)是不是相同的，根據(jù)一開(kāi)始的根節(jié)點(diǎn)進(jìn)行判斷 { return true; } //走到這里說(shuō)明root和subRoot不是相同的樹(shù) //那么我們還要遞歸root的左子樹(shù)是不是和subRoot相等的 //如果不相等的話(huà)，我們還要遞歸root的右子樹(shù) return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot); //我們這里用的是或，因?yàn)榧偃绲脑?huà)我們遞歸左子樹(shù)的時(shí)候就判斷出相等，那么就沒(méi)必要遞歸右子樹(shù)了 //但是左子樹(shù)不相等的話(huà)，那么我們就進(jìn)行右子樹(shù)的遞歸 } /* 我們先判斷的是根節(jié)點(diǎn)和subRoot是否相等 不相等的話(huà)我們進(jìn)行根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)與subRoot是否相等的判斷 */ 5.二叉樹(shù)的前序遍歷 ? ? ? /** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ //返回的是整型數(shù)組，數(shù)組必須是動(dòng)態(tài)開(kāi)辟的 /* 求二叉樹(shù)節(jié)點(diǎn)的個(gè)數(shù)就是這個(gè)二叉樹(shù)左子樹(shù)節(jié)點(diǎn)和右子樹(shù)節(jié)點(diǎn)的個(gè)數(shù)的總和*/ typedef struct TreeNode TreeNode; int TreeSize(TreeNode* root) { if(root==NULL) { return 0; } return 1+TreeSize(root->left)+TreeSize(root->right); //左子樹(shù)節(jié)點(diǎn)的個(gè)數(shù)和右子樹(shù)節(jié)點(diǎn)的個(gè)數(shù) } void _preorderTraversal(TreeNode* root,int *arr,int* pi)//進(jìn)行遞歸的函數(shù)//第一個(gè)參數(shù)是根節(jié)點(diǎn)，第二個(gè)參數(shù)是存儲(chǔ)的數(shù)組，將結(jié)果存儲(chǔ)在數(shù)組中 { if(root==NULL)//如果節(jié)點(diǎn)為空的話(huà)，那么我們就不需要保存當(dāng)前節(jié)點(diǎn)的值 { return; } //走到這里說(shuō)明當(dāng)前節(jié)點(diǎn)不為空，那么我們將當(dāng)前節(jié)點(diǎn)的值保存在數(shù)組中 //題目中說(shuō)的是前序遍歷，那么就是根左右 arr[(*pi)++]=root->val; _preorderTraversal(root->left,arr,pi); _preorderTraversal(root->right,arr,pi); } int* preorderTraversal(struct TreeNode* root, int* returnSize) { //第一步：先求出二叉樹(shù)節(jié)點(diǎn)的個(gè)數(shù) //將節(jié)點(diǎn)個(gè)數(shù)放到* returnSize里面 * returnSize=TreeSize(root); //第二步：動(dòng)態(tài)申請(qǐng)內(nèi)存--arr的大小 //這個(gè)數(shù)組存放二叉樹(shù)內(nèi)節(jié)點(diǎn)的值 int*returnArr=(int*)malloc(sizeof(int)*(* returnSize)); int i=0; _preorderTraversal(root,returnArr,&i); return returnArr; } /* 我們需要先知道二叉樹(shù)節(jié)點(diǎn)的個(gè)數(shù) 知道節(jié)點(diǎn)個(gè)數(shù)之后我們進(jìn)行數(shù)組的動(dòng)態(tài)內(nèi)存的開(kāi)辟 然后我們又創(chuàng)建了一個(gè)函數(shù)專(zhuān)門(mén)進(jìn)行遞歸，將節(jié)點(diǎn)中的數(shù)據(jù)存儲(chǔ)在數(shù)組中 在這個(gè)函數(shù)中，我們傳過(guò)去的有根節(jié)點(diǎn)，數(shù)組，還有i的地址 在函數(shù)內(nèi)，如果節(jié)點(diǎn)為空的話(huà)，那么我們直接返回 然后我們進(jìn)行數(shù)組內(nèi)元素的賦值 我們利用傳的指針作為下標(biāo) 為什么i要傳地址呢？ 因?yàn)槲覀兊膇作為下標(biāo)要一直進(jìn)行++ 如果不傳地址的話(huà)，傳值的話(huà)，那么對(duì)于這個(gè)函數(shù)內(nèi)的兩個(gè)遞歸 進(jìn)行完左遞歸之后我們的i是不會(huì)有變化的 所以我們要進(jìn)行傳地址操作 我們將節(jié)點(diǎn)數(shù)值依次放到數(shù)組中,*pi一直在++操作，下標(biāo)一直在變化 我們先遍歷左子樹(shù)的值，再遍歷右子樹(shù)的值，那么i就要一直進(jìn)行變化； 最后我們還要返回?cái)?shù)組的地址 */ 6.二叉樹(shù)的中序遍歷 typedef struct TreeNode TreeNode; int TreeSize(TreeNode* root) { if (root == NULL) { return 0; } return 1 + TreeSize(root->left) + TreeSize(root->right); } void _inorderTraversal(TreeNode* root, int *arr, int* pi) { if (root == NULL) { return; } _inorderTraversal(root->left, arr, pi); // 先遍歷左子樹(shù) arr[(*pi)++] = root->val; // 訪(fǎng)問(wèn)根節(jié)點(diǎn) _inorderTraversal(root->right, arr, pi); // 再遍歷右子樹(shù) } int* inorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize = TreeSize(root);//求節(jié)點(diǎn)個(gè)數(shù) int* returnArr = (int*)malloc(sizeof(int) * (*returnSize));//開(kāi)辟空間 int i = 0; _inorderTraversal(root, returnArr, &i);//遞歸函數(shù) return returnArr;//返回存儲(chǔ)數(shù)據(jù)的數(shù)組的指針 } 7.二叉樹(shù)的后續(xù)遍歷 typedef struct TreeNode TreeNode; int TreeSize(TreeNode* root) { if (root == NULL) { return 0; } return 1 + TreeSize(root->left) + TreeSize(root->right); } void _inorderTraversal(TreeNode* root, int *arr, int* pi) { if (root == NULL) { return; } _inorderTraversal(root->left, arr, pi); // 先遍歷左子樹(shù) _inorderTraversal(root->right, arr, pi); // 再遍歷右子樹(shù) arr[(*pi)++] = root->val; // 訪(fǎng)問(wèn)根節(jié)點(diǎn) } int* postorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize = TreeSize(root);//求節(jié)點(diǎn)個(gè)數(shù) int* returnArr = (int*)malloc(sizeof(int) * (*returnSize));//開(kāi)辟空間 int i = 0; _inorderTraversal(root, returnArr, &i);//遞歸函數(shù) return returnArr;//返回存儲(chǔ)數(shù)據(jù)的數(shù)組的指針 } 8.二叉樹(shù)的構(gòu)建以及遍歷 ? #include /* 讀取用戶(hù)輸入，保存在數(shù)組中，這個(gè)字符串的內(nèi)容剛好是二叉樹(shù)的前序遍歷 我們根據(jù)這個(gè)前序遍歷的結(jié)果來(lái)創(chuàng)建二叉樹(shù) 再對(duì)二叉樹(shù)進(jìn)行中序遍歷，輸出中序遍歷的結(jié)果 */ /* abc##de#g##f### 對(duì)于這個(gè)字符串，c是b的左子樹(shù)，b是a的左子樹(shù) */ /* 若遍歷中沒(méi)有給出NULL節(jié)點(diǎn)的情況，是不能根據(jù)某一個(gè)遍歷來(lái)創(chuàng)建二叉樹(shù)的 */ typedef struct BinaryTreeNode//定義二叉樹(shù)節(jié)點(diǎn)結(jié)構(gòu)類(lèi)型 { char data; struct BinaryTreeNode*left; struct BinaryTreeNode*right; }BTNode; BTNode*buyNode(char x)//創(chuàng)建節(jié)點(diǎn) { BTNode*newnode=(BTNode*)malloc(sizeof(BTNode)); newnode->data=x; newnode->left=newnode->right=NULL; return newnode; } BTNode*createTree(char*arr,int*pi)//創(chuàng)建二叉樹(shù)，返回根節(jié)點(diǎn),第一個(gè)參數(shù)是字符串，第二個(gè)參數(shù)是下標(biāo) { if(arr[*pi]=='#') { (*pi)++;//不要忘了往后面接著走 return NULL; } BTNode*root=buyNode(arr[(*pi)++]);//將數(shù)組中的數(shù)據(jù)存儲(chǔ)在二叉樹(shù)中，將數(shù)組中的數(shù)據(jù)傳到二叉樹(shù)節(jié)點(diǎn)內(nèi) root->left=createTree(arr,pi); //然后進(jìn)行二叉樹(shù)左節(jié)點(diǎn)的創(chuàng)建 root->right=createTree(arr,pi); //二叉樹(shù)右節(jié)點(diǎn)的創(chuàng)建 return root;//返回根節(jié)點(diǎn) } void InOeder(BTNode*root) { if(root==NULL) { return; } InOeder(root->left);//遞歸左子樹(shù) printf("%c ",root->data);//打印根節(jié)點(diǎn) InOeder(root->right);//遞歸右子樹(shù) } int main() { //讀取用戶(hù)輸入的字符串保存在字符數(shù)組中 char arr[100]; scanf("%s",arr); //根據(jù)字符串（前序遍歷）創(chuàng)建二叉樹(shù) int i=0; BTNode*root=createTree(arr,&i); //這里的root是創(chuàng)建的二叉樹(shù)的根節(jié)點(diǎn) //輸出二叉樹(shù)的中序遍歷 InOeder(root); return 0; } /* 當(dāng)pi=0時(shí)，我們創(chuàng)建了根節(jié)點(diǎn)a，然后創(chuàng)建a的左子樹(shù) 然后pi指向b，然后創(chuàng)建了根節(jié)點(diǎn)b，然后pi++,pi指向c， 創(chuàng)建了根節(jié)點(diǎn)c,然后pi++,pi指向了#，為空，那么我們就return 了 然后創(chuàng)建c的右子樹(shù) 那么pi++指向了#，那么就是空 那么就返回，回到了b這顆樹(shù)，那么b的左子樹(shù)就創(chuàng)建完成，那么就進(jìn)行b的右子樹(shù)的創(chuàng)建了 pi++指向了d,那么我們創(chuàng)建根節(jié)點(diǎn)d,然后pi++指向e，然后我們創(chuàng)建b的左節(jié)點(diǎn)e pi++,指向#，所以為空，那么我們就返回了，進(jìn)行e的右節(jié)點(diǎn)的創(chuàng)建 pi++指向了g，創(chuàng)建了根節(jié)點(diǎn)g pi++,指向了# 所以我們?cè)趧?chuàng)建g的左節(jié)點(diǎn)的時(shí)候返回了 那么我們就創(chuàng)建g的右節(jié)點(diǎn) pi++指向了#，所以為空，那么我們就返回了。返回到d,d的左子樹(shù)已經(jīng)創(chuàng)建好了 那么我們就創(chuàng)建d的右子樹(shù) pi++指向了f 我們創(chuàng)建根節(jié)點(diǎn)f 然后pi++,指向#，創(chuàng)建f的左節(jié)點(diǎn)，因?yàn)闉榭?，所以我們返回，然后?chuàng)建f的右節(jié)點(diǎn)，，Pi++,指向了#，為空，那么我們就返回了 那么d的左右子樹(shù)都已經(jīng)創(chuàng)建完成了 那么我們就返回到a了 在a這棵樹(shù)里面，a的左子樹(shù)b已經(jīng)創(chuàng)建好了 那么我們就進(jìn)行a的右子樹(shù)的創(chuàng)建了 pi++,指向了#，那么為空，我們就返回 到這里，a這顆二叉樹(shù)就創(chuàng)建好了 */ 可以參考這個(gè)圖片里面的二叉樹(shù) 6.二叉樹(shù)選擇題 ? 證明上述性質(zhì)：假設(shè)?個(gè)?叉樹(shù)有 a 個(gè)度為2的節(jié)點(diǎn)， b 個(gè)度為1的節(jié)點(diǎn)， c 個(gè)葉節(jié)點(diǎn)，則這個(gè)?叉樹(shù)的邊數(shù)是2a+b 另???，由于共有 a+b+c 個(gè)節(jié)點(diǎn)，所以邊數(shù)等于 a+b+c-1 結(jié)合上?兩個(gè)公式： 2a+b = a+b+c-1 ，即： a = c-1 就是度為2節(jié)點(diǎn)的個(gè)數(shù)等于葉子節(jié)點(diǎn)的個(gè)數(shù)-1 二叉樹(shù)性質(zhì)的題目： 某?叉樹(shù)共有 399 個(gè)結(jié)點(diǎn)，其中有 199 個(gè)度為 2 的結(jié)點(diǎn)，則該?叉樹(shù)中的葉?結(jié)點(diǎn)數(shù)為（B ） A 不存在這樣的?叉樹(shù) B 200 葉子節(jié)點(diǎn)的個(gè)數(shù)=節(jié)點(diǎn)數(shù)為2的節(jié)點(diǎn)的個(gè)數(shù)+1 n0=n2+1 C 198 D 199 2.在具有 2n 個(gè)結(jié)點(diǎn)的完全?叉樹(shù)中，葉?結(jié)點(diǎn)個(gè)數(shù)為（A ） A n n0+n1+n2=2N 因?yàn)閚0=n2+1 所以n0+n1+n0-1=2n0+n1-1=2N B n+1 完全二叉樹(shù)中有多少個(gè)度為1的節(jié)點(diǎn)呢？度為1的節(jié)點(diǎn)只可能為1個(gè)或者是0個(gè) C n-1 那么我們帶進(jìn)去的話(huà)，當(dāng)節(jié)點(diǎn)為0的時(shí)候，算出來(lái)的是小數(shù)，節(jié)點(diǎn)是1的時(shí)候，那么得 D n/2 到的就是n 3.?棵完全?叉樹(shù)的結(jié)點(diǎn)數(shù)位為531個(gè)，那么這棵樹(shù)的?度為（ ） A 11 B 10 2^h-1=531 那么得到的h=log532 那么得到的只能是10層，9層是不夠的 C 8 D 12 4.?個(gè)具有767個(gè)結(jié)點(diǎn)的完全?叉樹(shù)，其葉?結(jié)點(diǎn)個(gè)數(shù)為（B） A 383 B 384 C 385 D 386 這個(gè)題和第二題是差不多的 2n0+n1-1=767 n1只有1和0兩種可能 那么我們得到的n0=384 二叉樹(shù)遍歷題目 1.某完全?叉樹(shù)按層次輸出（同?層從左到右）的序列為 ABCDEFGH 。該完全?叉樹(shù)的前序序列為（A） A ABDHECFG B ABCDEFGH C HDBEAFCG D HDEBFGCA 2.?叉樹(shù)的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK;中序遍歷：HFIEJKG.則?叉樹(shù)根結(jié)點(diǎn)為（A） A E B F C G D H 3.設(shè)?課?叉樹(shù)的中序遍歷序列：badce，后序遍歷序列：bdeca，則?叉樹(shù)前序遍歷序列為D。 A adbce 后序遍歷的根節(jié)點(diǎn)肯定在最后面，那么a肯定是根節(jié)點(diǎn)，a的左節(jié)點(diǎn)是b, B decab 根據(jù)后續(xù)遍歷我們知道a的右節(jié)點(diǎn)是c C debac 那么結(jié)合中序遍歷來(lái)說(shuō)，d是c的左子樹(shù)，e是c的右子樹(shù) D abcde 4.某?叉樹(shù)的后序遍歷序列與中序遍歷序列相同，均為 ABCDEF ，則按層次輸出（同?層從左到右）的序列為（A） A FEDCBA B CBAFED C DEFCBA D ABCDEF 從后序遍歷我們知道根節(jié)點(diǎn)是F 但是中序遍歷中F在最后，那么說(shuō)明F沒(méi)有右子樹(shù)，只有左子樹(shù) 從中序遍歷和后序遍歷我們能知道E是F的左節(jié)點(diǎn) E的左子樹(shù)是D，D的左子樹(shù)是C，C的左子樹(shù)是B，B的左子樹(shù)是A 那么最后的圖形就是一根直線(xiàn)，最下面的是A 根據(jù)題目問(wèn)題，那么最后得到的就是A 證明上述性質(zhì)：假設(shè)?個(gè)?叉樹(shù)有 a 個(gè)度為2的節(jié)點(diǎn)， b 個(gè)度為1的節(jié)點(diǎn)， c 個(gè)葉節(jié)點(diǎn)，則這個(gè)?叉樹(shù)的邊數(shù)是2a+b 另???，由于共有 a+b+c 個(gè)節(jié)點(diǎn)，所以邊數(shù)等于 a+b+c-1 結(jié)合上?兩個(gè)公式： 2a+b = a+b+c-1 ，即： a = c-1 柚子快報(bào)邀請(qǐng)碼778899分享：c語(yǔ)言 手撕數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù) 推薦文章
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀(guān)點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Tospinob2b優(yōu)選平臺(tái)
