广度优先搜索树（广度优先搜索 递归）



在二叉树的遍历中，广度优先遍历（BFS）和深度优先遍历（DFS）是两种常用的遍历方法。它们的遍历顺序和实现方法有所不同。以下是这两种遍历方法的详细解释和 C++ 实现。

1. 广度优先遍历（BFS）

广度优先遍历使用队列（）来实现，它按层次从上到下、从左到右遍历树的每一层。

实现思路：

1. 从根节点开始，将其加入队列。
2. 从队列中取出节点，访问该节点，并将其左右子节点按顺序加入队列。
3. 重复以上步骤，直到队列为空。

C++ 代码实现：

2. 深度优先遍历（DFS）

深度优先遍历有三种主要方法：前序遍历、中序遍历和后序遍历。它们都可以通过递归或使用栈（）来实现。

2.1 前序遍历（Preorder Traversal）

前序遍历顺序是：根节点 -> 左子树 -> 右子树。

C++ 代码实现（递归）：

2.2 中序遍历（Inorder Traversal）

中序遍历顺序是：左子树 -> 根节点 -> 右子树。

C++ 代码实现（递归）：

2.4 深度优先遍历（DFS）整体实现

C++ 代码实现：

输出：

总结

• 广度优先遍历（BFS）：使用队列，按层次从上到下、从左到右遍历。
• 深度优先遍历（DFS）：
  • 前序遍历（根 -> 左 -> 右）
  • 中序遍历（左 -> 根 -> 右）
  • 后序遍历（左 -> 右 -> 根）

 新特性实现

下面是一个使用 C++11 修改后的代码。C++11 引入了一些新特性，如智能指针（ 和 ）和基于范围的 循环等，这些特性可以使代码更加现代化和安全。这里，我将使用 来管理二叉树节点的内存，避免手动的内存管理。

代码说明：

1. 使用 ：
   • 的左右子节点使用 进行管理，确保内存自动释放，避免手动调用 。
2. ：
   • C++14 引入的 函数用于创建 对象，它使代码更加简洁和安全。
3. 方法：
   • 在遍历树时，通过 方法获取原始指针，因为 中存储的是裸指针（），而不是智能指针。
4. 内存安全：
   • 由于使用了 ，在树不再需要时（例如当程序退出时），所有节点的内存都会自动释放，无需手动管理。

另外：全局函数 Preorder、Inorder、Postorder的形参可以改写为

const std::unique_ptr<TreeNode>& root  让代码更简洁一些

输出结果：

代码的输出与之前的实现相同，依然是：

这种修改使得代码在 C++11 风格下更加现代化且易于维护，同时也充分利用了智能指针的优势

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/45562.html