二叉树层序遍历的实现(C语言)
二叉树层序遍历
- 层序遍历的简单介绍
- 层序遍历的实现
- 思路分析+画图
- 接口实现
- 总结
层序遍历的简单介绍
层序遍历:从所在二叉树的根节点出发,先访问第一层根节点,然后从左向右访问第二层的节点,接着第三层,以此类推。
简单的说:自上而下,自左向右。
层序遍历的实现
层序遍历的接口实现要使用队列的相关知识, 队列相关知识的博客链接
思路分析+画图
思路:
1.如果根节点不为空,先把根节点push到队列
2.取出队头节点,按照顺序把左孩子和右孩子节点push到队列。
3.继续上面步骤,取出队头节点,把其孩子节点push到队列
接口实现
//层序遍历
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
//判断根节点是否为空,如果为空不入队列,则此时队列为空,也不会执行下面的循环
if (root)
QueuePush(&q, root);
//持续这个循环,循环结束层序遍历结束
while (!QueueEmpty(&q))
{
//取队头
BTNode* front = QueueFront(&q);
QueuePop(&q);
//打印对头数据
printf("%d ", front->data);
//如果队头的左、右孩子存在,push到队列
if (front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
QueueDestroy(&q);
}
注意:程序的出口一定要销毁队列,防止内存泄漏
总结
- DFS:深度优先遍历,在二叉树中先序遍历可以称为深度优先遍历。—— 一般使用递归。如果要求低一些,中序和后序遍历也可以称为深度优先遍历。
- BFS:广度优先遍历,在二叉树中层序遍历可以称为广度优先遍历。——一般使用队列。
电力电子空间: 这真是一篇高质量的好文,深度理解和清晰的表达方式使复杂的技术概念变得容易理解,值得收藏点赞。博主用心很有耐心,更有对知识的热忱和热爱,写了这么实用有效的分享,期盼博主能够光顾我的博客,给予宝贵的指导!
CSDN-Ada助手: 推荐 CS入门 技能树:https://edu.csdn.net/skill/gml?utm_source=AI_act_gml
白话机器学习: 博主的文章细节很到位,兼顾实用性和可操作性,感谢博主的分享,期待博主持续带来更多好文
CSDN-Ada助手: 哇, 你的文章质量真不错,值得学习!不过这么高质量的文章, 还值得进一步提升, 以下的改进点你可以参考下: (1)增加除了各种控件外,文章正文的字数;(2)增加条理清晰的目录。