深入理解 Rust 中序遍历（手把手教你用 Rust 实现二叉树中序遍历算法）

在 Rust 中定义二叉树节点

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

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

递归实现中序遍历

最直观的方式是使用递归。我们编写一个函数，接收一个 &Option<Box<TreeNode>> 引用，并将遍历结果收集到一个 Vec<i32> 中。

fn inorder_traversal(root: &Option>, result: &mut Vec) {    if let Some(node) = root {        // 先遍历左子树        inorder_traversal(&node.left, result);                // 访问当前节点        result.push(node.val);                // 再遍历右子树        inorder_traversal(&node.right, result);    }}

完整示例：构建树并执行中序遍历

下面是一个完整的可运行示例，展示如何构建一棵简单的二叉树并执行 Rust中序遍历。

fn main() {    // 构建如下二叉树：    //       1    //        \    //         2    //        /    //       3    let mut root = Box::new(TreeNode::new(1));    root.right = Some(Box::new(TreeNode::new(2)));    root.right.as_mut().unwrap().left = Some(Box::new(TreeNode::new(3)));    let mut result = Vec::new();    inorder_traversal(&Some(root), &mut result);    println!("中序遍历结果: {:?}", result); // 输出: [1, 3, 2]}

迭代方式实现（进阶）

虽然递归简洁易懂，但在某些场景下（如栈空间受限），我们可能希望使用迭代方式。这需要借助显式栈（Vec）来模拟递归过程。

fn inorder_iterative(root: Option>) -> Vec {    let mut result = Vec::new();    let mut stack = Vec::new();    let mut current = root;    while current.is_some() || !stack.is_empty() {        // 一直向左走到底        while let Some(node) = current {            current = node.left;            stack.push(node);        }        // 弹出栈顶节点        if let Some(node) = stack.pop() {            result.push(node.val);            // 转向右子树            current = node.right;        }    }    result}

总结

通过本文，你已经掌握了如何在 Rust 中实现 二叉树中序遍历 的递归与迭代方法。无论是面试准备还是实际项目开发，这些 Rust算法实现 技巧都非常实用。

记住，中序遍历的核心思想是“左 → 根 → 右”，而 Rust 的所有权和借用机制让我们在安全的前提下高效操作树结构。

希望这篇 中序遍历教程 对你有所帮助！动手写一写代码，加深理解吧。