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