【C语言】二叉树的层序遍历

admin • 2023-11-23 19:50 • C/C++

创建二叉树

要对二叉树进行层序遍历，那么我们首先得先创建出来一个二叉树了。

二叉树的模拟创建代码：

#define _CRT_SECURE_NO_WARNINGS

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

typedef  int BTDataType;//二叉树存放数据的类型

typedef struct BinaryTreeNode {//二叉树结构的定义

	struct BinaryTreeNode* left;//二叉树的左节点
	struct BinaryTreeNode* right;//二叉树的右节点
	BTDataType data;//二叉树的数据域

}BTNode;//将定义的二叉树结构名字重新简化定义



BTNode* BuyNode(BTDataType x) {//创建并且同时初始化二叉树的一个节点

	BTNode* node = (BTNode*)malloc(sizeof(BTNode));

	if (node == NULL) {
		printf("malloc fail!");
		exit(-1);
	}

	node->left = NULL;
	node->right = NULL;
	node->data = x;

	return node;
}

BTNode* CreatBinaryTree() {//模拟创建一个二叉树

	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;

}


int main() {

	BTNode* root = CreatBinaryTree();//模拟创建一个二叉树

	

	return 0;
}

二叉树的层序遍历

有了二叉树，那么我们接下来就来讲讲咋给它层序遍历一下了。

遍历二叉树，简单点来说呢，就是将其数据一层一层的进行遍历打印。也就是对其进行层序遍历。

看起来虽然简单，但要怎么实现这个层序遍历呢？

与队列的结合实现层序遍历

这里，我们可以利用一下队列的先进先出的特性来结合二叉树来实现层序遍历。

先看图：

这个图的意思就是：

我们可以先一个一个遍历二叉树的所有节点，每当遍历到一个节点的时候，我们可先将其数据打印出来，再将其删除。紧接着再将其左右孩子节点传入队列中并继续递归调用以上操作即可。

易混淆点：我们在队列中存储的并不是数，而是一个个二叉树节点的地址。并且在队列中删除了其数据之后，二叉树的节点并没有因此消失，因此还是可以根据二叉树的根节点找到其左右孩子节点并放入队列中去。

接下来，就是怎么在二叉树中联合使用队列来实现要求了。

队列的实现代码

Queue.c

#define _CRT_SECURE_NO_WARNINGS

#include "Queue.h"

void QueueInit(Queue* pq) {
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
void QueueDestory(Queue* pq) {
	
	assert(pq);

	QNode* cur = pq->head;

	while (cur) {
		
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;

}
void QueuePush(Queue* pq,QDataType x) {

	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建新节点，准备插入
	
	if (newnode == NULL) {
		printf("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;



	if (pq->tail == NULL) {//当队列为空
		pq->tail = pq->head = newnode;
	}
	else {//当队列不为空
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
void QueuePop(Queue* pq) {

	assert(pq);
	assert(!QueueEmpty(pq));//为空的时候不能再删除了

	//只有一个节点的
	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;
	}
	else {//有多个节点的
		QNode* tmp = pq->head->next;
		free(pq->head);
		pq->head = tmp;
	}


}
QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

QDataType QueueBack(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}


bool QueueEmpty(Queue* pq) {
	
	assert(pq);
	return (pq->head == NULL);//为空的话那么tail和head
	                          //至少有一个为空，head或者tail都可以
}

int QueueSize(Queue* pq) {
	
	assert(pq);
	QNode* cur = pq->head;
	int size = 0;
	while (cur) {

		++size;
		cur = cur->next;
	}
	return size;
}

Queue.h

#define _CRT_SECURE_NO_WARNINGS

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




typedef int QDataType;

typedef struct QueueNode {//队列的定义，用指针来创建

	QDataType data;
	struct QueueNode* next;

}QNode;

typedef struct Queue {//直接另外建立两个指针用来指向队列的队头和队尾。
	//方便了很多，比如头插和头删，以及查找队头和队尾元素都方便多了
	//减少了遍历次数
	QNode* head;
	QNode* tail;

}Queue;

//队列的初始化
void QueueInit(Queue* pq);

//队列的销毁
void QueueDestory(Queue* pq);

//队列的加数据（只能尾插）
void QueuePush(Queue* pq, QDataType x);

//队列的删数据（只能头删）
void QueuePop(Queue* pq);

//找队头的节点
QDataType QueueFront(Queue* pq);

//找队尾的节点
QDataType QueueBack(Queue* pq);

//判断队列是否为空
bool QueueEmpty(Queue* pq);

//计算队列的节点个数
int QueueSize(Queue* pq);

接下来，我们要将队列代码插入到二叉树中去。（先复制好Queue.c和Queue.h文件）

再点击头文件右键，先选添加，再选现有项

然后，会进入到以下界面（这里我已经添加好了）刚进是没有的，先在本项目文件位置处将复制好的Queue.c和Queue.h文件复制进去，再点击添加即可。

然后将.c文件直接拖到下面的源码块即可。

那么这时，我们来试着实现代码吧。（二叉树的实现代码上面有）

然后将队列中存储的数据改成二叉树的节点地址，并且同时在二叉树的包含的头文件中加入队列的头文件。

这样一番操作下来，看似没问题了。VS也没有报啥错。那我们来运行一下吧。

看看队列能否被成功创建出来。

运行失败，弹出来了这么一大筐子的错误。

这时，不用慌张。

因为这里我们在队列中直接定义二叉树了，造成它一时找不到所定义的二叉树节点类型，导致报错。

这时，就需要我们使用一个概念：前置声明

如下，这样Queue.h头文件就可在被调用时，因这里事先声明有这么个变量，然后在需要使用它的时候，不仅会在引用它的文件中找，也会去其他文件中找。就不会找不到了。

接下来，就是层序遍历的主要代码了：

void TreeLevelOrder(root) {
	Queue pq;
	QueueInit(&pq);//创建一个队列，利用其先进先出的特性并结合二叉树实现层序遍历

	if (root) {//首先，判断二叉树是否是空树。不是空树，就将根节点入队列
		QueuePush(&pq, root);
	}

	while (!QueueEmpty(&pq)) {//判断栈是否为空队列，不为空栈的话就可以进入程序中循环

		BTNode* front = QueueFront(&pq);//先将根节点的地址拿出来
		
		QueuePop(&pq);//将根节点弹出队列（注意:二叉树并没有被销毁）

		printf("%d ", front->data);
		
		if (front->left) {//判断根节点的左子树是否存在
			QueuePush(&pq, front->left);//如果存在则将其入队列
		}

		if (front->right) {//判断根节点的右子树是否存在
			QueuePush(&pq, front->right);//如果存在，则将其入队列
		}
	}

	printf("n");
	QueueDestory(&pq);//队列这时已经空了，后面也不需要使用了，所以将其置空。
}

如下，可以结合上面的画的思路图一起理解。

到这里，也就结束了。

不过说了这么长，可能思路有点混乱。

下面则有整个实现的代码，再总体看看可能会好点：

Test.c

#define _CRT_SECURE_NO_WARNINGS

#include "Queue.h"


typedef  int BTDataType;//二叉树存放数据的类型

typedef struct BinaryTreeNode {//二叉树结构的定义

	struct BinaryTreeNode* left;//二叉树的左节点
	struct BinaryTreeNode* right;//二叉树的右节点
	BTDataType data;//二叉树的数据域

}BTNode;//将定义的二叉树结构名字重新简化定义

BTNode* BuyNode(BTDataType x) {//创建并且同时初始化二叉树的一个节点

	BTNode* node = (BTNode*)malloc(sizeof(BTNode));

	if (node == NULL) {
		printf("malloc fail!");
		exit(-1);
	}

	node->left = NULL;
	node->right = NULL;
	node->data = x;

	return node;
}

BTNode* CreatBinaryTree() {//模拟创建一个二叉树

	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;

}

void TreeLevelOrder(root) {
	Queue pq;
	QueueInit(&pq);//创建一个队列，利用其先进先出的特性并结合二叉树实现层序遍历

	if (root) {//首先，判断二叉树是否是空树。不是空树，就将根节点入队列
		QueuePush(&pq, root);
	}

	while (!QueueEmpty(&pq)) {//判断栈是否为空队列，不为空栈的话就可以进入程序中循环

		BTNode* front = QueueFront(&pq);//先将根节点的地址拿出来
		
		QueuePop(&pq);//将根节点弹出队列（注意:二叉树并没有被销毁）

		printf("%d ", front->data);
		
		if (front->left) {//判断根节点的左子树是否存在
			QueuePush(&pq, front->left);//如果存在则将其入队列
		}

		if (front->right) {//判断根节点的右子树是否存在
			QueuePush(&pq, front->right);//如果存在，则将其入队列
		}
	}

	printf("n");
	QueueDestory(&pq);//队列这时已经空了，后面也不需要使用了，所以将其置空。
}



int main(){

	BTNode* root = CreatBinaryTree();//模拟创建一个二叉树

	TreeLevelOrder(root);

	return 0;
}

Queue.c

#define _CRT_SECURE_NO_WARNINGS

#include "Queue.h"

void QueueInit(Queue* pq) {
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
void QueueDestory(Queue* pq) {
	
	assert(pq);

	QNode* cur = pq->head;

	while (cur) {
		
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;

}
void QueuePush(Queue* pq,QDataType x) {

	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建新节点，准备插入
	
	if (newnode == NULL) {
		printf("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;



	if (pq->tail == NULL) {//当队列为空
		pq->tail = pq->head = newnode;
	}
	else {//当队列不为空
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
void QueuePop(Queue* pq) {

	assert(pq);
	assert(!QueueEmpty(pq));//为空的时候不能再删除了

	//只有一个节点的
	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;
	}
	else {//有多个节点的
		QNode* tmp = pq->head->next;
		free(pq->head);
		pq->head = tmp;
	}


}
QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

QDataType QueueBack(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}


bool QueueEmpty(Queue* pq) {
	
	assert(pq);
	return (pq->head == NULL);//为空的话那么tail和head
	                          //至少有一个为空，head或者tail都可以
}

int QueueSize(Queue* pq) {
	
	assert(pq);
	QNode* cur = pq->head;
	int size = 0;
	while (cur) {

		++size;
		cur = cur->next;
	}
	return size;
}

Queue.h

#define _CRT_SECURE_NO_WARNINGS

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


//前置声明
struct BinaryTreeNode;

typedef struct BinaryTreeNode* QDataType;

typedef struct QueueNode {//队列的定义，用指针来创建

	QDataType data;
	struct QueueNode* next;

}QNode;

typedef struct Queue {//直接另外建立两个指针用来指向队列的队头和队尾。
	//方便了很多，比如头插和头删，以及查找队头和队尾元素都方便多了
	//减少了遍历次数
	QNode* head;
	QNode* tail;

}Queue;

//队列的初始化
void QueueInit(Queue* pq);

//队列的销毁
void QueueDestory(Queue* pq);

//队列的加数据（只能尾插）
void QueuePush(Queue* pq, QDataType x);

//队列的删数据（只能头删）
void QueuePop(Queue* pq);

//找队头的节点
QDataType QueueFront(Queue* pq);

//找队尾的节点
QDataType QueueBack(Queue* pq);

//判断队列是否为空
bool QueueEmpty(Queue* pq);

//计算队列的节点个数
int QueueSize(Queue* pq);

有错误欢迎留言讨论，也可留言唠唠嗑。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

c语言图论算法

二维码

有如下分段函数，写程序，输入X，求Y的值

< <上一篇

)">

头歌c语言实训项目-字符数组

下一篇>>

搜索内容