前言

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

一、什么是樹(Tree):

1.樹的基本概念：

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

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

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

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

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

我們再來了解一些基本名詞概念：

3.樹的表示方法：

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

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

二、二叉樹：

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

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

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

從上圖可以看出：

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

注意：對于任意的二叉樹都是由以下幾種情況復合而成的：

2.特殊的二叉樹類型：

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

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

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

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

二叉樹一般可以使用兩種結(jié)構(gòu)存儲，一種順序結(jié)構(gòu)，一種鏈式結(jié)構(gòu)。

• 順序存儲：順序結(jié)構(gòu)存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲，二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。

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

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

5.二叉樹的遍歷：

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

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

1. 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之前。
2. 中序遍歷(InorderTraversal)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之中間。
3. 后序遍歷(PostorderTraversal)——訪問根結(jié)點的操作發(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)：

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

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

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

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

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

• 堆的創(chuàng)建：

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

代碼演示：

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)//返回堆中元素個數(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è)計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。

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

void HeapSort(int* arr, int sz)
{
	int end1 = (sz - 1 - 1) / 2;//求最后一個節(jié)點的父節(jié)點，這個父節(jié)點即最后一個非葉子節(jié)點
	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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！