C++實現二叉樹及堆的示例代碼

1 樹

樹是一種非線性數據結構,它是由n個有限結點組成的具有層次關系的集合。把它叫樹是因為它是根朝上,葉子朝下的
來上圖瞧瞧

在這裡插入圖片描述

1.1 樹的相關名詞

在這裡插入圖片描述

2 二叉樹

2.1 二叉樹的概念

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

在這裡插入圖片描述

二叉樹有以下特點:

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

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。

2.3 特殊的二叉樹

1、滿二叉樹:一個二叉樹,如果每一層的結點數都達到瞭最大,如果這個二叉樹的層次是k,則其結點數是2^k-1。
2、完全二叉樹:用最直白的話來說就是,樹的深度或者高度為k,前k-1層的結點都是滿的,隻有最後的第k層不滿但是從左到右的結點必須是連續的。
其實滿二叉樹是一種特殊的完全二叉樹。
如圖所示:

在這裡插入圖片描述

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

3 堆

3.1 堆的概念

普通的二叉樹是不適合用數組來存儲的,因為可能會存在大量的空間浪費,而完全二叉樹更適合用順序存儲,順序存儲的隨機訪問特性,會右巨大的優點。我們通常把堆(是一種完全二叉樹)采用順序存儲,需要註意的是這裡的堆和操作系統虛擬進程地址空間中的堆是兩回事,一個是數據結構一個是OS中管理內存的一塊區域分段。
堆分為大根堆和小根堆。
大根堆:父親結點>=孩子結點
小根堆:父親結點<=孩子結點

在這裡插入圖片描述

上面是堆的邏輯結構,下面是物理結構

3.2 堆的實現

首先構建堆我們要瞭解一個算法,叫向下調整算法。我們以小根堆為例,我們把圖示的完全二叉樹構建為小堆,這個二叉樹有個條件是根結點的兩個子樹都是小堆才可以進行向下調整算法。

在這裡插入圖片描述

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繼續向下調整
		//把次小(次大)的元素也選出來,直到剩最後一個,堆排序完成
		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繼續向下調整
		//把次小(次大)的元素也選出來,直到剩最後一個,堆排序完成
		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++實現二叉樹及堆的示例代碼的文章就介紹到這瞭,更多相關C++實現二叉樹及堆內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!