DEV Community
·
按层打印树的每一层
💡
原文英文，约1100词，阅读约需4分钟。
📝
内容提要
文章讨论了树的遍历方法，重点介绍了广度优先遍历（BFS）和深度优先遍历（DFS）。BFS使用队列按层访问节点，而DFS通过栈或递归深入一个方向。通过在BFS中添加虚拟节点，可以区分树的不同层级，最终实现了按层打印树的功能。
🎯
关键要点
- 文章讨论了树的遍历方法，重点介绍了广度优先遍历（BFS）和深度优先遍历（DFS）。
- 广度优先遍历（BFS）使用队列按层访问节点。
- 深度优先遍历（DFS）通过栈或递归深入一个方向。
- BFS遍历时，首先访问节点1，然后依次访问节点2、3、5和6，最后访问节点4和7。
- 在BFS中，使用队列作为辅助数据结构，确保按层遍历。
- 深度优先遍历（DFS）则是优先深入一个方向，使用栈作为辅助数据结构。
- DFS可以通过常规栈或递归实现。
- 树是一种图的配置，因此可以使用BFS和DFS遍历树。
- 为了区分树的不同层级，可以在BFS中添加虚拟节点。
- 虚拟节点的作用是标记当前层的结束，并在队列中添加以便继续遍历。
➡️
