這篇文章給大家分享的是有關C++怎么實現二叉樹及堆的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。
樹是一種非線性數據結構，它是由n個有限結點組成的具有層次關系的集合。把它叫樹是因為它是根朝上，葉子朝下的
來上圖瞧瞧
一顆二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根結點加上兩棵分別稱為左子樹和右子樹。
如圖所示：
二叉樹有以下特點：
1、每個二叉樹最多有兩顆子樹，所以二叉樹不存在度為2的結點。
2、二叉樹的子樹有左右之分，其子樹的順序不能顛倒。
1、若規定根結點的層數為第一層，則一顆非空二叉樹的第i層上最多有z^(k-1)個結點
2、若規定根結點的層數為第一層，則深度為h的二叉樹的最大結點數是2^k-1個。
3、對于任何一顆二叉樹，度為0的結點（葉子結點）的個數為n0 ,度為2的結點個數為n2則一定有，n0 = n2 + 1。
4、若規定根結點的層數為第一層,具有N個結點的滿二叉樹的深度h = log2(N+1)[說明：以2為底的N+1的對數]，這個可以由性質2推導得到。
5、對于具有n個結點的完全二叉樹，如果按照從上到下從左到右的數組順序對所有結點從0開始編號，即對于數組下標i的結點有：
1）i>1,i位置的父結點的在數組中的下標為（i-1）/2.
2)i位置結點的左孩子結點的下標為2i+1,右結點下標為2i+2。
1、滿二叉樹：一個二叉樹，如果每一層的結點數都達到了最大，如果這個二叉樹的層次是k，則其結點數是2^k-1。
2、完全二叉樹：用最直白的話來說就是，樹的深度或者高度為k，前k-1層的結點都是滿的，只有最后的第k層不滿但是從左到右的結點必須是連續的。
其實滿二叉樹是一種特殊的完全二叉樹。
如圖所示：
圖為完全二叉樹，要是最后一層全滿則為滿二叉樹。
滿足：
2^k-1-x = N;
x的取值范圍是[0,2^(k-1)-1]
普通的二叉樹是不適合用數組來存儲的，因為可能會存在大量的空間浪費，而完全二叉樹更適合用順序存儲，順序存儲的隨機訪問特性，會右巨大的優點。我們通常把堆（是一種完全二叉樹）采用順序存儲，需要注意的是這里的堆和操作系統虛擬進程地址空間中的堆是兩回事，一個是數據結構一個是OS中管理內存的一塊區域分段。
堆分為大根堆和小根堆。
大根堆：父親結點>=孩子結點
小根堆：父親結點<=孩子結點
上面是堆的邏輯結構，下面是物理結構
首先構建堆我們要了解一個算法，叫向下調整算法。我們以小根堆為例，我們把圖示的完全二叉樹構建為小堆，這個二叉樹有個條件是根結點的兩個子樹都是小堆才可以進行向下調整算法。
3.2.1 向下調整算法
根結點的左右子樹都是小堆，根結點27和左右子樹的根結點較小的那一個交換位置，然后依次進行，直到葉子結點。就把最小的15結點上浮到堆頂的位置。這個算法的前提是根節點的左右子樹都是小堆，如果我們想把任意的的數組構建成小堆顯然不滿足條件。在下面我們介紹把任意數組構建成小堆的辦法。
向下調整算法的代碼如下：
void AdjustDown(HeapDataType* a, int n, int root)
{
//父子下標的初始化
int parent = root;
int child = parent * 2 + 1;
//循環向下調整，把最小值（或者最大值浮到堆頂）
while (child < n)
{
//選出左右孩子中較小的孩子，作為child，child+1 < n保證下標不能越界
if (child+1 < n && a[child + 1] < a[child])
{
++child;
}
//父親比孩子小二者交換位置,并更新迭代孩子的位置
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
//迭代parent child
parent = child;
child = parent * 2 + 1;
}
else
{
break;//當孩子 >= 父親的時候，滿足小堆的條件，跳出循環節課，否則就會死循環
}
}
}3.2.2 堆的構建
把給定的數據化成完全二叉樹的邏輯結構如上圖所示，這個數組（二叉樹）顯然不能滿足向下調整算法的理想條件，所以我們把問題拆分，比如你先思考下這個問題，把左子樹和右子樹全部構建成小堆不就滿足條件了嘛，但是子樹的左右子不是小堆怎么辦呢，那么同樣的道理，把它也構建成子樹就可以了，那么我們可以從葉子結點向上每個結點都執行一邊向下調整算法不就可以了嘛。其實我們不必從葉子結點開始因為葉子結點沒有子樹其實都可以看成是小堆或者大堆。所以從第一個非葉子結點開始調整即可。
也就是從圖中紫色圈圈畫出來的那個開始調整即可，直到根結點93，就會把一個數組構建成小堆（大堆）。
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}（n-1-1）/2為第一非葉子結點下標。
3.2.3 堆排序
有了上面的知識做鋪墊，堆排序就可以很好的理解了。
1、把數組構建成大堆或者小堆，位于堆頂的數據就是最大值或者最小值，把堆頂數據和最后的結點位置的數據（數組元素最后一個）互換。然后對前n-1個結點重新向下調整為大堆或者小堆。直到剩下最后一個根節點就排序完成。
只是要升序：構建大堆，要降序：構建小堆，你細細品。
代碼如下：
//堆排序
void HeapSort(int* a, int n)
{
//堆排序的第一步就是構建堆,構建堆的時間復雜度是O(n),此時是小堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
//如果是升序，構建大堆
//如果是降序，構建小堆
//是反著的，因為要和最后一個進行交換
int end = n - 1;
while (end>0)
{
//把堆頂（最小或者最大）和最后的的元素交換，然后從0到n-2繼續向下調整
//把次?。ù未螅┑脑匾策x出來，直到剩最后一個，堆排序完成
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}### 3.2.4 堆的的增刪查改
聲明：
```c
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <windows.h>
typedef int HeapDataType;
typedef struct Heap
{
HeapDataType* arr;
int size;
int capacity;
} Heap;
//堆的初始化，內部有堆的創建
void HeapInit(Heap* php, HeapDataType* a, int n);
//堆的銷毀
void HeapDestory(Heap* php);
//堆的插入數據
void HeapPush(Heap* php, HeapDataType x);
//堆的刪除數據
void HeapPop(Heap* php);
//獲取堆頂數據
HeapDataType HeapTop(Heap* php);
//對傳入的數組內的數據進行堆排序
void HeapSort(int* a, int n);定義：
#include "Heap.h"
//堆是一種完全二叉樹，用順序存儲（數組）比較好
//用于交換兩個數據
void Swap(HeapDataType* n1, HeapDataType* n2)
{
HeapDataType temp = *n1;
*n1 = *n2;
*n2 = temp;
}
//向下調整算法___老重要了，這是理解堆排序和topk問題以及堆這里相關題的基礎
//向下調整結束的情況有兩個一個是a[parent]<a[child],另一個是從堆頂到數組結束全部比較完
void AdjustDown(HeapDataType* a, int n, int root)
{
//父子下標的初始化
int parent = root;
int child = parent * 2 + 1;
//循環向下調整，把最小值（或者最大值浮到堆頂）
while (child < n)
{
//選出左右孩子中較小的孩子，作為child，child+1 < n保證下標不能越界
if (child+1 < n && a[child + 1] < a[child])
{
++child;
}
//父親比孩子小二者交換位置,并更新迭代孩子的位置
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
//迭代parent child
parent = child;
child = parent * 2 + 1;
}
else
{
break;//當孩子 >= 父親的時候，滿足小堆的條件，跳出循環節課，否則就會死循環
}
}
}
//向上調整算法
//用在HeapPush中
void AdjustUp(HeapDataType* a, int n, int child)
{
int parent = (child - 1) / 2;
while (child>0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
//迭代
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//堆的初始化，內部有堆的創建
void HeapInit(Heap* php, HeapDataType* a, int n)
{
HeapDataType* temp = (HeapDataType*)malloc(sizeof(HeapDataType)*n);
if (temp)
{
php->arr = temp;
}
else
{
printf("內存申請失??！");
exit(-1);
}
//將傳進來的數組拷貝給malloc出來的空間，用來后續的堆的創建，刪除，插入數據等操作
memcpy(php->arr, a, sizeof(HeapDataType)*n);
php->size = n;
php->capacity = n;
//把拷貝進來的數組，構建成堆
//從倒數第一個非葉子節點進行構建(直接把數組畫成一個完全二叉樹可以直接由圖得到第一個
//非葉子節點的下標）
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(php->arr, php->size, i);
}
}
//堆排序
void HeapSort(int* a, int n)
{
//堆排序的第一步就是構建堆,構建堆的時間復雜度是O(n),此時是小堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
//如果是升序，構建大堆
//如果是降序，構建小堆
//是反著的，因為要和最后一個進行交換
int end = n - 1;
while (end>0)
{
//把堆頂（最小或者最大）和最后的的元素交換，然后從0到n-2繼續向下調整
//把次?。ù未螅┑脑匾策x出來，直到剩最后一個，堆排序完成
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
//銷毀堆
void HeapDestory(Heap* php)
{
assert(php);
free(php->arr);
php->arr = NULL;
php->capacity = php->size = 0;
}
//堆的插入數據
void HeapPush(Heap* php, HeapDataType x)
{
assert(php);
if (php->size == php->capacity)
{
php->capacity *= 2;
HeapDataType* tmp = (HeapDataType*)realloc(php->arr, sizeof(HeapDataType)*php->capacity);
if (tmp)
{
php->arr = tmp;
}
else
{
printf("擴容失??！\n");
exit(-1);
}
}
php->arr[php->size++] = x;
AdjustUp(php->arr, php->size, php->size - 1);
}
//堆的刪除數據,要刪除堆頂的數據
void HeapPop(Heap* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->arr[0], &php->arr[php->size - 1]);
php->size--;
AdjustDown(php->arr, php->size, 0);
}
//獲取堆頂數據
HeapDataType HeapTop(Heap* php)
{
assert(php);
assert(php->size > 0);
return php->arr[0];
}感謝各位的閱讀！關于“C++怎么實現二叉樹及堆”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
