数据结构：二叉树的广度优先遍历与深度优先遍历（递归方法）。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 风格下更加现代化且易于维护，同时也充分利用了智能指针的优势