数据结构：二叉树的广度优先遍历与深度优先遍历（递归方法）。C++及其新特性分别实现

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

1. 广度优先遍历（BFS）

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

实现思路：

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

C++ 代码实现：

#include <iostream>
#include <queue>struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};void BFS(TreeNode* root) {if (root == nullptr) return;std::queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();std::cout << node->val << " ";if (node->left) q.push(node->left);if (node->right) q.push(node->right);}
}int main() {TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);root->right->left = new TreeNode(6);root->right->right = new TreeNode(7);std::cout << "BFS traversal: ";BFS(root);std::cout << std::endl;return 0;
}

2. 深度优先遍历（DFS）

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

2.1 前序遍历（Preorder Traversal）

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

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

void Preorder(TreeNode* root) {if (root == nullptr) return;std::cout << root->val << " ";Preorder(root->left);Preorder(root->right);
}

2.2 中序遍历（Inorder Traversal）

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

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

void Inorder(TreeNode* root) {if (root == nullptr) return;Inorder(root->left);std::cout << root->val << " ";Inorder(root->right);
}

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

C++ 代码实现：

int main() {TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);root->right->left = new TreeNode(6);root->right->right = new TreeNode(7);std::cout << "Preorder traversal: ";Preorder(root);std::cout << std::endl;std::cout << "Inorder traversal: ";Inorder(root);std::cout << std::endl;std::cout << "Postorder traversal: ";Postorder(root);std::cout << std::endl;return 0;
}

输出：

Preorder traversal: 1 2 4 5 3 6 7
Inorder traversal: 4 2 5 1 6 3 7
Postorder traversal: 4 5 2 6 7 3 1

总结

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

 新特性实现

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

#include <iostream>
#include <queue>
#include <memory>  // For std::unique_ptr// 使用 std::unique_ptr 来管理内存
struct TreeNode {std::unique_ptr<TreeNode> left;int val;std::unique_ptr<TreeNode> right;TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};// 广度优先遍历(BFS)
void BFS(TreeNode* root) {if (root == nullptr) return;std::queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();std::cout << node->val << " ";if (node->left) q.push(node->left.get());if (node->right) q.push(node->right.get());}
}// 深度优先遍历(DFS)// 1、前序遍历（根节点 -> 左子树 -> 右子树）
void Preorder(TreeNode* root) {if (root == nullptr) return;std::cout << root->val << " ";Preorder(root->left.get());Preorder(root->right.get());
}// 2、中序遍历（左子树 -> 根节点 -> 右子树）
void Inorder(TreeNode* root) {if (root == nullptr) return;Inorder(root->left.get());std::cout << root->val << " ";Inorder(root->right.get());
}// 3、后序遍历（左子树 -> 右子树 -> 根节点）
void Postorder(TreeNode* root) {if (root == nullptr) return;Postorder(root->left.get());Postorder(root->right.get());std::cout << root->val << " ";
}int main() {auto root = std::make_unique<TreeNode>(1);root->left = std::make_unique<TreeNode>(2);root->right = std::make_unique<TreeNode>(3);root->left->left = std::make_unique<TreeNode>(4);root->left->right = std::make_unique<TreeNode>(5);root->right->left = std::make_unique<TreeNode>(6);root->right->right = std::make_unique<TreeNode>(7);/*std::cout << "BFS traversal: ";BFS(root.get());std::cout << std::endl;*/std::cout << "Preorder traversal: ";Preorder(root.get());std::cout << std::endl;std::cout << "Inorder traversal: ";Inorder(root.get());std::cout << std::endl;std::cout << "Postorder traversal: ";Postorder(root.get());std::cout << std::endl;return 0;
}

代码说明：

1. 使用 std::unique_ptr：

   • TreeNode 的左右子节点使用 std::unique_ptr 进行管理，确保内存自动释放，避免手动调用 delete。

2. std::make_unique：

   • C++14 引入的 std::make_unique 函数用于创建 std::unique_ptr 对象，它使代码更加简洁和安全。

3. get() 方法：

   • 在遍历树时，通过 get() 方法获取原始指针，因为 std::queue 中存储的是裸指针（TreeNode*），而不是智能指针。

4. 内存安全：

   • 由于使用了 std::unique_ptr，在树不再需要时（例如当程序退出时），所有节点的内存都会自动释放，无需手动管理。

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

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

输出结果：

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

Preorder traversal: 1 2 4 5 3 6 7 
Inorder traversal: 4 2 5 1 6 3 7 
Postorder traversal: 4 5 2 6 7 3 1 

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