C++怎么實現(xiàn)二叉樹及堆

這篇文章給大家分享的是有關(guān)C++怎么實現(xiàn)二叉樹及堆的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

1 樹

樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，它是由n個有限結(jié)點組成的具有層次關(guān)系的集合。把它叫樹是因為它是根朝上，葉子朝下的
來上圖瞧瞧

1.1 樹的相關(guān)名詞

2 二叉樹

2.1 二叉樹的概念

一顆二叉樹是結(jié)點的一個有限集合，該集合或者為空，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹。
如圖所示：

二叉樹有以下特點：

1、每個二叉樹最多有兩顆子樹，所以二叉樹不存在度為2的結(jié)點。
2、二叉樹的子樹有左右之分，其子樹的順序不能顛倒。

2.2 二叉樹的性質(zhì)

1、若規(guī)定根結(jié)點的層數(shù)為第一層，則一顆非空二叉樹的第i層上最多有z^(k-1)個結(jié)點
2、若規(guī)定根結(jié)點的層數(shù)為第一層，則深度為h的二叉樹的最大結(jié)點數(shù)是2^k-1個。
3、對于任何一顆二叉樹，度為0的結(jié)點（葉子結(jié)點）的個數(shù)為n0 ,度為2的結(jié)點個數(shù)為n2則一定有，n0 = n2 + 1。
4、若規(guī)定根結(jié)點的層數(shù)為第一層,具有N個結(jié)點的滿二叉樹的深度h = log2(N+1)[說明：以2為底的N+1的對數(shù)]，這個可以由性質(zhì)2推導(dǎo)得到。
5、對于具有n個結(jié)點的完全二叉樹，如果按照從上到下從左到右的數(shù)組順序?qū)λ薪Y(jié)點從0開始編號，即對于數(shù)組下標(biāo)i的結(jié)點有：
1）i>1,i位置的父結(jié)點的在數(shù)組中的下標(biāo)為（i-1）/2.
2)i位置結(jié)點的左孩子結(jié)點的下標(biāo)為2i+1,右結(jié)點下標(biāo)為2i+2。

2.3 特殊的二叉樹

1、滿二叉樹：一個二叉樹，如果每一層的結(jié)點數(shù)都達(dá)到了最大，如果這個二叉樹的層次是k，則其結(jié)點數(shù)是2^k-1。
2、完全二叉樹：用最直白的話來說就是，樹的深度或者高度為k，前k-1層的結(jié)點都是滿的，只有最后的第k層不滿但是從左到右的結(jié)點必須是連續(xù)的。
其實滿二叉樹是一種特殊的完全二叉樹。
如圖所示：

圖為完全二叉樹，要是最后一層全滿則為滿二叉樹。
滿足：
2^k-1-x = N;
x的取值范圍是[0,2^(k-1)-1]

3 堆

3.1 堆的概念

普通的二叉樹是不適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費，而完全二叉樹更適合用順序存儲，順序存儲的隨機(jī)訪問特性，會右巨大的優(yōu)點。我們通常把堆（是一種完全二叉樹）采用順序存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事，一個是數(shù)據(jù)結(jié)構(gòu)一個是OS中管理內(nèi)存的一塊區(qū)域分段。
堆分為大根堆和小根堆。
大根堆：父親結(jié)點>=孩子結(jié)點
小根堆：父親結(jié)點<=孩子結(jié)點

上面是堆的邏輯結(jié)構(gòu)，下面是物理結(jié)構(gòu)

3.2 堆的實現(xiàn)

首先構(gòu)建堆我們要了解一個算法，叫向下調(diào)整算法。我們以小根堆為例，我們把圖示的完全二叉樹構(gòu)建為小堆，這個二叉樹有個條件是根結(jié)點的兩個子樹都是小堆才可以進(jìn)行向下調(diào)整算法。

3.2.1 向下調(diào)整算法

根結(jié)點的左右子樹都是小堆，根結(jié)點27和左右子樹的根結(jié)點較小的那一個交換位置，然后依次進(jìn)行，直到葉子結(jié)點。就把最小的15結(jié)點上浮到堆頂?shù)奈恢?。這個算法的前提是根節(jié)點的左右子樹都是小堆，如果我們想把任意的的數(shù)組構(gòu)建成小堆顯然不滿足條件。在下面我們介紹把任意數(shù)組構(gòu)建成小堆的辦法。
向下調(diào)整算法的代碼如下：

void AdjustDown(HeapDataType* a, int n, int root)
{
	//父子下標(biāo)的初始化
	int parent = root;
	int child = parent * 2 + 1;
	//循環(huán)向下調(diào)整，把最小值（或者最大值浮到堆頂）
	while (child < n)
	{
		//選出左右孩子中較小的孩子，作為child，child+1 < n保證下標(biāo)不能越界
		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;//當(dāng)孩子 >= 父親的時候，滿足小堆的條件，跳出循環(huán)節(jié)課，否則就會死循環(huán)
		}
	}
}

3.2.2 堆的構(gòu)建

把給定的數(shù)據(jù)化成完全二叉樹的邏輯結(jié)構(gòu)如上圖所示，這個數(shù)組（二叉樹）顯然不能滿足向下調(diào)整算法的理想條件，所以我們把問題拆分，比如你先思考下這個問題，把左子樹和右子樹全部構(gòu)建成小堆不就滿足條件了嘛，但是子樹的左右子不是小堆怎么辦呢，那么同樣的道理，把它也構(gòu)建成子樹就可以了，那么我們可以從葉子結(jié)點向上每個結(jié)點都執(zhí)行一邊向下調(diào)整算法不就可以了嘛。其實我們不必從葉子結(jié)點開始因為葉子結(jié)點沒有子樹其實都可以看成是小堆或者大堆。所以從第一個非葉子結(jié)點開始調(diào)整即可。

也就是從圖中紫色圈圈畫出來的那個開始調(diào)整即可，直到根結(jié)點93，就會把一個數(shù)組構(gòu)建成小堆（大堆）。

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

（n-1-1）/2為第一非葉子結(jié)點下標(biāo)。

3.2.3 堆排序

有了上面的知識做鋪墊，堆排序就可以很好的理解了。
1、把數(shù)組構(gòu)建成大堆或者小堆，位于堆頂?shù)臄?shù)據(jù)就是最大值或者最小值，把堆頂數(shù)據(jù)和最后的結(jié)點位置的數(shù)據(jù)（數(shù)組元素最后一個）互換。然后對前n-1個結(jié)點重新向下調(diào)整為大堆或者小堆。直到剩下最后一個根節(jié)點就排序完成。
只是要升序：構(gòu)建大堆，要降序：構(gòu)建小堆，你細(xì)細(xì)品。
代碼如下：

//堆排序
void HeapSort(int* a, int n)
{
	//堆排序的第一步就是構(gòu)建堆,構(gòu)建堆的時間復(fù)雜度是O(n),此時是小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//如果是升序，構(gòu)建大堆
	//如果是降序，構(gòu)建小堆
	//是反著的，因為要和最后一個進(jìn)行交換
	int end = n - 1;
	while (end>0)
	{
		//把堆頂（最小或者最大）和最后的的元素交換，然后從0到n-2繼續(xù)向下調(diào)整
		//把次?。ù未螅┑脑匾策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;

//堆的初始化，內(nèi)部有堆的創(chuàng)建
void HeapInit(Heap* php, HeapDataType* a, int n);
//堆的銷毀
void HeapDestory(Heap* php);
//堆的插入數(shù)據(jù)
void HeapPush(Heap* php, HeapDataType x);
//堆的刪除數(shù)據(jù)
void HeapPop(Heap* php);
//獲取堆頂數(shù)據(jù)
HeapDataType HeapTop(Heap* php);
//對傳入的數(shù)組內(nèi)的數(shù)據(jù)進(jìn)行堆排序
void HeapSort(int* a, int n);

定義：

#include "Heap.h"
//堆是一種完全二叉樹，用順序存儲（數(shù)組）比較好
//用于交換兩個數(shù)據(jù)
void Swap(HeapDataType* n1, HeapDataType* n2)
{
	HeapDataType temp = *n1;
	*n1 = *n2;
	*n2 = temp;
}
//向下調(diào)整算法___老重要了，這是理解堆排序和topk問題以及堆這里相關(guān)題的基礎(chǔ)
//向下調(diào)整結(jié)束的情況有兩個一個是a[parent]<a[child],另一個是從堆頂?shù)綌?shù)組結(jié)束全部比較完
void AdjustDown(HeapDataType* a, int n, int root)
{
	//父子下標(biāo)的初始化
	int parent = root;
	int child = parent * 2 + 1;
	//循環(huán)向下調(diào)整，把最小值（或者最大值浮到堆頂）
	while (child < n)
	{
		//選出左右孩子中較小的孩子，作為child，child+1 < n保證下標(biāo)不能越界
		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;//當(dāng)孩子 >= 父親的時候，滿足小堆的條件，跳出循環(huán)節(jié)課，否則就會死循環(huán)
		}
	}
}
//向上調(diào)整算法
//用在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;
		}
	}
}
//堆的初始化，內(nèi)部有堆的創(chuàng)建
void HeapInit(Heap* php, HeapDataType* a, int n)
{
	HeapDataType* temp = (HeapDataType*)malloc(sizeof(HeapDataType)*n);
	if (temp)
	{
		php->arr = temp;
		
	}
	else
	{
		printf("內(nèi)存申請失??！");
		exit(-1);
	}
	//將傳進(jìn)來的數(shù)組拷貝給malloc出來的空間，用來后續(xù)的堆的創(chuàng)建，刪除，插入數(shù)據(jù)等操作
	memcpy(php->arr, a, sizeof(HeapDataType)*n);
	php->size = n;
	php->capacity = n;

	//把拷貝進(jìn)來的數(shù)組，構(gòu)建成堆
	//從倒數(shù)第一個非葉子節(jié)點進(jìn)行構(gòu)建(直接把數(shù)組畫成一個完全二叉樹可以直接由圖得到第一個
	//非葉子節(jié)點的下標(biāo)）
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->arr, php->size, i);
	}
}
//堆排序
void HeapSort(int* a, int n)
{
	//堆排序的第一步就是構(gòu)建堆,構(gòu)建堆的時間復(fù)雜度是O(n),此時是小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//如果是升序，構(gòu)建大堆
	//如果是降序，構(gòu)建小堆
	//是反著的，因為要和最后一個進(jìn)行交換
	int end = n - 1;
	while (end>0)
	{
		//把堆頂（最小或者最大）和最后的的元素交換，然后從0到n-2繼續(xù)向下調(diào)整
		//把次小（次大）的元素也選出來，直到剩最后一個，堆排序完成
		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;
}

//堆的插入數(shù)據(jù)
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("擴(kuò)容失??！\n");
			exit(-1);
		}
	}
	php->arr[php->size++] = x;
	AdjustUp(php->arr, php->size, php->size - 1);
}

//堆的刪除數(shù)據(jù),要刪除堆頂?shù)臄?shù)據(jù)
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);
}

//獲取堆頂數(shù)據(jù)
HeapDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	return php->arr[0];
}

感謝各位的閱讀！關(guān)于“C++怎么實現(xiàn)二叉樹及堆”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！