【數據結構】--二叉樹--堆(上)

一、樹的概念和結構

概念：

樹是一種非線性的數據結構，他是由n(n>=0)個有限結點組成一個具有層次關系的集合。其叫做樹，是因為他倒過來看就和一棵樹差不多，其實際上是根在上，樹枝在下的。

樹的特點：

1、其有一個特殊的結點，稱為根結點，根結點沒有前驅結點。

2、除根結點，其余的結點被分為M(M>0)個互不相交的集合，其中每個集合其又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，其可以有0個或者多個后繼。所以樹是遞歸定義的。

如上圖所示，樹的結構其倒過來就和我們現實生活中的樹長得很像了。

要注意的是，樹形結構中，我們的子樹之間是不能有交集的。

下面為樹的幾個要求：

1、子樹之間是不相交的（如果相交那么就是另外一種數據結構圖了）

2、除了根結點外，每個結點有且僅有一個父節點，即前驅結點有且僅有一個。

3、一顆有N個結點的樹，其邊有N-1條。

?樹的相關術語：

父結點：?若?個結點含有?結點，則這個結點稱為其?結點的?結點；如上圖：A是B的? 結點

子結點：?個結點含有的?樹的根結點稱為該結點的?結點；如上圖：B是A的孩?結點?

結點的度：?個結點有?個孩?，他的度就是多少；?如A的度為6，F的度為2，K的度為0

樹的度：一顆樹中，最大的結點的度就是這個樹的度，如上圖，結點的度最大的是A為6，那么樹的度就為6。

葉子節點：度為0的結點就為葉子結點，如上圖，B、C、H、I、J、P、Q、K、L、M、N就為葉子結點。

分支結點：度不為0的結點

結點的層次：從根的開始定義起，根為第1層、以此類推

樹的高度或深度：樹中結點的最大層次。如上圖為4?

結點的祖先：根結點。如上就是A結點

路徑：?條從樹中任意節點出發，沿?節點-?節點連接，達到任意節點的序列；?如A到Q的路徑為： A-E-J-Q；H到Q的路徑H-D-A-E-J-Q

子孫：以某結點為根的子樹中任一結點都稱為該結點的子孫。

森林：由m(m>0)棵互不相交的樹的集合稱為森林

樹的表示：

前面我們已經知道我們的樹是咋樣的情況了，那么我們在代碼中要如何進行表示一個樹結構呢？

在程序中我們表示樹的方式有很多種，我們要根據使用場景來選擇合適的表示方式，常見的表示方法有：孩子表示法，孩子兄弟表示法，雙親表示法。

下面是我們的孩子兄弟表示法：

孩子兄弟表示法，就是兩個指針，一個指針指向其左孩子，一個指針指向其右邊的第一個兄弟。

樹在實際運用：

實際上我們早已在電腦上使用過樹結構了，我們計算機上的文件存儲和管理文件的結構，其就是使用的樹形結構來組織和管理文件和文件夾的。在文件系統中，樹結構被廣泛應用，通過父結點，層層的往下找其子結點，然后找到最終的文件。其通過父結點和子結點之間的關系來表示不同的層級之間的文件和上一層文件夾之間的關系。

二、二叉樹?

二叉樹的概念和結構：

二叉樹是樹形結構中的一種特殊情況，也是我們最常用的一種樹形結構，一顆二叉樹是結點的一個有限集合，該集合由一個根結點再加上兩棵分別稱為左子樹和右子樹的二叉樹組成，或者為空。

如下：

在上面的圖中我們可以看到二叉樹的特點：

1、二叉樹不存在度大于2的結點

2、二叉樹的子樹是有左右之分的，次序是不能顛倒的，所以二叉樹是有序樹

二叉樹會有下面幾種情況：

特殊的二叉樹：

1、滿二叉樹

一個二叉樹，如果其每一層的結點樹都達到最大值，那么這個二叉樹就是滿二叉樹。即：我們現在有一個層數為k的二叉樹，那么我們的結點數，為2的k次方-1的時候，那么我們的二叉樹就是滿二叉樹。

如下：

2、完全二叉樹

完全二叉樹，也是一種特殊的二叉樹，它的定義是在二叉樹的前提下，其除了最后一層外，其余的層的結點都是滿的，而且最后一層的結點都是集中在左側。

如下：

二叉樹的性質：

1、若規定根結點的層次為1，則一顆樹非空二叉樹的第i層上最多的結點個數為2的i次方-1個結點

2、若規定根結點的層次為1，則一棵深度為h的二叉樹的最多的結點數為2的h次方-1個結點

3、若規定根結點的層次為1?，具有n個結點的滿二叉樹的深度h=log2(n+1)

二叉樹的存儲結構：

二叉樹一般使用兩種結構存儲嗎，一種順序結構，一種是鏈式結構。

順序存儲：

順序存儲結構底層上是使用數組來存儲，不過一般使用數組存儲的話就是滿二叉樹，因為完全二叉樹使用數組存儲，這是因為不是完全二叉樹的話，其會造成空間的浪費。

如下所示：

不過實際上我們通常將堆（二叉樹的一種）使用順序結構的數組來進行存儲，不過要注意的是這里的堆和操作系統虛擬進程地址空間中的堆是兩個回事，一個是數據結構，一個是操作系統中管理內存的一塊區域分段。

鏈式存儲：
二叉樹的鏈式存儲通過鏈表形式動態的進行表示結點間的邏輯關系，其方法如下：

通常的?法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別?來給出該結點左孩?和右孩?所在的鏈結點的存儲地址。鏈式結構?分為?叉鏈和三叉鏈，當前我們學習中?般都是?叉鏈。后?課程學到?階數據結構如紅?樹等會?到三叉鏈。

其具體思路如下：

1、結點結構：

其有三個成員組成：

數據域：存儲當前結點的元素值

左指針域：指向左子結點的地址

右指針域：指向右子結點的地址

2、鏈式類型劃分：

二叉鏈：僅含左右子結點指針

? ? ? ? ? ? ? ?空間效率高，滿足基礎算法實現需求

三叉鏈：增加父結點指針域

? ? ? ? ? ? ? ?便于逆向溯源，應用于紅黑樹等復雜數據結構

三、實現順序結構二叉樹

?堆的概念和結構：

如果有?個關鍵碼的集合K? =?{k0 ,k1, k2, ...，kn?1 }，把它的所有元素按完全?叉樹的順序存儲?式存儲，在?個?維數組中，并滿?：Ki<=? K(2i+1)

（K >=K（2*i+1）且Ki<=? K (2*i+2))i = 0、1、2...，則稱為?堆(或?堆)。將根結點最?的堆叫做最?堆或?根堆，根結點最?的堆叫做最?堆或?根堆。

如下：

堆的性質：

1、堆中的某個結點的值總是不大于或者不小于其父結點

2、堆總是一棵完全二叉樹

二叉樹的一些特點：

對于具有n個結點的完全二叉樹，如果按照從上到下，從左至右的順序，對所有的結點從0開始進行編號，那么對于編號為i的結點有下面的幾個性質：

1、若i>0，i位置的父結點序號：(i-1)/2;i=0的話，那么其是根結點，沒有父結點

2、若2i+1<n，那么左孩子序號為2i+1，如果2i+1>=n，那么沒有左孩子

3、若2i+2<n，那么其右孩子序號為2i+2，如果2i+2>=n那么沒有右孩子

堆的實現：

前面我們已經了解了啥是堆，堆的結構是如何的，那么我們下面就通過代碼來實現堆的功能。

首先我們要創建一個堆結構，那么我們該如何進行表示呢？通過上面的學習我們知道，堆是順序存放的，那么我們堆的實現的底層還是使用數組來實現。

然后就是簡單的初始化：

那么我們的堆如何進行插入數據呢？

我們會選擇在尾部進行插入，我們插入后，如何將當前的二叉樹變成堆的結構，我們的堆是有序的，其子結點要不就是大于或者等于其父結點，要不就小于或者等于其父結點，所以我們插入尾部后，我們還需要對這個二叉樹進行調整，那么我們的堆如果是小堆，那么我們小的元素就要往上存放，父結點一定要小于子結點，所以我們可以通過當前結點找到其父結點，然后進行比較，如果新插入的結點比其父結點要小，那么新插入的結點和父結點就進行交換。如果是大堆的話，那么就還是一樣，大的往上走即可。這種方法我們叫做向上調整法。

代碼如下：