【數據結構】樹二叉樹的概念以及堆的詳解

這篇具有很好參考價值的文章主要介紹了【數據結構】樹二叉樹的概念以及堆的詳解。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

?? 往期相關文章

?鏈接1：【數據結構】順序表
?鏈接2：【數據結構】單鏈表
?鏈接3：【數據結構】雙向帶頭循環(huán)鏈表
?鏈接4：【數據結構】棧和隊列

?? 樹的概念

百度百科的解釋：樹是一種非線性的數據結構，它是由n(n≥0)個有限節(jié)點組成一個具有層次關系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

有一個特殊的結點，稱為根節(jié)點(root)，根結點沒有前驅結點。
除根節(jié)點外，其余結點被分成 $M (M > 0)$ 個互不相交的集合，其中每一個集合又是一顆結構與樹類似的子樹，每顆子樹的根結點有且僅有一個前驅結點，可以有0個或者多個后繼結點。

注意： 樹型結構中，子樹之間不能有交集，否則就不是樹型結構。

【數據結構】樹二叉樹的概念以及堆的詳解,數據結構和算法,數據結構,學習,堆

節(jié)點的度： 一個節(jié)點含有的子樹的個數稱為該節(jié)點的度。如上圖：A的度為6
葉子節(jié)點或終端節(jié)點： 度為0的節(jié)點稱為葉子節(jié)點。如上圖：B、C、H、I、P、O、K…等節(jié)點都是葉子節(jié)點
非終端結點或分支結點： 度不為0的節(jié)點
父節(jié)點： 若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點
子節(jié)點： 一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點。如上圖：B是A的子節(jié)點
兄弟節(jié)點： 具有相同父節(jié)點的節(jié)點互稱兄弟節(jié)點
樹的度： 一棵樹中，最大節(jié)點的度稱為樹的度
樹的高度或深度： 如上圖：樹的高度為4
堂兄弟節(jié)點： 父節(jié)點在同一層的節(jié)點互為堂兄弟
祖先節(jié)點： 從根到該節(jié)點所經分支上的所有結點都叫做該結點的祖先結點（父節(jié)點也是祖先節(jié)點）
子孫節(jié)點： 以某節(jié)點為根的子樹中任一節(jié)點都成為該節(jié)點的子孫
森林： 又多棵樹且互不相交的結合稱為森林

?? 二叉樹的概念

以上樹的概念都適用于二叉樹，但是二叉樹在樹的基礎上添加了一些條件。

二叉樹不存在度大于2的節(jié)點
二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

【數據結構】樹二叉樹的概念以及堆的詳解,數據結構和算法,數據結構,學習,堆

?? 特殊的二叉樹

滿二叉樹： 一個二叉樹，如果每一層的節(jié)點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為 $k$ ，且節(jié)點總數是 $2^k - 1$ ，則就是滿二叉樹。
完全二叉樹： 一個二叉樹，假設樹的深度是 $k$ ，前 $k ? 1$ 層節(jié)點是滿的，最后一層節(jié)點從左到右連續(xù)且最少有一個，當最后一層也是滿的話，這樣應該被稱為滿二叉樹。完全二叉樹是一種效率很高的數據結構。注意：滿二叉樹是一種特殊的完全二叉樹。

【數據結構】樹二叉樹的概念以及堆的詳解,數據結構和算法,數據結構,學習,堆

?? 二叉樹的性質

若規(guī)定根節(jié)點的層數為1，則一顆非空二叉樹的第 $h$ 層上最多有 $2^{(h-1)}$ 個節(jié)點。
若規(guī)定根節(jié)點的層數為1，則深度為 $h$ 的二叉樹的最大節(jié)點數是 $2^h - 1$ 。
對于任意一顆二叉樹，如果度為 $0$ 也就是其葉子節(jié)點個數為 $x_0$ ，度為 $2$ 的分支節(jié)點個數為 $x_2$ ，則有 $x_0 = x_2 + 1$ 或 $x_2 = x_0 - 1$ 。
若規(guī)定根節(jié)點的層數為1，具有 $n$ 個節(jié)點的滿二叉樹的深度， $h = log_2(n+ 1)$
對于具有 $n$ 個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有節(jié)點從0開始。則對于序號為 $i$ 的節(jié)點有：
- 若 $i > 0$ ， $i$ 位置節(jié)點的父節(jié)點序號： $(i ? 1) /2$ 。 $i = 0$ ，根節(jié)點無父節(jié)點。
- 若 $2 ? i < n$ 左孩子下標： $2 ? i + 1 。$ ????( $n$ 為數組長度)
- 若 $2 ? i < n$ 右孩子下標： $2 ? i + 2 。$ ????( $n$ 為數組長度)

?? 堆的概念

百度百科的解釋：堆(Heap)是計算機科學中一類特殊的數據結構，是最高效的優(yōu)先級隊列。堆通常是一個可以被看作一棵完全二叉樹的數組對象。

堆中某個結點的值總是不大于或不小于其父結點的值。
堆總是一棵完全二叉樹。

小根堆： 每一個父節(jié)點的值總是小于等于子節(jié)點。
大根堆： 每一個父節(jié)點的值總是大于等于子節(jié)點。

注： 堆在物理存儲結構上數組的形式，在邏輯結構上是二叉樹。

【數據結構】樹二叉樹的概念以及堆的詳解,數據結構和算法,數據結構,學習,堆

?? 堆的核心算法 (向上調整算法與向下調整算法)

AdjustUp 實現思路：向上調整算法通常在堆 push 的時候使用向上調整算法來繼續(xù)維護當前是一個堆的結構。當堆添加數據的時候，如果是小根堆要滿足父節(jié)點的數據要小于等于子節(jié)點的數據，大根堆同理。其實堆在 push 數據的時候，不會影響到兄弟節(jié)點，只會影響到其父節(jié)點，所以通過二叉樹的性質來計算出父節(jié)點在與當前子節(jié)點比較，若子節(jié)點小于父節(jié)點則交換。

AdjustUp 實現(小根堆為例)：

// 向上調整
void AdjustUp(HeapDataType* data, int child) {
	assert(data);

	// 計算父節(jié)點位置
	int parentNode = (child - 1) / 2;
	while (child > 0) {
		if (data[child] < data[parentNode]) {
			// 交換
			Swap(&data[child] , &data[parentNode]);

			// 繼續(xù)向上搜索
			child = parentNode;
			parentNode = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

AdjustDown 實現思路：向下調整算法通常在 pop 堆頂數據后來繼續(xù)維護當前是一個堆的結構，這里采用了一個很巧妙的方法把堆頂元素與最后一個下標元素進行交換，而堆在物理上又是一個順序表只需要 --size 即可刪除最后一個元素，在通過向下調整算法也就是將下標為 0 的元素 ( parent節(jié)點 ) 和左右孩子中較小的那個進行比較，若較小的孩子要小于當前的 parent 節(jié)點，則交換。

AdjustUp 實現(小根堆為例)：

void AdjustDown(HeapDataType* data, int size, int parent) {
	assert(data);

	// 默認左孩子最小
	int child = parent * 2 + 1;
	while (child < size) {
		// 判斷左孩子和右孩子誰更小
		// 若右孩子小則改變child 右孩子不能越界
		if ( (child + 1 < size) && (data[child + 1] < data[child]) ) {
			child++;
		}

		// 最小的孩子是否比父節(jié)點小
		if (data[child] < data[parent]) {
			// 交換
			Swap(&data[child] , &data[parent]);
			// 迭代
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			// 父節(jié)點 <= 最小的孩子節(jié)點
			break;
		}
	}
}

?? 堆的實現

堆的結構定義與接口

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int HeapDataType;
// 邏輯結構 完全二叉樹
// 內存結構 順序表
typedef struct Heap {
	HeapDataType* data;
	int size;
	int capacity;
}Heap;

void AdjustDown(HeapDataType* data, int size, int parent);
void AdjustUp(HeapDataType* data, int child);
void HeapPrint(Heap* hp);
void Swap(HeapDataType* value1 , HeapDataType* value2);
void HeapInit(Heap * hp);
void HeapDestroy(Heap * hp);
void HeapPush(Heap * hp , HeapDataType value);
void HeapPop(Heap * hp);
HeapDataType HeapTop(Heap * hp);
bool HeapIsEmpty(Heap* hp);
int HeapSize(Heap * hp);

HeapInit 實現：

void HeapInit(Heap* hp) {
	assert(hp);

	hp->data = NULL;
	hp->size = 0;
	hp->capacity = 0;
}

HeapDestroy 實現：

void HeapDestroy(Heap* hp) {
	assert(hp);
	free(hp->data);
	hp->capacity = hp->size = 0;
}

HeapPrint 實現：

void HeapPrint(Heap* hp) {
	assert(hp);

	for (int i = 0; i < hp->size; i++) {
		printf("%d " , hp->data[i]);
	}
	printf("\n");
}

HeapPush 實現：

void HeapPush(Heap* hp, HeapDataType value) {
	assert(hp);

	// 檢查容量
	if (hp->size == hp->capacity) {
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HeapDataType* newData = (HeapDataType*)realloc(hp->data , sizeof(HeapDataType) * newCapacity);
		assert(newData);
		hp->data = newData;
		hp->capacity = newCapacity;
	}

	hp->data[hp->size] = value;
	hp->size++;

	// 向上調整
	AdjustUp(hp->data , hp->size - 1);
}

HeapPop 實現：

// 刪除堆頂的數據 堆頂選數小堆最小數
void HeapPop(Heap* hp) {
	assert(hp);

	// 堆不為空
	assert(!HeapIsEmpty(hp));

	// 交換
	Swap(&hp->data[0] , &hp->data[hp->size - 1]);
	hp->size--;

	// 向下調整
	AdjustDown(hp->data , hp->size , 0);
}

HeapTop 實現：

HeapDataType HeapTop(Heap* hp) {
	assert(hp);

	// 堆不為空
	assert(!HeapIsEmpty(hp));

	return hp->data[0];
}

HeapIsEmpty 實現：

bool HeapIsEmpty(Heap* hp) {
	assert(hp);

	return hp->size == 0;
}

HeapSize 實現：

int HeapSize(Heap* hp) {
	assert(hp);

	return hp->size;
}

Swap 實現：

void Swap(HeapDataType* value1, HeapDataType* value2) {
	assert(value1 && value2);

	HeapDataType temp = *value1;
	*value1 = *value2;
	*value2 = temp;
}