掌握Rust中的树结构（从零开始学习Rust树算法与数据结构）

最常见的树类型是二叉树（Binary Tree），即每个节点最多有两个子节点：左子节点和右子节点。

在 Rust 中定义二叉树

Rust 使用 Option 和 Box 来安全地处理树结构中的引用和内存分配。下面是一个简单的二叉树节点定义：

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

这里我们使用了 Option> 来表示子节点可能为空（None）或存在（Some(Box)）。Box 是 Rust 的智能指针，用于在堆上分配内存，避免无限大小的问题。

构建一棵简单的树

现在我们来手动构建一个包含三个节点的小树：

fn main() {    let mut root = TreeNode::new(1);    root.left = Some(Box::new(TreeNode::new(2)));    root.right = Some(Box::new(TreeNode::new(3)));    println!("{:?}", root);}  

运行这段代码，你会看到类似这样的输出：

TreeNode { val: 1, left: Some(TreeNode { val: 2, left: None, right: None }), right: Some(TreeNode { val: 3, left: None, right: None }) }  

树的遍历：递归实现

树的遍历是树算法的核心。常见的遍历方式有三种：前序（根-左-右）。下面我们用 Rust 实现这三种遍历。

// 前序遍历fn preorder(node: &Option>) {    if let Some(n) = node {        print!("{} ", n.val);        preorder(&n.left);        preorder(&n.right);    }}// 中序遍历fn inorder(node: &Option>) {    if let Some(n) = node {        inorder(&n.left);        print!("{} ", n.val);        inorder(&n.right);    }}// 后序遍历fn postorder(node: &Option>) {    if let Some(n) = node {        postorder(&n.left);        postorder(&n.right);        print!("{} ", n.val);    }}  

在 main 函数中调用它们：

fn main() {    let mut root = TreeNode::new(1);    root.left = Some(Box::new(TreeNode::new(2)));    root.right = Some(Box::new(TreeNode::new(3)));    print!("前序遍历: ");    preorder(&root.left); // 注意：这里应传 &Some(Box::...)    // 更准确的写法：    if let Some(r) = &root {        print!("前序遍历: ");        preorder(&Some(Box::new(r.clone()))); // 实际中建议重构为引用传递    }    // 为简化，我们直接传递 &root 的引用    // 更好的方式是修改函数签名接受 &TreeNode}  

为了更清晰，我们可以重写遍历函数，使其接受 &TreeNode 而不是 &Option>：

fn preorder_ref(node: &TreeNode) {    print!("{} ", node.val);    if let Some(ref left) = node.left {        preorder_ref(left);    }    if let Some(ref right) = node.right {        preorder_ref(right);    }}// 在 main 中调用fn main() {    let mut root = TreeNode::new(1);    root.left = Some(Box::new(TreeNode::new(2)));    root.right = Some(Box::new(TreeNode::new(3)));    print!("前序遍历: ");    preorder_ref(&root);    println!();}  

输出结果为：

前序遍历: 1 2 3  

为什么选择 Rust 实现树算法？

Rust 的所有权系统和借用检查器能有效防止空指针、内存泄漏等常见错误。在实现 Rust树算法 时，你无需手动管理内存，编译器会确保你的代码在运行时安全可靠。

此外，Rust 的模式匹配（if let、match）让处理 Option 类型变得非常自然，非常适合表达树结构中的“存在/不存在”语义。

总结

通过本教程，你已经学会了：

• 如何在 Rust 中定义二叉树节点
• 如何手动构建一棵树
• 如何实现前序、中序、后序遍历
• 理解 Rust 的 Option 和 Box 在树结构中的作用

掌握这些基础后，你可以进一步探索Rust数据结构中的平衡树（如 AVL 树、红黑树）、B 树，甚至用于解析表达式的抽象语法树（AST）。

记住，实践是最好的老师。尝试自己编写一个函数来计算树的高度，或者判断一棵树是否为对称二叉树吧！

关键词回顾：Rust树算法、Rust数据结构、Rust二叉树实现、Rust递归遍历。