在二叉树的遍历中，广度优先遍历（BFS）和深度优先遍历（DFS）是两种常用的遍历方法。它们的遍历顺序和实现方法有所不同。以下是这两种遍历方法的详细解释和 C++ 实现。
1. 广度优先遍历（BFS）
广度优先遍历使用队列（）来实现，它按层次从上到下、从左到右遍历树的每一层。
实现思路：
- 从根节点开始，将其加入队列。
- 从队列中取出节点，访问该节点，并将其左右子节点按顺序加入队列。
- 重复以上步骤，直到队列为空。
C++ 代码实现：
2. 深度优先遍历（DFS）
深度优先遍历有三种主要方法：前序遍历、中序遍历和后序遍历。它们都可以通过递归或使用栈（）来实现。
2.1 前序遍历（Preorder Traversal）
前序遍历顺序是：根节点 -> 左子树 -> 右子树。
C++ 代码实现（递归）：
2.2 中序遍历（Inorder Traversal）
中序遍历顺序是：左子树 -> 根节点 -> 右子树。
C++ 代码实现（递归）：
2.4 深度优先遍历（DFS）整体实现
C++ 代码实现：
输出：
总结
- 广度优先遍历（BFS）：使用队列，按层次从上到下、从左到右遍历。
- 深度优先遍历（DFS）：
- 前序遍历（根 -> 左 -> 右）
- 中序遍历（左 -> 根 -> 右）
- 后序遍历（左 -> 右 -> 根）
新特性实现
下面是一个使用 C++11 修改后的代码。C++11 引入了一些新特性，如智能指针（ 和 ）和基于范围的 循环等，这些特性可以使代码更加现代化和安全。这里，我将使用 来管理二叉树节点的内存，避免手动的内存管理。
代码说明：
- 使用 ：
- 的左右子节点使用 进行管理，确保内存自动释放，避免手动调用 。
- ：
- C++14 引入的 函数用于创建 对象，它使代码更加简洁和安全。
- 方法：
- 在遍历树时，通过 方法获取原始指针，因为 中存储的是裸指针（），而不是智能指针。
- 内存安全：
- 由于使用了 ，在树不再需要时（例如当程序退出时），所有节点的内存都会自动释放，无需手动管理。
另外：全局函数 Preorder、Inorder、Postorder的形参可以改写为
const std::unique_ptr<TreeNode>& root 让代码更简洁一些
输出结果：
代码的输出与之前的实现相同，依然是：
这种修改使得代码在 C++11 风格下更加现代化且易于维护，同时也充分利用了智能指针的优势
今天的文章 广度优先搜索树（广度优先搜索 递归）分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ri-ji/15717.html