Rust语言实现二叉树层序遍历（小白也能学会的广度优先搜索算法详解）

为什么用 Rust 实现？

Rust 是一门内存安全、高性能的系统编程语言，其所有权机制能有效防止空指针和数据竞争。使用 Rust 实现 Rust层序遍历 不仅能加深对算法的理解，还能锻炼你对 Rust 所有权、借用和标准库（如 VecDeque）的掌握。

准备工作：定义二叉树节点

首先，我们需要定义一个二叉树节点结构。在 Rust 中，我们通常使用 Option<Box<TreeNode>> 来表示子节点（因为子节点可能为空）。

#[derive(Debug, Clone)]pub struct TreeNode {    pub val: i32,    pub left: Option<Box<TreeNode>>,    pub right: Option<Box<TreeNode>>,}impl TreeNode {    #[inline]    pub fn new(val: i32) -> Self {        TreeNode {            val,            left: None,            right: None,        }    }}  

核心算法：使用队列实现层序遍历

层序遍历的关键在于使用 队列（FIFO：先进先出）来暂存待访问的节点。Rust 标准库中的 std::collections::VecDeque 是一个高效的双端队列，非常适合此场景。

算法步骤如下：

1. 将根节点加入队列。
2. 当队列非空时，取出队首节点并记录其值。
3. 将其左子节点（如果存在）加入队列。
4. 将其右子节点（如果存在）加入队列。
5. 重复步骤 2-4，直到队列为空。

完整代码实现

下面是一个完整的 Rust算法实现 示例，包含构建测试树和执行层序遍历：

use std::collections::VecDeque;// 假设 TreeNode 定义如上pub fn level_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {    let mut result = Vec::new();    if root.is_none() {        return result;    }    let mut queue = VecDeque::new();    queue.push_back(root);    while !queue.is_empty() {        let level_size = queue.len();        let mut current_level = Vec::new();        for _ in 0..level_size {            if let Some(node) = queue.pop_front().unwrap() {                current_level.push(node.val);                if node.left.is_some() {                    queue.push_back(node.left);                }                if node.right.is_some() {                    queue.push_back(node.right);                }            }        }        result.push(current_level);    }    result}// 测试函数fn main() {    // 构建如下二叉树：    //       3    //      / \    //     9   20    //        /  \    //       15   7    let root = Some(Box::new(TreeNode {        val: 3,        left: Some(Box::new(TreeNode::new(9))),        right: Some(Box::new(TreeNode {            val: 20,            left: Some(Box::new(TreeNode::new(15))),            right: Some(Box::new(TreeNode::new(7))),        })),    }));    let traversal = level_order(root);    println!("{:?}", traversal); // 输出: [[3], [9, 20], [15, 7]]}  

关键点解析

• 队列初始化：将根节点包装在 Option<Box<...>> 中入队。
• 按层处理：通过记录当前队列长度（即当前层节点数），确保每轮循环只处理一层节点。
• 空值处理：使用 if let 安全解包 Option，避免 panic。

总结

通过本教程，你已经学会了如何用 Rust 实现 二叉树遍历 中的层序遍历。这项技能不仅适用于面试题，也是理解图算法（如 BFS）的基础。记住，广度优先搜索 的核心思想是“层层推进”，而 Rust 的强大类型系统能帮助你写出更安全、高效的代码。

现在，试着自己构建不同的二叉树并运行这段代码吧！实践是掌握 Rust层序遍历 和 Rust算法实现 的最佳方式。