二叉樹的順序結(jié)構(gòu)
普通的二叉樹是不適合用數(shù)組來存儲(chǔ)的，因?yàn)榭赡軙?huì)存在大量的空間浪費(fèi)。而完全二叉樹更適合使用順序結(jié)構(gòu)存儲(chǔ)。現(xiàn)實(shí)中我們通常把堆(一種二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲(chǔ)，需要注意的是這里的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事，一個(gè)是數(shù)據(jù)結(jié)構(gòu)，一個(gè)是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。
堆的概念及結(jié)構(gòu)
在這里我們先學(xué)習(xí)一下堆，堆是一種特殊的二叉樹形式
如果有一個(gè)關(guān)鍵碼的集合K = { N1，N2 ，N3 ，…， }，把它的所有元素按完全二叉樹的順序存儲(chǔ)方式存儲(chǔ)在一個(gè)一維數(shù)組中，并滿足： Ni<= N(2i+1)且 Ni<= N(2i+2)( Ni>= N(2i+1)且Ni >=N(2i+2) ) i = 0，1，2…，則稱為小堆(或大堆)。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。
堆的性質(zhì)：
★堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
★堆總是一棵完全二叉樹。
堆的實(shí)現(xiàn)
1、堆向下調(diào)整算法
現(xiàn)在我們給出一個(gè)數(shù)組，邏輯上看做一顆完全二叉樹。我們通過從根節(jié)點(diǎn)開始的向下調(diào)整算法可以把它調(diào)整成一個(gè)小堆。向下調(diào)整算法有一個(gè)前提：左右子樹必須是一個(gè)堆，才能調(diào)整。
int arr[] = {27,15,19,18,28,34,65,49,25,37};
后面在講到堆的插入接口函數(shù)時(shí)，還會(huì)提到向上調(diào)整算法
2、堆的創(chuàng)建
下面我們給出一個(gè)數(shù)組，這個(gè)數(shù)組邏輯上可以看做一顆完全二叉樹，但是還不是一個(gè)堆，現(xiàn)在我們通過算法，把它構(gòu)建成一個(gè)堆。根節(jié)點(diǎn)左右子樹不是堆，我們?cè)趺凑{(diào)整呢？這里我們從倒數(shù)的第一個(gè)非葉子節(jié)點(diǎn)的子樹開始調(diào)整，一直調(diào)整到根節(jié)點(diǎn)的樹，就可以調(diào)整成堆。
int a[] = {1,5,3,8,7,6};
此時(shí)調(diào)換1和8的位置時(shí)，8的左子樹堆結(jié)構(gòu)被破壞，所以在每一次發(fā)生元素交換的時(shí)候，都需要遞歸調(diào)用重新構(gòu)造堆的結(jié)構(gòu)
最后構(gòu)造的大堆：8，7，6，5，1，3
3、堆的插入
刪除堆是刪除堆頂?shù)臄?shù)據(jù)，將堆頂?shù)臄?shù)據(jù)根最后一個(gè)數(shù)據(jù)一換，然后刪除數(shù)組最后一個(gè)數(shù)據(jù)，再進(jìn)行向下調(diào)整算法。
★將堆頂元素和堆中最后一個(gè)元素進(jìn)行交換
★刪除最后一個(gè)元素
★將堆頂?shù)脑叵蛳抡{(diào)整，直到滿足堆特性為止
4、堆的實(shí)現(xiàn)
這里堆的實(shí)現(xiàn)我們使用的是順序表結(jié)構(gòu)
堆的結(jié)構(gòu)體及接口定義
// 大堆
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void AdjustUp(int* a, int child);//向上調(diào)整
void AdjustDown(int* a, int n, int parent);//向下調(diào)整
void Swap(HPDataType* px, HPDataType* py);//交換函數(shù)
void HeapInit(HP* hp);//堆的初始化
void HeapDestroy(HP* hp);// 堆的銷毀
void HeapPush(HP* hp, HPDataType x);// 堆的插入
void HeapPop(HP* hp);// 堆的刪除
HPDataType HeapTop(HP* hp);// 取堆頂?shù)臄?shù)據(jù)
void HeapPrint(HP* hp);//堆的打印
bool HeapEmpty(HP* hp);// 堆的判空
int HeapSize(HP* hp);// 堆的數(shù)據(jù)個(gè)數(shù)
堆的接口實(shí)現(xiàn)
交換函數(shù)(Swap)
代碼如下：
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}
這里的交換函數(shù)不是接口函數(shù)，僅為了方便其他接口函數(shù)調(diào)用
向上調(diào)整(AdjustUp)
代碼如下：
void AdjustUp(int* a, int child)
{
assert(a);
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;
}
}
}
這里的向上調(diào)整函數(shù)就是指定一個(gè)元素與其父親比較，如果孩子小于父親，就交換
常用于小堆的插入與堆排序。
向下調(diào)整(AdjustDown)
代碼如下：
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
// 選出左右孩子中小的那一個(gè)
if (child + 1 < n && a[child + 1] < a[child])
{
++child;
}
// 如果小的孩子小于父親，則交換，并繼續(xù)向下調(diào)整
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
這里的向下調(diào)整函數(shù)就是指定一個(gè)元素與其父親比較，如果孩子小于父親，就交換
同樣常用于小堆的插入與堆排序，和向上調(diào)整的不同的就是方向。
堆的初始化(HeapInit)
代碼如下：
void HeapInit(HP* hp)
{
assert(hp);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
堆的銷毀(HeapDestroy)
代碼如下：
void HeapDestroy(HP* hp)
{
assert(hp);
free(hp->a);
hp->capacity = hp->size = 0;
}
堆的插入(HeapPush)
代碼如下：
void HeapPush(HP* hp, HPDataType x)
{
assert(hp);
if (hp->size == hp->capacity)
{
size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HPDataType* tmp = realloc(hp->a, sizeof(HPDataType)*newCapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
hp->a = tmp;
hp->capacity = newCapacity;
}
hp->a[hp->size] = x;
hp->size++;
AdjustUp(hp->a, hp->size - 1);
}
堆的插入，首先創(chuàng)建內(nèi)存空間，然后插入元素，size++就不說了；
重點(diǎn)講一下這里的向上調(diào)整，因?yàn)槭切?shù)往上調(diào)，所以這里的調(diào)用是用于小堆的建立；
如果要改成大堆，那么就要將向上調(diào)整函數(shù)的判斷改為大于；
修改后代碼如下：
if (a[child] > a[parent])
堆的刪除(HeapPop)
代碼如下：
void HeapPop(HP* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
Swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;
AdjustDown(hp->a, hp->size, 0);
}
堆的刪除是刪除堆頂?shù)脑兀切枰⒁獾氖遣⒉皇侵苯訉⒍秧斣刂苯觿h除
而是將堆頂元素和最后一個(gè)元素交換，再進(jìn)行size–
再將換上去的最后的元素重新向下調(diào)整到相應(yīng)位置
這樣做的目的是為了保持堆的基本結(jié)構(gòu)，否則可能堆結(jié)構(gòu)可能不成立。
取堆頂?shù)臄?shù)據(jù)(HeapTop)
代碼如下：
HPDataType HeapTop(HP* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
return hp->a[0];
}
直接返回第一個(gè)元素即可
堆的打印(HeapPrint)
代碼如下：
void HeapPrint(HP* hp)
{
for (int i = 0; i < hp->size; ++i)
{
printf("%d ", hp->a[i]);
}
printf("\n");
}
常用的for循環(huán)對(duì)順序表進(jìn)行元素遍歷逐個(gè)打印
堆的判空(HeapEmpty)
代碼如下：
bool HeapEmpty(HP* hp)
{
assert(hp);
return hp->size == 0;
}
這里使用的是bool值，當(dāng)然你也可以使用int類型
堆的數(shù)據(jù)個(gè)數(shù)(HeapSize)
代碼如下：
int HeapSize(HP* hp)
{
assert(hp);
return hp->size;
}
堆排序的簡(jiǎn)易例子
代碼如下：
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
for (int end = n - 1; end > 0; --end)
{
Swap(&a[end], &a[0]);
AdjustDown(a, end, 0);
}
}
int main()
{
int a[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 };
HeapSort(a, sizeof(a) / sizeof(a[0]));
for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
這里我們主要使用向下調(diào)整的方法來實(shí)現(xiàn)，因?yàn)樯厦鎸?duì)堆的刪除是用于小堆
所以這里調(diào)用向下調(diào)整后，該數(shù)組為降序，排序后打印如下：
75 70 69 56 50 33 30 25 15 10
如果要進(jìn)行升序排序，我們只需將向下調(diào)整函數(shù)的部分符號(hào)修改即可
修改如下：
void AdjustDown(int* 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]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
排序后打印如下：文章來源：http://www.zghlxwxcb.cn/news/detail-418078.html
10 15 25 30 33 50 56 69 70 75
結(jié)語
有興趣的小伙伴可以關(guān)注作者，如果覺得內(nèi)容不錯(cuò)，請(qǐng)給個(gè)一鍵三連吧，蟹蟹你喲?。。?br> 制作不易，如有不正之處敬請(qǐng)指出
感謝大家的來訪，UU們的觀看是我堅(jiān)持下去的動(dòng)力
在時(shí)間的催化劑下，讓我們彼此都成為更優(yōu)秀的人吧?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-418078.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)入門（C語言版）二叉樹的順序結(jié)構(gòu)及堆的概念及結(jié)構(gòu)實(shí)現(xiàn)應(yīng)用的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
