109.【C语言】数据结构之二叉树层序遍历

目录

1.知识回顾

2.代码实现

准备工作

LevelOrder函数

代码框架

关键代码

3.执行结果

---

1.知识回顾

层序遍历参见106.【C语言】数据结构之二叉树的三种递归遍历方式文章

截取的部分内容

定义:按层的方式遍历(,设n为树的深度,h==1-->h==2-->h==3-->...-->h==n)

以下面这张图为例子

遍历顺序:1-->2-->4-->3-->5-->6

h==1为第一层,只有1;h==2为第二层,有2和4;h==3为第三层,有3,5和6;

2.代码实现

这里用的是队列,画图分析上方二叉树的层序遍历

会发现出队的顺序恰好是层序遍历的结果! (注意空节点不入队)

核心思想:先出队一个根节点,后将根的左右非空节点入队

准备工作

直接借用98.【C语言】数据结构之队列文章的队列代码,将其载入到VS的解决方案

这里需要对原代码左一点修改

Queue.h修改为

typedef struct QueueNode* QDataType;

typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;

队列的每个节点是一个结构体,既存储了树的节点的地址又存储了下一个节点的地址(这样做方便操作)

LevelOrder函数

代码框架

养成良好的习惯 先写初始化和销毁

void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
//......
QueueDestroy(&q);
}

关键代码

非空节点才能入队

以"知识回顾"的二叉树画图分析if (root) {QueuePush(&q,root);}后的图

if (root)
QueuePush(&q,root);

while (!QueueEmpty(&q))
{
        //先出队一个根节点
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);

        //后将根的左右非空节点入队
if (front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}

QueuePop是将data和next都销毁(记得销毁前先保留data数据备用打印)

可以看到QueuePop的free(pq->head);

void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head != NULL);

QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
if (pq->head == NULL)
pq->tail = NULL;
pq->size--;
}

 

3.执行结果

原文地址：https://blog.csdn.net/2401_85828611/article/details/144330199

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！