＜數(shù)據(jù)結(jié)構(gòu) ＞ w字拿捏鏈?zhǔn)蕉鏄?- Toy模板網(wǎng)

這篇具有很好參考價(jià)值的文章主要介紹了＜數(shù)據(jù)結(jié)構(gòu) ＞ w字拿捏鏈?zhǔn)蕉鏄?。希望?duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

1、為何使用鏈?zhǔn)蕉鏄?/p>

2、何為鏈?zhǔn)蕉鏄?/p>

3、基本接口

????????創(chuàng)建二叉鏈結(jié)構(gòu)

????????手動(dòng)構(gòu)建一顆樹

4、二叉樹的遍歷

????????前序遍歷

????????中序遍歷

????????后續(xù)遍歷

????????層序遍歷

5、經(jīng)典問題

????????結(jié)點(diǎn)個(gè)數(shù)

????????葉結(jié)點(diǎn)個(gè)數(shù)

????????第K層結(jié)點(diǎn)個(gè)數(shù)

????????二叉樹的深度

????????二叉樹查找值為x的節(jié)點(diǎn)

????????二叉樹的銷毀

????????判斷二叉樹是否是完全二叉樹

6、總代碼

1、為何使用鏈?zhǔn)蕉鏄?/h4>

在前幾篇博文中，我們學(xué)習(xí)的都是完全二叉樹或滿二叉樹，而這兩個(gè)都是可以用數(shù)組來實(shí)現(xiàn)的，但是如果不是完全二叉樹呢？回顧下曾經(jīng)學(xué)過的知識(shí)點(diǎn)：

?由上圖得知，普通二叉樹也可以使用數(shù)組來存儲(chǔ)，但是會(huì)存在大量的空間浪費(fèi)，而完全二叉樹就不會(huì)這樣，因?yàn)槠淇臻g利用率是％100的。既然這樣，那普通二叉樹該如何進(jìn)行存儲(chǔ)呢？答案是使用鏈?zhǔn)浇Y(jié)構(gòu)進(jìn)行存儲(chǔ)。

2、何為鏈?zhǔn)蕉鏄?/h4>

?鏈?zhǔn)浇Y(jié)構(gòu)分為兩種：二叉鏈和三叉鏈

先看下代碼結(jié)構(gòu)：
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)值域
};
畫圖演示：

注意：

鏈?zhǔn)蕉鏄浜臀覀冎暗膶W(xué)習(xí)略有差別。以前我們學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)無非就是增刪查改這些東西，而鏈?zhǔn)蕉鏄洳惶P(guān)注這塊的增刪查改。因?yàn)槠胀ǘ鏄涞脑鰟h查改沒有意義。如下的二叉樹：

鏈?zhǔn)蕉鏄涫且戎版湵砩兜母訌?fù)雜的，如果只是單純的讓鏈?zhǔn)蕉鏄浯鎯?chǔ)數(shù)據(jù)的話，價(jià)值就不大了，不如使用線性表。接下來，我將通過其遍歷方式，結(jié)點(diǎn)個(gè)數(shù)……為大家展開討論。此節(jié)內(nèi)容是為了后續(xù)學(xué)習(xí)更復(fù)雜的搜索二叉樹打基礎(chǔ)，具體是啥后面再談。

在具體講解之前，再回顧下二叉樹，二叉樹是：

空樹

非空：根節(jié)點(diǎn)，根節(jié)點(diǎn)的左子樹、根節(jié)點(diǎn)的右子樹組成的。

從概念中可以看出，二叉樹定義是遞歸式的，因此后序基本操作中基本都是按照該概念實(shí)現(xiàn)的。

3、基本接口

????????創(chuàng)建二叉鏈結(jié)構(gòu)

創(chuàng)建二叉鏈結(jié)構(gòu)其實(shí)就很easy了，也就是創(chuàng)建一個(gè)結(jié)構(gòu)體罷了，這種在先前已經(jīng)寫過很多，咱就是說直接上代碼：
//創(chuàng)建二叉鏈結(jié)構(gòu)
typedef int BTDataType; //本文以int整型為例
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	int data;
}BTNode;

????????手動(dòng)構(gòu)建一顆樹

思路：

其實(shí)構(gòu)建一棵樹的思想還是挺簡(jiǎn)單的，按照?qǐng)D示創(chuàng)建6個(gè)節(jié)點(diǎn)，并根據(jù)圖中的樣子將節(jié)點(diǎn)順次鏈接起來

代碼演示：

//創(chuàng)建二叉鏈結(jié)構(gòu)
typedef int BTDataType; //本文以int整型為例
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	int data;
}BTNode;
//創(chuàng)建結(jié)點(diǎn)
BTNode* BuyBTNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}
//構(gòu)建樹
BTNode* CreatBinaryTree()
{
	//創(chuàng)建6個(gè)結(jié)點(diǎn)
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);
	//將結(jié)點(diǎn)連接起來，構(gòu)成自己想要的樹
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	//返回根結(jié)點(diǎn)
	return node1;
}
int main()
{
	BTNode* tree = CreatBinaryTree();
	return 0;
}

4、二叉樹的遍歷

?以一顆二叉樹為例：

后續(xù)的遍歷均是建立在次二叉樹基礎(chǔ)上展開。?

????????前序遍歷

?遍歷規(guī)則：

前序遍歷，也叫先根遍歷

遍歷順序：根 -> 左子樹 -> 右子樹

思路：

既然先從根走，根就是1，接下來訪問1的左子樹，此時(shí)又要先訪問其左子樹的根為2，接著再訪問2的左子樹->根：3，接著訪問其左子樹和右子樹，不過均為空，遞歸返回，此時(shí)3作為2的左子樹訪問完畢，訪問2的右子樹為NULL，再遞歸返回此時(shí)1的左子樹就訪問完畢了，訪問其右子樹，同理訪問左樹4，再訪問左樹5，接著左右子樹NULL，遞歸返回訪問4的右樹，……類似的

圖示：

?代碼演示：

前序遍歷的代碼非常簡(jiǎn)潔，短短幾行即可操作，先看代碼：
//前序遍歷
void PrevOrder(BTNode*root)
{
	if (root == NULL)
	{
		printf("NULL  "); //如果為空，就打印空
		return;
	}
	printf("%d  ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
效果如下：

跟我們先前畫的圖一模一樣，讓我們通過一副遞歸圖來深刻理解其原理：

遞歸圖：

????????中序遍歷

?遍歷規(guī)則：

中序遍歷，也叫中根遍歷

遍歷順序：左子樹?-> 根結(jié)點(diǎn) -> 右子樹

思路：

根據(jù)遍歷順序，我們得知，如若想訪問1，得先訪問其左子樹2，訪問2還得先訪問其左子樹3，類似的，再訪問其左子樹為NULL，遞歸返回訪問根結(jié)點(diǎn)3，再訪問右子樹NULL，遞歸返回訪問根結(jié)點(diǎn)2，再訪問右子樹NULL，遞歸返回訪問根結(jié)點(diǎn)1，再訪問其右子樹，1的右子樹訪問規(guī)律同1的左子樹，這里不過多贅述。

畫圖演示：

?代碼演示：

中序遍歷的代碼和前序遍歷一樣，看起來都非常簡(jiǎn)潔：
//中序遍歷
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL  "); //如果為空，就打印空
		return;
	}
	InOrder(root->left);
	printf("%d  ", root->data);
	InOrder(root->right);
}
效果如下：

單純看代碼看不出啥頭緒，還得是畫遞歸圖。

遞歸圖：

????????后續(xù)遍歷

?遍歷規(guī)則：

后續(xù)遍歷，也叫后根遍歷

遍歷順序：左子樹 -> 右子樹 -> 根結(jié)點(diǎn)

思路：

要訪問1得先訪問1的左子樹2，繼而得先訪問2的左子樹3，再先訪問3的左子樹NULL，右子樹NULL，根3，遞歸返回訪問2的右子樹NULL，根2，再遞歸返回訪問1的右子樹……類似的

畫圖演示：

代碼演示：

后續(xù)的代碼也非常簡(jiǎn)單，有了前文前序遍歷和中序遍歷的基礎(chǔ)，后續(xù)遍歷只需要把打印放后面即可，代碼如下：
//后序遍歷
void PosOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL  "); //如果為空，就打印空
		return;
	}
	PosOrder(root->left);
	PosOrder(root->right);
	printf("%d  ", root->data);
}
效果如下：

畫圖演示遞歸過程：

????????層序遍歷

?遍歷規(guī)則：

層序遍歷聽名字就很直白，直接一層一層按順序遍歷唄。

我這里直接給出答案：1、2、4、3、5、6

思路：

細(xì)心的童鞋可能已經(jīng)發(fā)現(xiàn)，先前的遍歷思想都是通過遞歸來完成的，而層序的遍歷則是通過隊(duì)列來實(shí)現(xiàn)的。

首先，把根節(jié)點(diǎn)1的結(jié)點(diǎn)指針先入隊(duì)列，隊(duì)列此時(shí)不為空，出隊(duì)頭的數(shù)據(jù)，把隊(duì)頭數(shù)據(jù)的孩子2的結(jié)點(diǎn)指針和4的結(jié)點(diǎn)指針入進(jìn)去，隊(duì)列不為空，出2，入孩子3，隊(duì)列不為空，再出4，把孩子5和6入進(jìn)去，然后再出，沒有孩子繼續(xù)出，出到最后隊(duì)列為空?？偨Y(jié)如下兩句話：

先把根入隊(duì)列，借助隊(duì)列性質(zhì)：先進(jìn)先出

上一層的節(jié)點(diǎn)出的時(shí)候，帶下一層的節(jié)點(diǎn)進(jìn)去

圖示：

代碼演示：
//層序遍歷
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root); //先把根結(jié)點(diǎn)入進(jìn)去
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q); //取隊(duì)頭
		QueuePop(&q); //出隊(duì)頭
		printf("%d ", front->data); //打印隊(duì)頭數(shù)據(jù)
		if (front->left)
		{
			QueuePush(&q, front->left); //front左孩子不為空，就入
		}
		if (front->right)
		{
			QueuePush(&q, front->right);//front右孩子不為空，就入
		}
	}
	printf("\n");
	QueueDestory(&q);
}
效果如下：

5、經(jīng)典問題

????????結(jié)點(diǎn)個(gè)數(shù)

?思想：

求結(jié)點(diǎn)個(gè)數(shù)，這里我將提供如下幾種方法，但不都是可行的，要對(duì)比著看，本質(zhì)都是遞歸的思想：

法一：遍歷

在前文中，我們已經(jīng)學(xué)習(xí)了如何遍歷鏈?zhǔn)蕉鏄?，現(xiàn)在想求結(jié)點(diǎn)的個(gè)數(shù)，那么只需要隨便采用一種遍歷方式，并把打印換成計(jì)數(shù)++來求個(gè)數(shù)即可，聽起來非常容易，先看代碼：
//節(jié)點(diǎn)個(gè)數(shù)
void BTreeSize(BTNode* root)
{
	int count = 0; //局部變量
	if (root == NULL) //如果為空
		return;
	++count;
	BTreeSize(root->left);
	BTreeSize(root->right);
}
難道上述代碼能夠準(zhǔn)確求出結(jié)點(diǎn)個(gè)數(shù)嗎？其實(shí)不然，根本求不出來。

具體解釋起來需要借用棧幀的思想，因?yàn)檫@里用的是遞歸，而遞歸是每遞歸一次在棧幀里頭都會(huì)開辟一塊空間，每一塊棧幀都會(huì)有一個(gè)count，而我希望的是只需要有一個(gè)count，然后所有的count均加在一起，可是現(xiàn)在每遞歸一次，重新開辟一個(gè)count，count即局部變量。遞歸完就銷毀，同形參的改變不會(huì)影響實(shí)參一樣，一個(gè)道理。所有此法根本就行不通，得換。

法二：定義局部靜態(tài)變量count

在法一中，我們定義的是局部變量count，會(huì)導(dǎo)致每遞歸一次就開辟棧幀，并創(chuàng)建count，每次遞歸結(jié)束返回就銷毀棧幀。那如果可以把count放在靜態(tài)區(qū)里頭，不久可以保留住count嗎
//節(jié)點(diǎn)個(gè)數(shù)
int BTreeSize(BTNode* root)
{
	static int count = 0; //局部靜態(tài)變量
	if (root == NULL) //如果為空
		return count;
	++count;
	BTreeSize(root->left);
	BTreeSize(root->right);
	return count;
}
效果如下：

看似好像是成功了，確實(shí)結(jié)點(diǎn)個(gè)數(shù)為6，但真的就是成功了嗎？當(dāng)然不是，如果我們現(xiàn)在想多打印幾次呢？

什么鬼？怎么size還呈現(xiàn)等差數(shù)列遞增呢？就是因?yàn)檫@里運(yùn)用了static關(guān)鍵字，將count扣在靜態(tài)區(qū)，導(dǎo)致多次調(diào)用沒辦法初始化為0，使其每次遞歸調(diào)用累計(jì)加加，但是當(dāng)你再重新調(diào)用自己時(shí)，count不會(huì)重新置為0，會(huì)依舊保留為曾經(jīng)++的結(jié)果。局部的靜態(tài)變量有一個(gè)好處，它的生命周期在全局，但是只能在局部去訪問。它的初始化為0只有第一次調(diào)用會(huì)訪問，其余均不會(huì)。由此可見，局部的靜態(tài)也是不行的，還得再優(yōu)化。

法三：定義全局變量count

法二的局部靜態(tài)變量行不通，那就把count設(shè)定為全局變量。要知道全局變量是存在靜態(tài)區(qū)的。雖然也在靜態(tài)區(qū)，但是其初始化為0是可以重復(fù)訪問的。
//節(jié)點(diǎn)個(gè)數(shù)
int count = 0;
void BTreeSize(BTNode* root)
{
	if (root == NULL) //如果為空
		return;
	++count;
	BTreeSize(root->left);
	BTreeSize(root->right);
}
效果如下：

確實(shí)可以求出結(jié)點(diǎn)個(gè)數(shù)，并且也不會(huì)出現(xiàn)像法二一樣的問題。但是其實(shí)定義全局變量也會(huì)存在一個(gè)小問題：線程安全的問題，這個(gè)等以后學(xué)到Linux再來討論，我們這邊考慮再換一種更優(yōu)解。

法四：最優(yōu)解

我們這里可以考慮多套一層，可以考慮把變量的地址傳過去。這樣操作不會(huì)存在任何問題，上代碼：
//節(jié)點(diǎn)個(gè)數(shù)
void BTreeSize(BTNode* root, int* pCount)
{
	if (root == NULL) //如果為空
		return;
	++(*pCount);
	BTreeSize(root->left, pCount);
	BTreeSize(root->right, pCount);
}
法五：新思路

直接利用子問題的思想來寫，返回當(dāng)root為空為0，不是就遞歸左樹+右樹+1。

空樹，最小規(guī)模子問題，結(jié)點(diǎn)個(gè)數(shù)返回0

非空，左子樹結(jié)點(diǎn)個(gè)數(shù)+右子樹結(jié)點(diǎn)個(gè)數(shù) + 1（自己）
int BTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 
    BTreeSize(root->left) + 
    BTreeSize(root->right) + 1;
}
此法非常巧妙，很靈活的運(yùn)用了遞歸的思想，我們通過遞歸圖來深刻理解下：

遞歸圖：

?總結(jié)：

上述算法思想其實(shí)就是分治思想。

把復(fù)雜的問題分成更小規(guī)模的子問題，子問題再分成更小規(guī)模的子問題……直到子問題不可再分割，直接能出結(jié)果。

此思想純純是在套娃。接下來的多個(gè)問題都將會(huì)用到分治思想。

????????葉結(jié)點(diǎn)個(gè)數(shù)

?思路1：遍歷+計(jì)數(shù)

在遍歷的基礎(chǔ)上如果結(jié)點(diǎn)的左右子樹均為空則count++。但是此題我們依舊采用分治思想。

思路2：分治思想

首先，如果為空，直接返回0，如若結(jié)點(diǎn)的左子樹和右子樹均為空，則為葉節(jié)點(diǎn)，此時(shí)返回1，其它的繼續(xù)分治遞歸。

代碼演示：
//葉結(jié)點(diǎn)個(gè)數(shù)
int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0; //為空，返回0
	if (root->left == NULL && root->right == NULL)
		return 1; //如果左右子樹均為空，則為葉結(jié)點(diǎn)，返回1
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right); //繼續(xù)分治遞歸
}
遞歸圖：

????????第K層結(jié)點(diǎn)個(gè)數(shù)

?思路：

假設(shè)K=3

空樹，返回0

非空，且K == 1，返回1

非空，且K>1，轉(zhuǎn)換成左子樹K-1層節(jié)點(diǎn)個(gè)數(shù) + 右子樹K-1層節(jié)點(diǎn)個(gè)數(shù)

代碼演示：
//第K層節(jié)點(diǎn)個(gè)數(shù),K>=1
int BTreeKLevelSize(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTreeKLevelSize(root->left, k - 1) + BTreeKLevelSize(root->right, k - 1);
}
遞歸圖：

????????二叉樹的深度

?思路：

此題同樣是運(yùn)用分治的思想來解決，要比較左子樹的高度和右子樹的高度，大的那個(gè)就+1，因?yàn)檫€有根結(jié)點(diǎn)也算1個(gè)高度。

代碼演示：
//求樹的深度
int BTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftDepth = BTreeDepth(root->left); //左子樹高度
	int rightDepth = BTreeDepth(root->right);//右子樹高度
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
遞歸圖：

????????二叉樹查找值為x的節(jié)點(diǎn)

?思路：

還是利用分治的思想，將其遞歸化成子問題去解決

先去根結(jié)點(diǎn)尋找，是就返回此節(jié)點(diǎn)

此時(shí)去左子樹查找有無節(jié)點(diǎn)x

最后再去右子數(shù)去查找有無節(jié)點(diǎn)x

若左右子樹均找不到節(jié)點(diǎn)x，直接返回空

代碼演示：
//二叉樹查找值為x的節(jié)點(diǎn)
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	//如果根節(jié)點(diǎn)為空，直接返回空
	if (root == NULL)
		return NULL;
	//如果找到節(jié)點(diǎn)，直接返回節(jié)點(diǎn)位置
	if (root->data == x)
		return root;
	//若沒找到，去左子樹找
	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;
	//此時(shí)左子樹沒找到，去右子樹找
	BTNode* ret2 = BTreeFind(root->right, x);
	if (ret2)
		return ret2;
	//若左子樹和右子樹都每找到，直接返回空
	return NULL;
}

int main()
{
	BTNode* tree = CreatBinaryTree();
	for (int i = 0; i <= 7; i++)
	{
		printf("Find:%d,%p\n", i, BTreeFind(tree, i));
	}
	return 0;
}
效果如下：

遞歸圖：

假設(shè)我們尋找的是數(shù)字5

????????二叉樹的銷毀

?思路：

銷毀的思想和遍歷類似，如若我挨個(gè)遍歷的同時(shí)，沒遍歷一次就銷毀一次，豈不能達(dá)到效果，但是又會(huì)存在一個(gè)問題，那就是你要采用什么樣的遍歷方式？倘若你采用前序遍歷，剛開始就把根銷毀了，那么后面的子樹還怎么銷毀呢？因?yàn)榇藭r(shí)根沒了，子樹找不到了就，所以要采用倒著銷毀的規(guī)則，也就是后續(xù)的思想

代碼演示：
//二叉樹的銷毀
void BTreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeDestory(root->left);
	BTreeDestory(root->right);
	free(root);
	root = NULL;
}
思想和后續(xù)遍歷類似，不做遞歸圖演示。

????????判斷二叉樹是否是完全二叉樹

?在做提前，再來回顧下完全二叉樹的概念：前k-1層是滿的，最后一層是連續(xù)的。

來看一幅圖：

在這三幅圖中，很明顯肉眼得知第二幅和第三幅圖是完全二叉樹，只有第一幅不是，現(xiàn)在如何用代碼的方式表明出來呢？

思路：層序遍歷+變形?

通過上圖，不難發(fā)現(xiàn)，如果是完全二叉樹的話，在層序遍歷的時(shí)候是不會(huì)出現(xiàn)間隔的NULL。例如第一幅圖就不是完全二叉樹，因?yàn)閷有虮闅v到第三層的時(shí)候會(huì)出現(xiàn)間隔NULL，因?yàn)?span style="color:#956fe7;">3 -> NULL -> 5 -> 6，而剩余兩幅圖均不會(huì)出現(xiàn)這樣的問題，接下來，我將利用類似的思想解決這道題。

層序遍歷明確指出，當(dāng)其中一個(gè)結(jié)點(diǎn)pop出來時(shí)，要把它的孩子給push進(jìn)隊(duì)列里，但前提是把不為空的孩子給push進(jìn)去，現(xiàn)在規(guī)矩變了，不管你是否為空，都給push進(jìn)去，也就是說出一個(gè)結(jié)點(diǎn)，push兩個(gè)孩子結(jié)點(diǎn)，使其停止的條件是當(dāng)我pop出來的結(jié)點(diǎn)為NULL時(shí)，此時(shí)停止push，一直pop到隊(duì)列為空，如果全是空，就是完全二叉樹，如果有非空，就不是。

畫圖演示：

代碼演示：
//判斷一顆二叉樹是否是完全二叉樹
bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root); //根結(jié)點(diǎn)不為空，入隊(duì)列
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q); //刪除隊(duì)頭數(shù)據(jù)，方便后續(xù)取隊(duì)頭數(shù)據(jù)
		if (front == NULL) //如果取隊(duì)頭為空，停止，接下來進(jìn)入下一個(gè)while循環(huán)判斷是否為完全二叉樹
			break;
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q); 
		//如果空出到非空，那么說明不是完全二叉樹
		if (front)
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true; //全是空，此時(shí)返回true，為完全二叉樹
}
效果如下：

文章來源地址http://www.zghlxwxcb.cn/news/detail-663240.html

6、總代碼

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include"Queue.h"
//創(chuàng)建二叉鏈結(jié)構(gòu)
typedef int BTDataType; //本文以int整型為例
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	int data;
}BTNode;
//創(chuàng)建結(jié)點(diǎn)
BTNode* BuyBTNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}
//構(gòu)建樹
BTNode* CreatBinaryTree()
{
	//創(chuàng)建6個(gè)結(jié)點(diǎn)
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);
	//將結(jié)點(diǎn)連接起來，構(gòu)成自己想要的樹
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	//返回根結(jié)點(diǎn)
	return node1;
}

//前序遍歷
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL  "); //如果為空，就打印空
		return;
	}
	printf("%d  ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

//中序遍歷
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL  "); //如果為空，就打印空
		return;
	}
	InOrder(root->left);
	printf("%d  ", root->data);
	InOrder(root->right);
}

//后序遍歷
void PosOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL  "); //如果為空，就打印空
		return;
	}
	PosOrder(root->left);
	PosOrder(root->right);
	printf("%d  ", root->data);
}

/* 全局變量
節(jié)點(diǎn)個(gè)數(shù)
int count = 0;
void BTreeSize(BTNode* root)
{
	if (root == NULL) //如果為空
		return;
	++count;
	BTreeSize(root->left);
	BTreeSize(root->right);
}*/

/*節(jié)點(diǎn)個(gè)數(shù)
多套一層
void BTreeSize(BTNode* root, int* pCount)
{
	if (root == NULL) //如果為空
		return;
	++(*pCount);
	BTreeSize(root->left, pCount);
	BTreeSize(root->right, pCount);
}
*/
//結(jié)點(diǎn)個(gè)數(shù) -- > 子問題法
int BTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

//葉結(jié)點(diǎn)個(gè)數(shù)
int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0; //為空，返回0
	if (root->left == NULL && root->right == NULL)
		return 1; //如果左右子樹均為空，則為葉結(jié)點(diǎn)，返回1
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right); //繼續(xù)分治遞歸
}

//第K層節(jié)點(diǎn)個(gè)數(shù),K>=1
int BTreeKLevelSize(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTreeKLevelSize(root->left, k - 1) + BTreeKLevelSize(root->right, k - 1);
}

//求樹的深度
int BTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftDepth = BTreeDepth(root->left);
	int rightDepth = BTreeDepth(root->right);
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

//二叉樹查找值為x的節(jié)點(diǎn)
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	//如果根節(jié)點(diǎn)為空，直接返回空
	if (root == NULL)
		return NULL;
	//如果找到節(jié)點(diǎn)，直接返回節(jié)點(diǎn)位置
	if (root->data == x)
		return root;
	//若沒找到，去左子樹找
	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;
	//此時(shí)左子樹沒找到，去右子樹找
	BTNode* ret2 = BTreeFind(root->right, x);
	if (ret2)
		return ret2;
	//若左子樹和右子樹都每找到，直接返回空
	return NULL;
}

//二叉樹的銷毀
void BTreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeDestory(root->left);
	BTreeDestory(root->right);
	free(root);
	root = NULL;
}

//層序遍歷
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root); //先把根結(jié)點(diǎn)入進(jìn)去
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q); //取隊(duì)頭
		QueuePop(&q); //出隊(duì)頭
		printf("%d ", front->data); //打印隊(duì)頭數(shù)據(jù)
		if (front->left)
		{
			QueuePush(&q, front->left); //front左孩子不為空，就入
		}
		if (front->right)
		{
			QueuePush(&q, front->right);//front右孩子不為空，就入
		}
	}
	printf("\n");
	QueueDestory(&q);
}

//判斷一顆二叉樹是否是完全二叉樹
bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root); //根結(jié)點(diǎn)不為空，入隊(duì)列
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q); //刪除隊(duì)頭數(shù)據(jù)，方便后續(xù)取隊(duì)頭數(shù)據(jù)
		if (front == NULL) //如果取隊(duì)頭為空，停止，接下來進(jìn)入下一個(gè)while循環(huán)判斷是否為完全二叉樹
			break;
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q); 
		//如果空出到非空，那么說明不是完全二叉樹
		if (front)
			return false;
	}
	return true; //全是空，此時(shí)返回true，為完全二叉樹
}


int main()
{
	BTNode* tree = CreatBinaryTree();
	//PrevOrder(tree);
	//printf("\n");
	//InOrder(tree);
	//printf("\n");
	//PosOrder(tree);
	//printf("\n");
	//printf("size: %d", BTreeSize(tree));

	for (int i = 0; i <= 7; i++)
	{
		printf("Find:%d,%p\n", i, BTreeFind(tree, i));
	}
	LevelOrder(tree);
	printf("完全二叉樹:%d\n", BTreeComplete(tree));
	BTreeDestory(tree);
	tree = NULL;
	return 0;
}

到了這里，關(guān)于＜數(shù)據(jù)結(jié)構(gòu) ＞ w字拿捏鏈?zhǔn)蕉鏄涞奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！