数据结构——二叉树的层序遍历

大耳朵土土垚

发布于 2024-03-16 11:31:15

1070

发布于 2024-03-16 11:31:15

文章被收录于专栏：c/c++c/c++

1.什么是层序遍历？

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

2.层序遍历的实现

// 层序遍历

void LevelOrder(BTNode* root);

实现之前我们还是简单创造一颗符合我们心意的二叉树：

BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->right = NULL;
	newnode->data = x;
	newnode->left = NULL;
	return newnode;
}
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 LevelOrder(BTNode* root)
{
	Queue qt;//创建队列
	QueueInit(&qt);//队列初始化

	if (root)//判断节点是否为空
		QueuePush(&qt, root);//不为空入队列
	while (!QueueEmpty(&qt))//判断队列是否为空
	{
		BTNode* front = QueueFront(&qt);//不为空取队头值
		printf("%d\n", front->data);//打印队头值
		QueuePop(&qt);//删除队头值

		if (front->left)//接着将左右子树的节点依次入队列
			QueuePush(&qt, front->left);
		if (front->right)
			QueuePush(&qt, front->right);
	}
	QueueDestroy(&qt);//销毁队列
}

层序遍历利用队列先进先出的特点达到遍历的效果，以上就是实现层序遍历的函数啦~🥳🥳🥳 运行结果如下：

✨✨队列的实现在这里，记得使用前要声明哦~ 也可以查看土土的博客二叉树前、中、后序遍历进行详细的学习。

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


typedef struct QListNode
{
    struct QListNode* pNext;
    QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
    QNode* front;
    QNode* rear;
}Queue;

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建新节点
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = data;
	newnode->pNext = NULL;
	//队列为空的情况入队列
	if (QueueEmpty(q))
	{
		q->front = newnode;
		q->rear = newnode;
		return;
	}
	//队列不为空的情况入队列
	else
	{
		q->rear->pNext = newnode;
		q->rear = newnode;
		return;
	}
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));//判断队列非空
	QNode* tmp = q->front;//先保存队头指针
	q->front = tmp->pNext;
	free(tmp);
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));//判断队列非空
	return q->front->data;

}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));//判断队列非空
	return q->rear->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));//判断队列非空
	int count = 0;//记录元素个数
	QNode* cur = q->front;
	while (cur)
	{
		cur = cur->pNext;
		count++;
	}
	return count;
}
// 检测队列是否为空，如果为空返回true,非空返回false
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->front == NULL;

}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	//assert(!QueueEmpty(q));//判断队列非空

	while (q->front)
	{
		QueuePop(q);
	}

}


//队列的特点是先进先出