樹 堆一、什么是樹二、樹的相關(guān)術(shù)語三、樹的分類四、樹的表示五、二叉樹的介紹1.概念結(jié)構(gòu)2.特殊二叉樹2.1 滿二叉樹2.2 完全二叉樹3.遍歷方法4.二叉樹的存儲(chǔ)結(jié)構(gòu)4.1 順序存儲(chǔ)4.2 鏈?zhǔn)酱鎯?chǔ)5. 二叉樹存儲(chǔ)方式總結(jié)六、堆6.1 堆的定義6.2 堆的實(shí)現(xiàn)6.2.1 堆的結(jié)構(gòu)6.2.2 堆的初始化——void HPInit(HP* php)6.2.3 堆的插入數(shù)據(jù)入堆——void HPPush(HP* php)6.2.4 堆的刪除數(shù)據(jù)出堆——void HPPop(HP* php)6.2.5 取堆頂——HPDataType HPTop(HP* php)6.2.6 堆的銷毀——void HPInit(HP* php)一、什么是樹樹是非線性數(shù)據(jù)結(jié)構(gòu)由一組具有層次關(guān)系的節(jié)點(diǎn)組成不像鏈表、數(shù)組是一維線性結(jié)構(gòu)。類比現(xiàn)實(shí)中的大樹根在上、枝葉向下計(jì)算機(jī)樹根節(jié)點(diǎn)在最上層子節(jié)點(diǎn)往下延伸。核心特點(diǎn)1.且僅有一個(gè)根節(jié)點(diǎn)最頂層無父節(jié)點(diǎn)2.除根外每個(gè)節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)3.任意節(jié)點(diǎn)向下延伸可以分出若干子節(jié)點(diǎn)4.不存在環(huán)不能繞一圈回到自身。5.子樹是不相交的6.一棵由N個(gè)結(jié)點(diǎn)的樹有N-1條邊二、樹的相關(guān)術(shù)語?結(jié)點(diǎn)/雙親結(jié)點(diǎn)若?個(gè)結(jié)點(diǎn)含有?結(jié)點(diǎn)則這個(gè)結(jié)點(diǎn)稱為其?結(jié)點(diǎn)的?結(jié)點(diǎn)。?結(jié)點(diǎn)/孩?結(jié)點(diǎn)?個(gè)結(jié)點(diǎn)含有的?樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的?結(jié)點(diǎn)。eg:A是B C D E的父節(jié)點(diǎn)/雙親結(jié)點(diǎn)。B C D E是A的孩子結(jié)點(diǎn)/子節(jié)點(diǎn)結(jié)點(diǎn)的度?個(gè)結(jié)點(diǎn)有?個(gè)孩?他的度就是多少eg:A結(jié)點(diǎn)的度為4B結(jié)點(diǎn)的度為2C結(jié)點(diǎn)的度為1…葉?結(jié)點(diǎn)/終端結(jié)點(diǎn)度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)eg:這棵樹的葉子結(jié)點(diǎn)有F G H I J K兄弟結(jié)點(diǎn)具有相同?結(jié)點(diǎn)的結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)(親兄弟)eg: B C D E四個(gè)結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)F G互為兄弟結(jié)點(diǎn)…樹的度?棵樹中最?的結(jié)點(diǎn)的度稱為樹的度。eg:這棵樹的度為4結(jié)點(diǎn)的層次從根開始定義起根為第1 層根的?結(jié)點(diǎn)為第2層以此類推樹的?度或深度樹中結(jié)點(diǎn)的最?層次eg:這棵樹的高度/深度為3結(jié)點(diǎn)的祖先從根到該結(jié)點(diǎn)所經(jīng)分?上的所有結(jié)點(diǎn)eg:A是所有結(jié)點(diǎn)的祖先路徑從一個(gè)節(jié)點(diǎn)走到另一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)序列eg:A-G的路徑A-B-G…森林由mm0 棵互不相交的樹的集合稱為森林三、樹的分類3.1 普通樹多叉樹每個(gè)節(jié)點(diǎn)可以有任意多個(gè)子節(jié)點(diǎn)。上面舉的例子就是普通樹3.2 二叉樹每個(gè)節(jié)點(diǎn)最多只能有 2 個(gè)子節(jié)點(diǎn)分左孩子、右孩子順序不能互換左子樹左邊子節(jié)點(diǎn)右子樹右邊子節(jié)點(diǎn)四、樹的表示常用孩子兄弟表示法每個(gè)節(jié)點(diǎn)固定 2 個(gè)指針1.firstchild第一個(gè)左孩子即長子結(jié)點(diǎn)2.rightsib指向右側(cè)的的兄弟結(jié)點(diǎn)structCSNode{intdata;structCSNode*firstchild;// 長子structCSNode*rightsib;// 右兄弟};五、二叉樹的介紹1.概念結(jié)構(gòu)1.1二叉樹是每個(gè)節(jié)點(diǎn)最多擁有 2 個(gè)子節(jié)點(diǎn)的樹形結(jié)構(gòu)嚴(yán)格區(qū)分左子樹、右子樹左右不能互換。五種基本形態(tài)空樹、只有根、只有左孩子、只有右孩子、左右孩子都有。1.2二叉樹的特點(diǎn)1二叉樹不存在度大于2的結(jié)點(diǎn)2二叉樹的有左右之分次序不能顛倒二叉樹是有序樹空樹空的二叉樹沒有根結(jié)點(diǎn)只有根結(jié)點(diǎn)的也是二叉樹1.3二叉樹的性質(zhì)一 棵二叉樹的深度為 h節(jié)點(diǎn)總數(shù) 為n則可知第 i 層最多有2^(i-1)個(gè)節(jié)點(diǎn)。深度 h 的二叉樹最多有 2^k - 1 個(gè)節(jié)點(diǎn)n0n21葉子節(jié)點(diǎn)數(shù) 度為 2 節(jié)點(diǎn)數(shù) 1完全二叉樹編號(hào)為 i的節(jié)點(diǎn)其父節(jié)點(diǎn)編號(hào)為i/2向下取整其左孩子編號(hào)為2i其右孩子編號(hào)為2i12.特殊二叉樹2.1 滿二叉樹?個(gè)?叉樹如果每?個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最?值則這個(gè)?叉樹就是滿?叉樹。也就是說如果?個(gè)?叉樹的層數(shù)為k且結(jié)點(diǎn)總數(shù)是2^k-1則它就是滿?叉樹。第k層有2^(k-1個(gè)結(jié)點(diǎn)2.2 完全二叉樹完全?叉樹是效率很?的數(shù)據(jù)結(jié)構(gòu)完全?叉樹是由滿?叉樹?引出來的。對(duì)于深度為K的有n個(gè)結(jié)點(diǎn)的?叉樹當(dāng)且僅當(dāng)其每?個(gè)結(jié)點(diǎn)都與深度為K的滿?叉樹中編號(hào)從1?n的結(jié)點(diǎn)??對(duì)應(yīng)時(shí)稱之為完全?叉樹。要注意的是滿?叉樹是?種特殊的完全?叉樹。特點(diǎn)1.除了最后一層每層節(jié)點(diǎn)的個(gè)數(shù)達(dá)到最大2.最后一層個(gè)數(shù)不一定達(dá)到最大最后一層結(jié)點(diǎn)個(gè)數(shù)達(dá)到最大那么這個(gè)二叉樹即使完全二叉樹也是滿二叉樹3.結(jié)點(diǎn)從左到右依次排序性質(zhì)若規(guī)定根結(jié)點(diǎn)的層數(shù)為1具有n個(gè)結(jié)點(diǎn)的滿?叉樹的深度(h log2(n1)以2為底n1 為對(duì)數(shù))3.遍歷方法以根節(jié)點(diǎn)訪問順序區(qū)分3.1 前序遍歷先根遍歷根左右訪問當(dāng)前根節(jié)點(diǎn)遍歷左子樹遍歷右子樹步驟演示根 A訪問 A遍歷 A 左子樹 B根 B訪問 BB 左 D訪問 DD 無孩子返回B 右 E訪問 EE 無孩子返回遍歷 A 右子樹 C根 C訪問 CC 左 F訪問 F無孩子C 右 G訪問 G上述圖前序遍歷的結(jié)果為A B D E C F G3.2 中序遍歷左 根 右執(zhí)行邏輯遞歸遍歷左子樹訪問當(dāng)前根節(jié)點(diǎn)遞歸遍歷右子樹中序遍歷結(jié)果D B E A F C G3.3 后序遍歷左 右 根執(zhí)行邏輯遞歸遍歷左子樹遞歸遍歷右子樹訪問當(dāng)前根節(jié)點(diǎn)后序遍歷結(jié)果D E B F G C A3.4 層序遍歷從上到下、從左到右借助隊(duì)列實(shí)現(xiàn)層序遍歷結(jié)果A B C D E F G4.二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹一般有兩種存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)4.1 順序存儲(chǔ)順序存儲(chǔ)底層結(jié)構(gòu)是數(shù)組適用場景僅適合完全二叉樹 / 滿二叉樹普通二叉樹會(huì)大量浪費(fèi)數(shù)組空間。存儲(chǔ)規(guī)則數(shù)組下標(biāo)從 1 開始方便計(jì)算父子關(guān)系設(shè)當(dāng)前節(jié)點(diǎn)下標(biāo)為 i父節(jié)點(diǎn)下標(biāo)i/2向下取整左孩子2i右孩子2i1空位表示無節(jié)點(diǎn)示例4.2 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)浇Y(jié)構(gòu)底層結(jié)構(gòu)為鏈表?鏈表來表??棵?叉樹即?鏈來指?元素的邏輯關(guān)系。通常的?法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成數(shù)據(jù)域和左右指針域左右指針分別?來給出該結(jié)點(diǎn)左孩?和右孩?所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。5. 二叉樹存儲(chǔ)方式總結(jié)為了更清晰地展示二叉樹的不同存儲(chǔ)方式及其適用場景我們可以用以下思維導(dǎo)圖進(jìn)行歸納二叉樹存儲(chǔ)方式鏈?zhǔn)酱鎯?chǔ):任意二叉樹通用二叉鏈表data, left, right三叉鏈表data, left, right, parent順序存儲(chǔ)數(shù)組普通完全二叉樹:無大小規(guī)則:僅層序存放堆:完全二叉樹 父子數(shù)值大小約束大根堆大頂堆:任意父節(jié)點(diǎn) ≥ 子節(jié)點(diǎn)小根堆小頂堆:任意父節(jié)點(diǎn) ≤ 子節(jié)點(diǎn)要點(diǎn)解析鏈?zhǔn)酱鎯?chǔ)通過指針引用連接節(jié)點(diǎn)是最通用、最靈活的存儲(chǔ)方式可以表示任意形態(tài)的二叉樹。根據(jù)指針數(shù)量可分為二叉鏈表左、右孩子指針和三叉鏈表增加指向父節(jié)點(diǎn)的指針。順序存儲(chǔ)使用數(shù)組按層序存放節(jié)點(diǎn)。這種方式僅適用于完全二叉樹包括滿二叉樹否則會(huì)浪費(fèi)大量數(shù)組空間。它又可分為兩類普通完全二叉樹僅滿足完全二叉樹的結(jié)構(gòu)特性層序、從左到右節(jié)點(diǎn)間沒有數(shù)值大小約束。堆在完全二叉樹的基礎(chǔ)上增加了父子節(jié)點(diǎn)間的數(shù)值大小約束大根堆或小根堆是一種特殊的、高效的順序存儲(chǔ)應(yīng)用。通過此圖可以直觀看出選擇存儲(chǔ)方式時(shí)首先要判斷二叉樹是否為完全二叉樹。如果是則可以考慮高效的順序存儲(chǔ)尤其是堆如果不是則應(yīng)使用鏈?zhǔn)酱鎯?chǔ)。六、堆6.1 堆的定義堆是特殊的完全二叉樹只能用數(shù)組順序存儲(chǔ)所以堆必須是完全二叉樹分類大根堆大頂堆任意父節(jié)點(diǎn) ≥ 左右孩子堆頂數(shù)組第一個(gè)元素是整個(gè)序列最大值小根堆小頂堆任意父節(jié)點(diǎn) ≤ 左右孩子堆頂是整個(gè)序列最小值堆的節(jié)點(diǎn)編號(hào)為了在堆的實(shí)現(xiàn)中節(jié)省空間貼合編程語言數(shù)組特性方便代碼實(shí)現(xiàn)堆的編號(hào)一般不像前面從1 開始而是從0開始所以堆的編號(hào)有以下特點(diǎn)對(duì)于具有n個(gè)結(jié)點(diǎn)的完全?叉樹如果按照從上?下從左?右的數(shù)組順序?qū)λ薪Y(jié)點(diǎn)從0 開始編號(hào)則對(duì)于序號(hào)為i的結(jié)點(diǎn)有若i0i位置結(jié)點(diǎn)的雙親序號(hào)i-1/2若i0i為根結(jié)點(diǎn)編號(hào)若2i1n 左孩?序號(hào)2i1 2i1n 否則?左孩?若2i2n 右孩?序號(hào)2i2 2i2n 否則?右孩?6.2 堆的實(shí)現(xiàn)以小堆為例6.2.1 堆的結(jié)構(gòu)堆是完全二叉樹采用順序存儲(chǔ)結(jié)構(gòu)所以堆的底層結(jié)構(gòu)為數(shù)組所以堆的結(jié)構(gòu)定義為數(shù)組表示數(shù)組的有效個(gè)數(shù)大小的size,數(shù)組的空間容量//堆的結(jié)構(gòu)——順序存儲(chǔ)底層結(jié)構(gòu)為數(shù)組typedefintHPDataType;typedefstructHeap{HPDataType*arr;//底層結(jié)構(gòu)intsize;//有效數(shù)據(jù)的個(gè)數(shù)intcapacity;//空間容量}HP;和棧的結(jié)構(gòu)定義相似。6.2.2 堆的初始化——void HPInit(HP* php)有了堆的結(jié)構(gòu)定義之后就可以創(chuàng)建堆了同時(shí)不要忘記對(duì)堆結(jié)構(gòu)成員進(jìn)行初始化操作。調(diào)用堆的初始化函數(shù)時(shí)實(shí)參傳過去的是堆的地址所以形參在接受時(shí)應(yīng)當(dāng)用一級(jí)指針//堆的初始化voidHPInit(HP*php){php-arrNULL;php-capacityphp-size0;}6.2.3 堆的插入數(shù)據(jù)入堆——void HPPush(HP* php)由于堆是一個(gè)完全二叉樹完全二叉樹的插入數(shù)據(jù)就是根結(jié)點(diǎn)往根節(jié)點(diǎn)的左子樹插根節(jié)點(diǎn)的右子樹插左子樹的左子樹插左子樹的右子樹插右子樹的左子樹插右子樹的右子樹插…放在堆的底層結(jié)構(gòu)——數(shù)組中看就是向數(shù)組的最后一個(gè)元素后面插入數(shù)據(jù)。插入數(shù)據(jù)之前要判斷是否有足夠的空間可以插入數(shù)據(jù)有的話直接插入更新size。沒有的話擴(kuò)容更新capacity 和arr的地址再插入更新size。當(dāng)sizecapacity時(shí)就需要擴(kuò)容擴(kuò)容用realloc來實(shí)現(xiàn)堆是由大堆和小堆的分類的所以在插入完數(shù)據(jù)之后要進(jìn)行判斷插入之后的邏輯結(jié)構(gòu)是否滿足大堆或者是小堆的定義不滿足需要調(diào)整這個(gè)調(diào)整方法就是向上調(diào)整法以小堆為例向上調(diào)整法void AdjustUp(HPDataType* arr, int child)參數(shù)說明需要得到要調(diào)整的堆的地址即底層數(shù)組的地址還需要得到插入數(shù)據(jù)的編號(hào)也是數(shù)組下標(biāo)child用來計(jì)算雙親結(jié)點(diǎn)的編號(hào)也是數(shù)組下標(biāo)進(jìn)行調(diào)整什么時(shí)候需要向上調(diào)整當(dāng)孩子結(jié)點(diǎn)的值小于雙親結(jié)點(diǎn)的值時(shí)需要進(jìn)行調(diào)整因?yàn)橐孕《褳槔敬蠖训脑捳{(diào)整條件與小堆 相反其他不變】調(diào)整是將孩子結(jié)點(diǎn)的值與雙親結(jié)點(diǎn)的值互換但這只是向上調(diào)整了一次當(dāng)堆有多層時(shí)需要將上述步驟重復(fù)所以需要while循環(huán)循環(huán)條件是child0向上調(diào)整的代碼voidSwap(int*x,int*y){inttmp*x;*x*y;*ytmp;}//向上調(diào)整法voidAdjustUp(HPDataType*arr,intchild){//求雙親結(jié)點(diǎn)intparent(child-1)/2;while(child0){//大堆// if (arr[child] arr[parent])//小堆if(arr[child]arr[parent]){//調(diào)整,即交換孩子結(jié)點(diǎn)和雙親結(jié)點(diǎn)Swap(arr[child],arr[parent]);//更新child和parentchildparent;parent(child-1)/2;}else{//滿足小堆的結(jié)構(gòu)不用調(diào)整break;}}}堆的插入數(shù)據(jù)的完整代碼voidSwap(int*x,int*y){inttmp*x;*x*y;*ytmp;}//向上調(diào)整法voidAdjustUp(HPDataType*arr,intchild){//求雙親結(jié)點(diǎn)intparent(child-1)/2;while(child0){//大堆// if (arr[child] arr[parent])//小堆if(arr[child]arr[parent]){//調(diào)整,即交換孩子結(jié)點(diǎn)和雙親結(jié)點(diǎn)Swap(arr[child],arr[parent]);//更新child和parentchildparent;parent(child-1)/2;}else{//滿足小堆的結(jié)構(gòu)不用調(diào)整break;}}}//堆的插入數(shù)據(jù)voidHPPush(HP*php,HPDataType x){assert(php);//判斷空間是否足夠if(php-sizephp-capacity){//擴(kuò)容intnewcapacityphp-capacity0?4:2*php-capacity;HPDataType*tmp(HPDataType*)realloc(php-arr,newcapacity*sizeof(HPDataType));//判斷擴(kuò)容是否成功if(tmpNULL){perror(realloc fail!);exit(1);}//擴(kuò)容成功更新capacity,和arr空間的地址php-arrtmp;php-capacitynewcapacity;}//空間足夠php-arr[php-size]x;//向上調(diào)整AdjustUp(php-arr,php-size);php-size;}6.2.4 堆的刪除數(shù)據(jù)出堆——void HPPop(HP* php)出堆在堆的結(jié)構(gòu)里面刪除數(shù)據(jù)只能操作堆頂為了保持其他結(jié)點(diǎn)的關(guān)系不變最小程度的修改原來堆的關(guān)系我們一般直接將最后一個(gè)元素與第一個(gè)元素交換之后進(jìn)行向下調(diào)整以小堆為例的向下調(diào)整法voidSwap(int*x,int*y){inttmp*x;*x*y;*ytmp;}//向下調(diào)整voidAdjustDown(HPDataType*arr,intparent,intn){intchildparent*21;while(childn){//判斷左右孩子的大小// 大堆if (child1narr[child] arr[child 1]);//小堆child1不能越界if(child1narr[child]arr[child1]){childchild1;}//孩子結(jié)點(diǎn)與雙親結(jié)點(diǎn)的比較//大堆a(bǔ)rr[child] arr[parent]//小堆if(arr[child]arr[parent]){//調(diào)整Swap(arr[child],arr[parent]);parentchild;childparent*21;}else{break;}}}//堆的刪除數(shù)據(jù)voidHPPop(HP*php){assert(!HPEmpty(php));//交換Swap(php-arr[0],php-arr[php-size-1]);--php-size;//向下調(diào)整AdjustDown(php-arr,0,php-size);}堆的刪除操作的完整代碼//判斷堆是否為空boolHPEmpty(HP*php){assert(php);returnphp-size0;}//向下調(diào)整voidAdjustDown(HPDataType*arr,intparent,intn){intchildparent*21;while(childn){//判斷左右孩子的大小// 大堆if (child1narr[child] arr[child 1]);//小堆child1不能越界if(child1narr[child]arr[child1]){childchild1;}//孩子結(jié)點(diǎn)與雙親結(jié)點(diǎn)的比較//大堆a(bǔ)rr[child] arr[parent]//小堆if(arr[child]arr[parent]){//調(diào)整Swap(arr[child],arr[parent]);parentchild;childparent*21;}else{break;}}}//堆的刪除數(shù)據(jù)voidHPPop(HP*php){assert(!HPEmpty(php));//交換Swap(php-arr[0],php-arr[php-size-1]);--php-size;//向下調(diào)整AdjustDown(php-arr,0,php-size);}6.2.5 取堆頂——HPDataType HPTop(HP* php)堆頂元素就是數(shù)組下標(biāo)為0的元素取堆頂取出的值是最值//取堆頂數(shù)據(jù)HPDataTypeHPTop(HP*php){assert(!HPEmpty(php));returnphp-arr[0];}6.2.6 堆的銷毀——void HPInit(HP* php)//堆的銷毀voidHPDestory(HP*php){//判斷arr是否為空為空就不需要free了if(php-arr)free(php-arr);//銷毀之后還原結(jié)構(gòu)體成員的值php-arrNULL;php-sizephp-capacity0;}