除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第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);
}
}
//队列的特点是先进先出
层序遍历关键点在于它对于队列的使用与理解,🥳🥳大家都学废了吗完结撒花~ 🎉🎉🎉