前言

樹形結(jié)構(gòu)指的是數(shù)據(jù)元素之間存在著“一對(duì)多”的樹形關(guān)系的數(shù)據(jù)結(jié)構(gòu)，是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，本篇重點(diǎn)講解它。

一、什么是樹(Tree):

1.樹的基本概念：

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的。

我們先來看一張圖來試著了解樹形結(jié)構(gòu)：

我們可以看到，每個(gè)結(jié)點(diǎn)不斷往下有一個(gè)或多個(gè)結(jié)點(diǎn)，就像樹的樹枝一樣，樹形結(jié)構(gòu)像是倒過來的樹。

• 有一個(gè)特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)
• 除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M>0)個(gè)互不相交的集合T1、T2、……、Tm，其中每一個(gè)集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼
• 因此，樹是遞歸定義的。

2.樹的相關(guān)概念：

我們?cè)賮砹私庖恍┗久~概念：

3.樹的表示方法：

樹結(jié)構(gòu)相對(duì)線性表就比較復(fù)雜了，要存儲(chǔ)表示起來就比較麻煩了，既要保存值域，也要保存結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系，實(shí)際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。我們這里就簡單的了解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; //第一個(gè)孩子結(jié)點(diǎn)
 struct Node* _pNextBrother; //指向其下一個(gè)兄弟結(jié)點(diǎn)
 DataType _data; //結(jié)點(diǎn)中的數(shù)據(jù)域
};

二、二叉樹：

1.基本概念及結(jié)構(gòu)：

一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合:

• 由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成
• 或者為空

從上圖可以看出：

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

注意：對(duì)于任意的二叉樹都是由以下幾種情況復(fù)合而成的：

2.特殊的二叉樹類型：

1. 滿二叉樹：一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。也就是說，如果一個(gè)二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是 ，則它就是滿二叉樹。
2. 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。

3.二叉樹的性質(zhì)：

1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i-1)個(gè)結(jié)點(diǎn).
2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是2^h - 1.
3. 對(duì)任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為n0, 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為n2,則有 n0＝n2＋1
4. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h= log2(n+1). (ps： log2(n+1)是log以2為底，n+1為對(duì)數(shù))
5. 對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開始編號(hào)，則對(duì)于序號(hào)為i的結(jié)點(diǎn)有：
   • 1.若i>0，i位置節(jié)點(diǎn)的雙親序號(hào)：(i-1)/2；i=0，無雙親節(jié)點(diǎn)
     2. 若2i+1<n，左孩子序號(hào)：2i+1，2i+1>=n否則無左孩子
     3. 若2i+2<n，右孩子序號(hào)：2i+2，2i+2>=n否則無右孩子

4.二叉樹的存儲(chǔ)結(jié)構(gòu)：

二叉樹一般可以使用兩種結(jié)構(gòu)存儲(chǔ)，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。

• 順序存儲(chǔ)：順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來存儲(chǔ)，一般使用數(shù)組只適合表示完全二叉樹，因?yàn)椴皇峭耆鏄鋾?huì)有空間的浪費(fèi)。而現(xiàn)實(shí)中使用中只有堆才會(huì)使用數(shù)組來存儲(chǔ)，二叉樹順序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一顆二叉樹。

• 鏈?zhǔn)酱鎯?chǔ)：二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)的左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址，鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中一般都是二叉鏈。

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
 struct BinTreeNode* _pLeft; //指向當(dāng)前節(jié)點(diǎn)左孩子
 struct BinTreeNode* _pRight; //指向當(dāng)前節(jié)點(diǎn)右孩子
 BTDataType _data; //當(dāng)前節(jié)點(diǎn)值域
}
// 三叉鏈
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; //指向當(dāng)前節(jié)點(diǎn)的雙親
 struct BinTreeNode* _pLeft; //指向當(dāng)前節(jié)點(diǎn)左孩子
 struct BinTreeNode* _pRight; //指向當(dāng)前節(jié)點(diǎn)右孩子
 BTDataType _data; //當(dāng)前節(jié)點(diǎn)值域
}；

5.二叉樹的遍歷：

學(xué)習(xí)二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對(duì)二叉樹中的節(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個(gè)節(jié)點(diǎn)只操作一次。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)。

按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷：

1. 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。
2. 中序遍歷(InorderTraversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中間。
3. 后序遍歷(PostorderTraversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。

void PreOrder(BTNode* root)//前序遍歷
{
	if (root == NULL)
	{
		printf("# ");//為空打印#
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
void InOrder(BTNode* root)//中序遍歷
{
	if (root == NULL)
	{
		printf("# ");//為空打印#
		return;
	}
	InOrder(root->left);
	printf("%d", root->data);
	InOrder(root->right);
}
void PostOrder(BTNode* root)//后序遍歷
{
	if (root == NULL)
	{
		printf("# ");//為空打印#
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

三、堆：

1.基本概念及結(jié)構(gòu)：

如果有一個(gè)集合它的所有元素按完全二叉樹的順序存儲(chǔ)方式存儲(chǔ)在一個(gè)一維數(shù)組中，并滿足： 每個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值； 將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。 堆的性質(zhì)：

• 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
• 堆總是一棵完全二叉樹

2.堆的實(shí)現(xiàn)：

• 向下調(diào)整算法：

我們可以把一個(gè)數(shù)組從邏輯上看做一顆完全二叉樹。我們通過從根節(jié)點(diǎn)開始的向下調(diào)整算法可以把它調(diào)整成一個(gè)小堆。向下調(diào)整算法有一個(gè)前提：左右子樹必須是一個(gè)堆，才能調(diào)整。

• 堆的創(chuàng)建：

我們可以把一個(gè)數(shù)組從邏輯上看做一顆完全二叉樹，葉子節(jié)點(diǎn)可以看為是一個(gè)堆，所以從最后一個(gè)非葉子節(jié)點(diǎn)開始依次向前進(jìn)行向下調(diào)整算法既可創(chuàng)建一個(gè)堆。

代碼演示：

void HeapInit(Heap* ph)//堆的初始化
{
	assert(ph);
	ph->arr = NULL;
	ph->capacity = ph->size = 0;
}
void HeapDestroy(Heap* ph)//堆的銷毀
{
	assert(ph);
	free(ph->arr);
	ph->arr = NULL;
	ph->size = ph->capacity = 0;
}
void Swap(HeapDataType* child, HeapDataType* parent)//交換堆數(shù)組內(nèi)容
{
	HeapDataType tmp = *child;
	*child = *parent;
	*parent = tmp;
}
void AdjustUp(int* arr, int child)//向上調(diào)整函數(shù)
{
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (arr[parent] > arr[child])
		{
			Swap(&arr[child], &arr[parent]);//交換堆數(shù)組內(nèi)容
			child = parent;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* ph, HeapDataType x)//插入數(shù)據(jù)
{
	assert(ph);
	if (ph->capacity == ph->size)
	{
		int newcapacity = ph->capacity = 0 ? 4 : ph->capacity * 2;
		HeapDataType* tmp = (HeapDataType*)realloc(ph->arr, sizeof(HeapDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc");
			exit(-1);
		}
		ph->arr = tmp;
		ph->capacity = newcapacity;
	}
	ph->arr[ph->size] = x;
	ph->size++;
	AdjustUp(ph->arr, ph->size - 1);//向上調(diào)整函數(shù)
}
void AdjustDown(HeapDataType* arr, int size, int parent)//向下調(diào)整函數(shù)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPop(Heap* ph)//堆的刪除
{
	assert(ph);
	assert(!HeapEmpty(ph));
	Swap(&ph->arr[0], &ph->arr[ph->size - 1]);
	ph->size--;
	AdjustDown(ph->arr, ph->size, 0);//向下調(diào)整函數(shù)
}
HeapDataType HeapTop(Heap* ph)//返回堆頂元素
{
	assert(ph);
	assert(!HeapEmpty(ph));
	return ph->arr[0];
}
bool HeapEmpty(Heap* ph)//堆的判空
{
	assert(ph);
	return ph->size == 0;
}
int HeapSize(Heap* ph)//返回堆中元素個(gè)數(shù)
{
	assert(ph);
	return ph->size;
}
void HeapPrint(Heap* ph)//打印堆中數(shù)據(jù)
{
	assert(ph);
	assert(!HeapEmpty(ph));
	for (int i = 0; i < ph->size; i++)
	{
		printf("%d ", ph->arr[i]);
	}
	printf("\n");
}

• 堆排序：

堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。它是通過堆來進(jìn)行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。

原理：例如排升序建大堆，即堆頂元素為序列最大值，例如堆尾元素下標(biāo)為end，將堆頂元素與堆尾元素交換讓最大值到堆尾，然后end-1，再向下調(diào)整繼續(xù)交換，以此類推，最后end=0排序結(jié)束

void HeapSort(int* arr, int sz)
{
	int end1 = (sz - 1 - 1) / 2;//求最后一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，這個(gè)父節(jié)點(diǎn)即最后一個(gè)非葉子節(jié)點(diǎn)
	for (int i = end1; i >= 0; i--)
	{
		AdjustDown(arr, sz, i);
	}
	//開始排序
	//升序 -- 用大堆
	//降序 -- 用小堆
	int end2 = sz - 1;
	while (end2 > 0)
	{
		Swap(&arr[0], &arr[end2]);
		AdjustDown(arr, end2, 0);
		end2--;
	}
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}

到此這篇關(guān)于C語言中的二叉樹和堆詳解的文章就介紹到這了,更多相關(guān)二叉樹和堆內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論