在上篇文章數(shù)據(jù)結(jié)構(gòu)6——樹與二叉樹中，我們了解了樹和二叉樹的概念，接著上篇文章，在本篇文章中我們學(xué)習(xí)二叉樹順序結(jié)構(gòu)的實現(xiàn)。

---

---

目錄

1. 二叉樹的順序存儲結(jié)構(gòu)

2. 堆的概念及結(jié)構(gòu)

1. 堆的概念

2. 堆的結(jié)構(gòu)

3. 堆的實現(xiàn)

1. 堆節(jié)點

2. 交換節(jié)點

3. 打印

4. 堆的插入

向上調(diào)整：

插入：

5. 堆的刪除

向下調(diào)整：

刪除：

6. 初始化

7. 銷毀

驗證：

源代碼：

Heap.h:

Heap.c:

test.c:

---

1. 二叉樹的順序存儲結(jié)構(gòu)

二叉樹一般可以使用兩種結(jié)構(gòu)存儲，一種是順序結(jié)構(gòu)，一種是鏈式結(jié)構(gòu)。本篇文章我們先來研究二叉樹的順序存儲，下篇文章詳解二叉樹的鏈式存儲。

普通的二叉樹是不適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結(jié)構(gòu)存儲。現(xiàn)實中我們通常把堆(一種二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進程地址空間中的堆是兩回事，一個是數(shù)據(jù)結(jié)構(gòu)，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。

如圖： 完全二叉樹順序存儲：

非完全二叉樹順序存儲：

2. 堆的概念及結(jié)構(gòu)

1. 堆的概念

簡單來說，堆除了是一棵完全二叉樹之外，還要滿足堆序性。

堆中每個節(jié)點的值都大于等于其子節(jié)點的值，根節(jié)點是堆中最大的元素，這樣的堆稱為最大堆或大根堆；

相反的，堆中每個節(jié)點的值都小于等于其子節(jié)點的值，根節(jié)點是堆中最小的元素，這樣的堆稱為最小堆或小根堆；

2. 堆的結(jié)構(gòu)

3. 堆的實現(xiàn)

（本篇文章只實現(xiàn)最小堆，最大堆與最小堆是相同的道理）

1. 堆節(jié)點

typedef int HPDataType;
//堆的物理結(jié)構(gòu)與順序表相似
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

2. 交換節(jié)點

//交換
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

3. 打印

//打印
void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}

4. 堆的插入

可是現(xiàn)在堆屬性并不滿足，因為30在5的上面，這是一個最小堆，我們需要將小的數(shù)字在上面。

為了恢復(fù)堆屬性，我們需要交換30和5：

可是現(xiàn)在仍舊沒有滿足最小堆的堆屬性，所以還需要交換10和5：

此時才得到了最小堆。

因此在插入數(shù)據(jù)后每次都要進行向上調(diào)整，于是向上調(diào)整的實現(xiàn)為：

向上調(diào)整：

//向上調(diào)整
void AdjustUP(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}

插入：

//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//判斷是否需要擴容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL)//檢查是否擴容成功{perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUP(php->a, php->size - 1);//傳數(shù)組的最后一個數(shù)據(jù)
}

5. 堆的刪除

由于堆頂是最大或最小元素，為了滿足堆屬性，所以堆中每次只能刪除堆頂元素，一般的做法是先將堆頂元素與數(shù)組末尾元素先交換，再刪除末尾元素。

可是現(xiàn)在40在了堆頂，反而成了最大的元素，并不滿足最小堆，這時就需要向下調(diào)整：

每次刪除都要調(diào)整，所以向下調(diào)整的具體實現(xiàn)為：

向下調(diào)整：

//向下調(diào)整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//找出小的那個孩子if (child + 1 < n && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//繼續(xù)往下調(diào)整parent = child;child = parent * 2 + 1;}else{break;}}
}

刪除：

//刪除
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);--php->size;AdjustDown(php->a, php->size, 0);
}

6. 初始化

//初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

7. 銷毀

//銷毀
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

驗證：

int main()
{int a[] = { 9,3,7,10,24,14,28,72,21,5 };HP hp;HeapInit(&hp);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);}HeapPrint(&hp);HeapDestroy(&hp);return 0;
}

---

---

源代碼：

Heap.h:

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int HPDataType;
//堆的物理結(jié)構(gòu)與順序表相似
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//交換
void Swap(HPDataType* p1, HPDataType* p2);//打印
void HeapPrint(HP* php);//初始化
void HeapInit(HP* php);//向上調(diào)整
void AdjustUP(HPDataType* a, int child);
//插入
void HeapPush(HP* php, HPDataType x);//向下調(diào)整
void AdjustDown(HPDataType* a, int n, int parent);
//刪除
void HeapPop(HP* php);//銷毀
void HeapDestroy(HP* php);

Heap.c:

#include "Heap.h"//交換
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//打印
void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}//向上調(diào)整
void AdjustUP(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//判斷是否需要擴容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL)//檢查是否擴容成功{perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUP(php->a, php->size - 1);//傳數(shù)組的最后一個數(shù)據(jù)
}//向下調(diào)整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//找出小的那個孩子if (child + 1 < n && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//繼續(xù)往下調(diào)整parent = child;child = parent * 2 + 1;}else{break;}}
}//刪除
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);--php->size;AdjustDown(php->a, php->size, 0);
}//初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}//銷毀
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

test.c:

int main()
{int a[] = { 9,3,7,10,24,14,28,72,21,5 };HP hp;HeapInit(&hp);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);}HeapPrint(&hp);HeapDestroy(&hp);return 0;
}