數(shù)據(jù)結(jié)構(gòu)之鏈?zhǔn)蕉鏄湓斀?/h1>

 更新時(shí)間：2023年04月17日 10:05:49   作者：蛋超飯不要加蛋  

所謂二叉樹遍歷 (Traversal) 是按照某種特定的規(guī)則，依次對(duì)二叉樹中的節(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個(gè)節(jié)點(diǎn)只操作一次。本文通過代碼示例詳細(xì)介紹了C語(yǔ)言中的鏈?zhǔn)蕉鏄洌枰呐笥芽梢詤⒖家幌?/div>

目錄

• ??1.二叉樹的遍歷??
• 1.1前序遍歷
• 1.2中序遍歷
• 1.3后序遍歷
• 1.4層次遍歷
•  ??2.鏈?zhǔn)蕉鏄涞膶?shí)現(xiàn)??
• 2.1二叉樹的創(chuàng)建
• 2.2前序遍歷
• 2.3中序遍歷
• 2.4后序遍歷
• 2.5層序遍歷
• 2.6銷毀
• 2.7求節(jié)點(diǎn)個(gè)數(shù)
• 2.8求葉子節(jié)點(diǎn)個(gè)數(shù)
• 2.9求二叉樹的深度
• 2.10求第K層節(jié)點(diǎn)個(gè)數(shù)
• 2.11查找
• 2.12判斷是否為完全二叉樹

??1.二叉樹的遍歷??

所謂二叉樹遍歷 (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ī)則，二叉樹的遍歷分為： 前序遍歷、中序遍歷、后序遍歷的遞歸遍歷，層序遍歷的非遞歸遍歷下面將以下面的二叉樹為例講解四種遍歷

1.1前序遍歷

二叉樹的前序遍歷也叫先序遍歷，遍歷的順序?yàn)椋焊?、左子樹、右子樹，即遇到一棵樹，先訪問根節(jié)點(diǎn)，再訪問左子樹和右子樹，訪問左子樹和右子樹的過程又分為先訪問根節(jié)點(diǎn)，再訪問左子樹和右子樹，這是一個(gè)遞歸訪問的過程，因此前序遍歷屬于遞歸遍歷

遍歷的過程將以文字和圖片兩種方式展現(xiàn)

遍歷過程：

先遇到根節(jié)點(diǎn)1，訪問根節(jié)點(diǎn)1，再訪問1的左子樹

1的左子樹：遇到根節(jié)點(diǎn)2，訪問根節(jié)點(diǎn)2，再訪問2的左子樹，2的左子樹只有一個(gè)根節(jié)點(diǎn)3，3的左右子樹為空因此不需要訪問3的左右子樹，訪問根節(jié)點(diǎn)3便結(jié)束，2的左子樹遍歷結(jié)束訪問2的右子樹，2的右子樹為空即不用訪問，此時(shí)2的整顆樹遍歷結(jié)束，即1的左子樹遍歷結(jié)束，然后接著訪問1的右子樹

1的右子樹：遇到根節(jié)點(diǎn)4，訪問根節(jié)點(diǎn)4，再訪問4的左子樹，4的左子樹只有一個(gè)根節(jié)點(diǎn)5，5的左右子樹為空因此不需要訪問5的左右子樹，訪問根節(jié)點(diǎn)5便結(jié)束，4的左子樹遍歷結(jié)束訪問4的右子樹，4的右子樹只有一個(gè)根節(jié)點(diǎn)6，6的左右子樹為空因此不需要訪問6的左右子樹，訪問根節(jié)點(diǎn)6便結(jié)束，此時(shí)4的整顆樹遍歷結(jié)束，即1的右子樹遍歷結(jié)束

整棵樹遍歷完成，遍歷序列為：1 2 3 4 5 6

遍歷圖示：

1.2中序遍歷

二叉樹的中序遍歷也叫中根遍歷，遍歷的順序?yàn)椋鹤笞訕?、根、右?jié)點(diǎn)，即遇到一棵樹，先訪問它的左子樹，再訪問根，最后訪問右子樹，訪問左子樹和右子樹的過程又分為先訪問左子樹，再訪問根和右子樹，這是一個(gè)遞歸訪問的過程，因此中序遍歷也屬于遞歸遍歷

遍歷的過程將以文字和圖片兩種方式展現(xiàn)

遍歷過程：

遇到根節(jié)點(diǎn)1，先不訪問根節(jié)點(diǎn)，先訪問1的左子樹

1的左子樹：遇到根節(jié)點(diǎn)2，先不訪問根節(jié)點(diǎn)2，先訪問2的左子樹：2的左子樹只有一個(gè)根節(jié)點(diǎn)3，3的左右子樹為空因此不需要訪問3的左右子樹，訪問根節(jié)點(diǎn)3便結(jié)束，此時(shí)2的左子樹結(jié)束，訪問根節(jié)點(diǎn)2，然后訪問2的右子樹，2的右子樹為空則不訪問，此時(shí)2的整顆樹遍歷結(jié)束，即1的左子樹遍歷結(jié)束

訪問根節(jié)點(diǎn)1，接著訪問1的右子樹

1的右子樹：遇到根節(jié)點(diǎn)4，先不訪問根節(jié)點(diǎn)4，先訪問4的左子樹：遇到根節(jié)點(diǎn)5，5的左右子樹為空因此不需要訪問5的左右子樹，訪問根節(jié)點(diǎn)5便結(jié)束，此時(shí)4的左子樹訪問結(jié)束，訪問根節(jié)點(diǎn)4，接著訪問4的右子樹，4的右子樹只有一個(gè)根節(jié)點(diǎn)6，6的左右子樹為空因此不需要訪問6的左右子樹，訪問根節(jié)點(diǎn)6便結(jié)束，此時(shí)4的整棵樹訪問結(jié)束，即1的右子樹訪問結(jié)束

整棵樹遍歷完成，遍歷序列：3 2 1 5 4 6

 遍歷圖示：

1.3后序遍歷

二叉樹的后序遍歷也叫后根遍歷，遍歷的順序?yàn)椋鹤笞訕?、右子樹、根，即遇到一棵樹，先訪問它的左子樹，再訪問右子樹，最后訪問根，訪問左子樹和右子樹的過程又分為先訪問左子樹，再訪問右子樹和根，這是一個(gè)遞歸訪問的過程，因此后序遍歷也屬于遞歸遍歷

遍歷的過程將以文字和圖片兩種方式展現(xiàn)

遍歷過程：

遇到根節(jié)點(diǎn)1，先不訪問根節(jié)點(diǎn)1，先訪問左子樹

1的左子樹：遇到根節(jié)點(diǎn)2，先不訪問根節(jié)點(diǎn)2，先訪問2的左子樹：2的左子樹只有根節(jié)點(diǎn)3，3的左右子樹為空因此不需要訪問3的左右子樹，訪問根節(jié)點(diǎn)3便結(jié)束，此時(shí)2的左子樹訪問結(jié)束，接著訪問2的右子樹，2的右子樹為空因此不需要訪問，此時(shí)2的左右子樹訪問結(jié)束，最后訪問根節(jié)點(diǎn)2，此時(shí)2的整顆樹訪問結(jié)束，即1的左子樹訪問結(jié)束，接著訪問1的右子樹

1的右子樹：遇到根節(jié)點(diǎn)4，先不訪問根節(jié)點(diǎn)4，先訪問4的左子樹：5的左右子樹為空因此不需要訪問5的左右子樹，訪問根節(jié)點(diǎn)5便結(jié)束，此時(shí)4的左子樹訪問結(jié)束，接著訪問4的右子樹，6的左右子樹為空因此不需要訪問6的左右子樹，訪問根節(jié)點(diǎn)6便結(jié)束，此時(shí)4的左右子樹遍歷結(jié)束，最后訪問根節(jié)點(diǎn)4,4的整顆樹訪問結(jié)束，即1的右子樹訪問結(jié)束

最后訪問根節(jié)點(diǎn)1，整棵樹遍歷結(jié)束，遍歷序列：3 2 5 6 4 1

 遍歷圖示：

1.4層次遍歷

除了先序遍歷、中序遍歷、后序遍歷外，還可以對(duì)二叉樹進(jìn)行層序遍歷。設(shè)二叉樹的根節(jié)點(diǎn)所在層數(shù)為1， 層序遍歷就是從所在二叉樹的根節(jié)點(diǎn)出發(fā)，首先訪問第一層的樹根節(jié)點(diǎn)，然后從左到右訪問第 2 層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類推， 自上而下，自左至右逐層訪問樹的結(jié)點(diǎn)的過程就是層序遍歷。

遍歷圖示：

由上圖可以看出，層序遍歷為非遞歸遍歷

 ??2.鏈?zhǔn)蕉鏄涞膶?shí)現(xiàn)??

鏈?zhǔn)蕉鏄涞膶?shí)現(xiàn)包括二叉樹的創(chuàng)建、遍歷、銷毀、求節(jié)點(diǎn)個(gè)數(shù)、求葉子節(jié)點(diǎn)個(gè)數(shù)、求二叉樹的深度、求第k層節(jié)點(diǎn)個(gè)數(shù)、查找、判斷是否是完全二叉樹等

下面我們一一來(lái)實(shí)現(xiàn)這些接口

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

2.1二叉樹的創(chuàng)建

給定一個(gè)前序遍歷字符串，按照此字符串以指針方式構(gòu)建一顆二叉樹

給定字符串ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空樹

代碼設(shè)計(jì)思路：

函數(shù)參數(shù)為字符串指針和下標(biāo)指針，利用遞歸的思想，首先判斷是否遇到空格，遇到空格則跳過該空格即下標(biāo)加1并返回，接著構(gòu)建一個(gè)節(jié)點(diǎn)，當(dāng)前字符指針指向的字符賦值給節(jié)點(diǎn)的值域然后下標(biāo)加1，將字符指針和下標(biāo)傳參調(diào)用遞歸函數(shù)然后用節(jié)點(diǎn)的左指針接收。再將字符指針和下標(biāo)傳參調(diào)用遞歸函數(shù)然后用節(jié)點(diǎn)的右指針接收，最后返回節(jié)點(diǎn)指針

BTNode *TreeBuild(char *arr,int* i)
{
    if(arr[*i]=='#')//遇到空格則跳過該空格
    {
        (*i)++;
        return NULL;
    }
    // 建立節(jié)點(diǎn)
    BTNode *root=(BTNode *)malloc(sizeof(BTNode));
    //節(jié)點(diǎn)的值為當(dāng)前下標(biāo)指向的字符
    rot->data=arr[(*i)++];
    //調(diào)用遞歸，并用節(jié)點(diǎn)的左指針接收
    root->left=TreeBuild(arr,i);
    //調(diào)用遞歸，并用節(jié)點(diǎn)的左指針接收
    root->right=TreeBuild(arr,i);
    return root;
}

2.2前序遍歷

前序遍歷的過程在前面已經(jīng)介紹，我們按照過程設(shè)計(jì)相應(yīng)的函數(shù)

代碼設(shè)計(jì)思路：

利用遞歸的思想，首先判斷當(dāng)前節(jié)點(diǎn)是否為空，為空則直接返回，先打印當(dāng)前節(jié)點(diǎn)的值，再將自己的左子樹作為參數(shù)調(diào)用遞歸遍歷，最后將自己的右子樹作為參數(shù)調(diào)用遞歸遍歷

代碼：

void PreOrder(BTNode* root)
{
	if (root == NULL)//當(dāng)前節(jié)點(diǎn)為空則直接返回
		return NULL;
	printf("%d ", root->data);//打印當(dāng)前節(jié)點(diǎn)的值
	PreOrder(root->left);//遞歸遍歷左子樹
	PreOrder(root->right);//遞歸調(diào)用右子樹
}

2.3中序遍歷

中序遍歷的過程在前面已經(jīng)介紹，我們按照過程設(shè)計(jì)相應(yīng)的函數(shù)

代碼設(shè)計(jì)思路：

利用遞歸的思想，首先判斷當(dāng)前節(jié)點(diǎn)是否為空，為空則直接返回，先將自己的左子樹作為參數(shù)調(diào)用遞歸遍歷，再打印當(dāng)前節(jié)點(diǎn)的值，最后將自己的右子樹作為參數(shù)調(diào)用遞歸遍歷

代碼：

void InOrder(BTNode* root)
{
	if (root == NULL)//當(dāng)前節(jié)點(diǎn)為空則直接返回
		return NULL;
	InOrder(root->left);//遞歸遍歷左子樹
	printf("%d ", root->data);//打印當(dāng)前節(jié)點(diǎn)的值
	InOrder(root->right);//遞歸調(diào)用右子樹
}

2.4后序遍歷

后序遍歷的過程在前面已經(jīng)介紹，我們按照過程設(shè)計(jì)相應(yīng)的函數(shù)

代碼設(shè)計(jì)思路：

利用遞歸的思想，首先判斷當(dāng)前節(jié)點(diǎn)是否為空，為空則直接返回，先將自己的左子樹作為參數(shù)調(diào)用遞歸遍歷，再將自己的右子樹作為參數(shù)調(diào)用遞歸遍歷，最后打印當(dāng)前節(jié)點(diǎn)的值

void PostOrder(BTNode* root)
{
	if (root == NULL)//當(dāng)前節(jié)點(diǎn)為空則直接返回
		return NULL;
	PostOrder(root->left);//遞歸遍歷左子樹
	PostOrder(root->right);//遞歸調(diào)用右子樹
	printf("%d ", root->data);//打印當(dāng)前節(jié)點(diǎn)的值
}

2.5層序遍歷

層序遍歷的過程在前面已經(jīng)介紹，我們按照過程設(shè)計(jì)相應(yīng)的函數(shù)

代碼設(shè)計(jì)思路：

利用隊(duì)列，首先判斷當(dāng)前節(jié)點(diǎn)是否為空，為空則直接返回。把第一個(gè)節(jié)點(diǎn)的指針入隊(duì)，然后進(jìn)去循環(huán)（循環(huán)條件是隊(duì)列不為空），定義一個(gè)指針拿到隊(duì)列的第一個(gè)節(jié)點(diǎn)，然后出隊(duì)并打印節(jié)點(diǎn)的值，出隊(duì)之后將節(jié)點(diǎn)的左右孩子入隊(duì)，如果節(jié)點(diǎn)的左孩子存在，則將左孩子指針入隊(duì)，如果節(jié)點(diǎn)的右孩子存在，則將右孩子指針入隊(duì)，然后又繼續(xù)取隊(duì)頭元素打印，直到隊(duì)列為空

代碼：

void LevelOrder(BTNode *root)
{
	Queue q;//定義一個(gè)隊(duì)列
	QueueInit(&q);//隊(duì)列初始化
	if (root == NULL)//當(dāng)前節(jié)點(diǎn)為空則返回
		return;
	QueuePush(&q, root);//將第一個(gè)節(jié)點(diǎn)指針入隊(duì)
	while (!(QueueEmpty(&q)))//循環(huán)條件是隊(duì)列不為空，隊(duì)列為空則結(jié)束
	{
		BTNode* front = QueueFront(&q);//取隊(duì)頭節(jié)點(diǎn)
		printf("%d ", front->data);//打印節(jié)點(diǎn)的值
		QueuePop(&q);//出隊(duì)
		if (front->left)//左孩子存在，則將左孩子指針入隊(duì)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)//右孩子存在，則將右孩子指針入隊(duì)
		{
			QueuePush(&q, front->right);
		}
	}
	QueueDestroy(&q);//銷毀隊(duì)列
}

2.6銷毀

銷毀的過程：先從最后一層開始銷毀，先銷毀左子樹，再銷毀右子樹，最后銷毀根，即用到后序遍歷的思想，遞歸銷毀

代碼設(shè)計(jì)思路：

利用后序遍歷的思想，首先判斷當(dāng)前節(jié)點(diǎn)是否為空，為空則返回。先將左孩子指針作為參數(shù)調(diào)用遞歸，再將左孩子指針作為參數(shù)調(diào)用遞歸，最后將根節(jié)點(diǎn)釋放

代碼：

void BinaryTreeDestory(BTNode* root)
{
	if(root == NULL)//為空則返回
		return;
	BinaryTreeDestory(root->left);//遞歸銷毀左子樹
	BinaryTreeDestory(root->right);//遞歸銷毀右子樹
	free(root);//最后銷毀根節(jié)點(diǎn)
}

2.7求節(jié)點(diǎn)個(gè)數(shù)

一顆樹的節(jié)點(diǎn)個(gè)數(shù)可以分為左子樹的節(jié)點(diǎn)數(shù)加上右子樹的節(jié)點(diǎn)數(shù)再加1即根節(jié)點(diǎn)，同樣是遞歸求節(jié)點(diǎn)個(gè)數(shù)

代碼設(shè)計(jì)思路：

利用遞歸的思想，首先判斷當(dāng)前節(jié)點(diǎn)是否為空，為空則返回0，然后將左孩子指針作為參數(shù)調(diào)用遞歸，再將右孩子指針作為參數(shù)調(diào)用遞歸，最后將兩者的值加1返回，即節(jié)點(diǎn)個(gè)數(shù)等于左子樹的節(jié)點(diǎn)個(gè)數(shù)+右子樹的節(jié)點(diǎn)個(gè)數(shù)+1

 代碼：

int  TreeSize(BTNode* root)
{
	if (root == NULL)//當(dāng)前節(jié)點(diǎn)為空則返回0
		return 0;
	//遞歸左子樹和右子樹，然后將兩者的和加1返回
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

2.8求葉子節(jié)點(diǎn)個(gè)數(shù)

一顆樹的葉子節(jié)點(diǎn)個(gè)數(shù)可以分為左子樹的葉子節(jié)點(diǎn)個(gè)數(shù)+右子樹的葉子節(jié)點(diǎn)個(gè)數(shù)，即同樣利用遞歸求葉子節(jié)點(diǎn)個(gè)數(shù)

代碼設(shè)計(jì)思路：

利用遞歸的思想，首先判斷當(dāng)前節(jié)點(diǎn)是否為空，為空則返回0，然后判斷當(dāng)前節(jié)點(diǎn)是否為葉子結(jié)點(diǎn)，左孩子和右孩子都為空的節(jié)點(diǎn)即為葉子節(jié)點(diǎn)，為葉子節(jié)點(diǎn)則返回1，接著遞歸左子樹和右子樹，并返回兩者的和

代碼：

int TreeLeafSize(BTNode* root)
{
	if (root ==NULL)//當(dāng)前節(jié)點(diǎn)為空則返回0
		return 0;
	if (root->left == NULL && root->right == NULL)//當(dāng)前節(jié)點(diǎn)為葉子結(jié)點(diǎn)則返回1
		return 1;
	//遞歸左子樹和右子樹，并返回兩者的和
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

2.9求二叉樹的深度

一顆樹的深度等于左右子樹的較大的深度加1（加根節(jié)點(diǎn)），即利用遞歸求左右子樹的深度，將左右子樹較大的深度加1返回

代碼設(shè)計(jì)思路：

利用遞歸的思想，首先判斷當(dāng)前節(jié)點(diǎn)是否為空，為空則返回0，再判斷當(dāng)前節(jié)點(diǎn)是否為葉節(jié)點(diǎn)，是葉節(jié)點(diǎn)則返回1，接著遞歸左子樹和右子樹，取較大的深度加1返回

代碼：

int TreeHeight(BTNode* root)
{
	if (root == NULL)//當(dāng)前節(jié)點(diǎn)為空則返回空
		return 0;
	if (root->left == NULL && root->right == NULL)//當(dāng)前節(jié)點(diǎn)為葉節(jié)點(diǎn)則返回1
		return 1;
	int left = TreeHeight(root->left);//遞歸左子樹
	int right = TreeHeight(root->right);//遞歸右子樹
	return left > right ? left + 1 : right + 1;//將左右子樹較大的深度加1返回
}

2.10求第K層節(jié)點(diǎn)個(gè)數(shù)

整顆樹的第k層可以看成第二層的第k-1層，第三層的k-2層，第k層的第1層，即整棵樹的第k層的節(jié)點(diǎn)數(shù)等于左右子樹的第k-1層節(jié)點(diǎn)子樹，即利用遞歸求左右子樹的k-1層節(jié)點(diǎn)個(gè)數(shù)

代碼設(shè)計(jì)思路：

利用遞歸的思想，首先判斷當(dāng)前節(jié)點(diǎn)是否為空，為空則返回0，再判斷當(dāng)前層數(shù)是否為1，為1則返回1，然后遞歸左子樹，傳左子樹指針和k-1，然后遞歸右子樹，傳右子樹指針和k-1，最后返回兩者的和

代碼：

int TreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)//當(dāng)前節(jié)點(diǎn)為空則返回0
		return 0;
	if (k == 1)//當(dāng)前層數(shù)為1則返回1
		return 1;
	//遞歸左子樹和右子樹，返回兩者的值
	return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

2.11查找

查找值為x的節(jié)點(diǎn)，并返回節(jié)點(diǎn)的指針

代碼設(shè)計(jì)思路：

利用遞歸的思想，首先判斷當(dāng)前節(jié)點(diǎn)是否為空，為空則返回空，不為空則判斷當(dāng)前節(jié)點(diǎn)的值是否等于x，等于則返回該節(jié)點(diǎn)，然后遞歸查找左子樹，如果遞歸左子樹返回的值不為空說明找到則返回該值，接著遞歸右子樹，如果遞歸右子樹返回的值不為空說明找到則返回該值，遞歸左右子樹都未找到說明x不存在，返回空

代碼：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)//當(dāng)前節(jié)點(diǎn)為空則返回空
		return NULL;
	if (root->data == x)//當(dāng)前節(jié)點(diǎn)的值等于x則返回該節(jié)點(diǎn)
		return root;
	//遞歸左子樹查找
	BTNode* left = BinaryTreeFind(root->left,x);
	//返回的值不為空說明已找到，返回該值
	if (left)
		return left;
	//遞歸右子樹查找
	BTNode* right = BinaryTreeFind(root->right, x);
	//返回的值不為空說明已找到，返回該值
	if (right)
		return right;
	//遞歸左右子樹均為找到，則趕回空
	return NULL;
}

2.12判斷是否為完全二叉樹

上一篇文章介紹了完全二叉樹的概念，完全二叉樹可以看成是滿二叉樹以最后一層開始從右往左挖去了幾個(gè)節(jié)點(diǎn)而成，即完全二叉樹的倒數(shù)第二層是滿的，倒數(shù)第一層不可能存在只有右孩子而沒有左孩子的情況

代碼設(shè)計(jì)思路：

類似于層序遍歷的思想，利用隊(duì)列，首先判斷第一個(gè)節(jié)點(diǎn)是否為空，為空則返回，然后將第一個(gè)節(jié)點(diǎn)入隊(duì)，接著進(jìn)入循環(huán)（循環(huán)條件為隊(duì)列不為空），取隊(duì)頭元素并出隊(duì)，如果取到的隊(duì)頭元素為空，說明此時(shí)已經(jīng)此時(shí)二叉樹剛好遍歷結(jié)束，則退出循環(huán)檢查后面隊(duì)列值地情況如果是完全二叉樹，則隊(duì)列后面應(yīng)該都是空，如果存在不為空的元素則證明不是完全二叉樹。如果取到的隊(duì)頭元素不為空，則將其左右孩子（為空也一樣）入隊(duì)，如果循環(huán)正常結(jié)束，則證明是完全二叉樹

代碼：

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;//定義一個(gè)隊(duì)列
	QueueInit(&q);//隊(duì)列初始化
	if (root == NULL)//當(dāng)前節(jié)點(diǎn)為空則返回
		return;
	QueuePush(&q, root);//將第一個(gè)節(jié)點(diǎn)入隊(duì)
	while (!(QueueEmpty(&q)))
	{
		//取隊(duì)頭元素并出隊(duì)
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//取到的隊(duì)頭元素為空則退出循環(huán)，檢查隊(duì)列后面值地情況
		if (front==NULL)
		{
			break;
		}
		else//不為空則將左右孩子入隊(duì)
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	//檢查隊(duì)列后面的值的情況
	while (!(QueueEmpty(&q)))
	{
		BTNode* front = QueueFront(&q);//取隊(duì)頭元素并出隊(duì)
		QueuePop(&q);
		if (front != NULL)//如果有不為空的元素則證明不是完全二叉樹
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);//銷毀隊(duì)列
	return true;//循環(huán)正常結(jié)束則返回true
}

好啦，關(guān)于鏈?zhǔn)蕉鏄渚拖葘W(xué)到這里，如果對(duì)您有所幫助，歡迎一鍵三連~

到此這篇關(guān)于數(shù)據(jù)結(jié)構(gòu)之鏈?zhǔn)蕉鏄湓斀獾奈恼戮徒榻B到這了,更多相關(guān)C語(yǔ)言 鏈?zhǔn)蕉鏄鋬?nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

• C語(yǔ)言實(shí)現(xiàn)二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的示例詳解
• C語(yǔ)言詳解實(shí)現(xiàn)鏈?zhǔn)蕉鏄涞谋闅v與相關(guān)接口
• C語(yǔ)言 鏈?zhǔn)蕉鏄浣Y(jié)構(gòu)詳解原理
• C語(yǔ)言 二叉樹的鏈?zhǔn)酱鎯?chǔ)實(shí)例
• 探討:C++實(shí)現(xiàn)鏈?zhǔn)蕉鏄?用非遞歸方式先序,中序,后序遍歷二叉樹)

• C語(yǔ)言
• 鏈?zhǔn)?/a>
• 二叉樹
• 數(shù)據(jù)結(jié)構(gòu)

相關(guān)文章

• 

  c++與python實(shí)現(xiàn)二分查找的原理及實(shí)現(xiàn)

  本文介紹了c++與python實(shí)現(xiàn)二分查找的原理及實(shí)現(xiàn)，二分查找指首先將數(shù)組中間值和目標(biāo)值進(jìn)行比較，如果相等則返回；如果不相等，則選擇中間值左邊的一半或者右邊的一半進(jìn)行比較；不斷重復(fù)直到檢索完畢，下文相關(guān)資料需要的朋友可以參考一下

  2022-03-03
• 

  C語(yǔ)言實(shí)例之雙向鏈表增刪改查

  雙向鏈表（Doubly Linked List）是一種常見的數(shù)據(jù)結(jié)構(gòu),在單鏈表的基礎(chǔ)上增加了向前遍歷的功能,與單向鏈表不同,雙向鏈表的每個(gè)節(jié)點(diǎn)除了包含指向下一個(gè)節(jié)點(diǎn)的指針外,還包含指向前一個(gè)節(jié)點(diǎn)的指針,本文給大家介紹了C語(yǔ)言中雙向鏈表的增刪改查

  2023-08-08
• 

  C++/GoLang如何實(shí)現(xiàn)自底向上的歸并排序

  這篇文章主要給大家介紹了關(guān)于C++/GoLang如何實(shí)現(xiàn)自底向上的歸并排序的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

  2020-08-08
• 

  c語(yǔ)言中的二級(jí)指針做函數(shù)參數(shù)說明

  這篇文章主要介紹了c語(yǔ)言中的二級(jí)指針做函數(shù)參數(shù)說明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

  2022-05-05
• 

  最大對(duì)稱字符串的算法

  題目：輸入一個(gè)字符串，輸出該字符串中對(duì)稱的子字符串的最大長(zhǎng)度。比如輸入字符串“google”，由于該字符串里最長(zhǎng)的對(duì)稱子字符串是“goog”，因此輸出4。

  2013-03-03
• 

  C語(yǔ)言求階乘之和的三種實(shí)現(xiàn)方法(先階乘再累加)

  對(duì)于C/C++初學(xué)者來(lái)說,可能會(huì)經(jīng)常遇到如計(jì)算階乘等問題,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言求階乘之和的三種實(shí)現(xiàn)方法,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下

  2022-07-07
• 

  c語(yǔ)言printf函數(shù)的使用詳解

  本篇文章是對(duì)c語(yǔ)言中printf函數(shù)的使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

  2013-05-05
• 

  C語(yǔ)言 以數(shù)據(jù)塊的形式讀寫文件詳解及實(shí)現(xiàn)代碼

  本文主要介紹 C語(yǔ)言 以數(shù)據(jù)塊的形式讀寫文件，這里對(duì)相關(guān)知識(shí)資料做了整理，并附代碼示例，以便大家學(xué)習(xí)參考，有學(xué)習(xí)此部分知識(shí)的朋友可以參考下

  2016-08-08
• 

  C語(yǔ)言結(jié)構(gòu)體中內(nèi)存對(duì)齊的問題理解

  內(nèi)存對(duì)齊”應(yīng)該是編譯器的“管轄范圍”。編譯器為程序中的每個(gè)“數(shù)據(jù)單元”安排在適當(dāng)?shù)奈恢蒙?。但是C語(yǔ)言的一個(gè)特點(diǎn)就是太靈活，太強(qiáng)大，它允許你干預(yù)“內(nèi)存對(duì)齊”。如果你想了解更加底層的秘密，“內(nèi)存對(duì)齊”對(duì)你就不應(yīng)該再模糊了

  2022-02-02
• 

  掌握C++：揭秘寫時(shí)拷貝與淺深拷貝之間的關(guān)系

  探索C++的奧秘,本指南將揭秘寫時(shí)拷貝與淺深拷貝之間的微妙關(guān)系,摸索這些復(fù)雜概念背后的邏輯,讓你的編程技能瞬間提升,來(lái)吧,讓我們一起進(jìn)入這個(gè)引人入勝的C++世界！

  2024-01-01

最新評(píng)論