深入理解Rust二叉树遍历（从零开始掌握Rust二叉树遍历算法）

什么是二叉树？

二叉树是一种每个节点最多有两个子节点（左子节点和右子节点）的树形结构。在 Rust 中，我们通常用结构体（struct）和枚举（enum）来定义二叉树。

定义二叉树结构

首先，我们需要定义一个二叉树节点：

#[derive(Debug)]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,        }    }}

这里使用 Option<Box<TreeNode>> 来表示子节点可能为空（None）或存在（Some(Box<TreeNode>)）。这是 Rust 中处理可空引用的安全方式。

1. 前序遍历（根 → 左 → 右）

递归实现

pub fn preorder_traversal(root: Option<Box<TreeNode>>) -> Vec<i32> {    let mut result = Vec::new();    preorder_helper(&root, &mut result);    result}fn preorder_helper(node: &Option<Box<TreeNode>>, result: &mut Vec<i32>) {    if let Some(n) = node {        result.push(n.val);          // 访问根        preorder_helper(&n.left, result);   // 遍历左子树        preorder_helper(&n.right, result);  // 遍历右子树    }}

非递归实现（使用栈）

use std::collections::VecDeque;pub fn preorder_iterative(root: Option<Box<TreeNode>>) -> Vec<i32> {    let mut result = Vec::new();    let mut stack = VecDeque::new();        if let Some(node) = root {        stack.push_back(node);    }        while let Some(current) = stack.pop_back() {        result.push(current.val);                // 先压入右子树（因为栈是后进先出）        if let Some(right) = current.right {            stack.push_back(right);        }        if let Some(left) = current.left {            stack.push_back(left);        }    }        result}

2. 中序遍历（左 → 根 → 右）

递归实现

pub fn inorder_traversal(root: Option<Box<TreeNode>>) -> Vec<i32> {    let mut result = Vec::new();    inorder_helper(&root, &mut result);    result}fn inorder_helper(node: &Option<Box<TreeNode>>, result: &mut Vec<i32>) {    if let Some(n) = node {        inorder_helper(&n.left, result);        result.push(n.val);        inorder_helper(&n.right, result);    }}

3. 后序遍历（左 → 右 → 根）

递归实现

pub fn postorder_traversal(root: Option<Box<TreeNode>>) -> Vec<i32> {    let mut result = Vec::new();    postorder_helper(&root, &mut result);    result}fn postorder_helper(node: &Option<Box<TreeNode>>, result: &mut Vec<i32>) {    if let Some(n) = node {        postorder_helper(&n.left, result);        postorder_helper(&n.right, result);        result.push(n.val);    }}

总结

通过本教程，你已经掌握了在 Rust 中实现Rust二叉树遍历的基本方法。无论是使用Rust递归遍历还是Rust非递归遍历，关键在于理解每种遍历顺序的访问逻辑。

对于初学者来说，建议先掌握递归写法，因为它更直观、易读；当你对栈和内存管理有更深理解后，再尝试非递归实现。

希望这篇Rust数据结构教程能帮助你在学习 Rust 的道路上更进一步！如果你有任何问题，欢迎在评论区留言交流。