用Rust从零构建二叉搜索树（BST）

第一步：定义树节点

在 Rust 中，由于所有权机制，我们不能直接使用原始指针。通常我们会使用 Rc<RefCell<T>> 来实现共享可变引用。但为了更清晰地展示逻辑，我们先使用 Box（独占所有权）来实现一个不可变但可构建的 BST。后续我们会讨论如何支持修改。

首先，我们定义一个 TreeNode 结构体：

#[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>> 表示子节点可能为空（None）或存在（Some(Box<...>)）。

第二步：构建二叉搜索树结构

接下来，我们定义 BinarySearchTree 结构体，并实现插入和查找方法。

#[derive(Debug)]struct BinarySearchTree {    root: Option>,}impl BinarySearchTree {    fn new() -> Self {        BinarySearchTree { root: None }    }    // 插入一个值    fn insert(&mut self, val: i32) {        self.root = Self::insert_helper(self.root.take(), val);    }    fn insert_helper(node: Option>, val: i32) -> Option> {        match node {            None => Some(Box::new(TreeNode::new(val))),            Some(mut boxed_node) => {                if val < boxed_node.val {                    boxed_node.left = Self::insert_helper(boxed_node.left, val);                } else if val > boxed_node.val {                    boxed_node.right = Self::insert_helper(boxed_node.right, val);                }                // 如果相等，不插入（去重）                Some(boxed_node)            }        }    }    // 查找一个值是否存在    fn search(&self, val: i32) -> bool {        Self::search_helper(&self.root, val)    }    fn search_helper(node: &Option>, val: i32) -> bool {        match node {            None => false,            Some(boxed_node) => {                if val == boxed_node.val {                    true                } else if val < boxed_node.val {                    Self::search_helper(&boxed_node.left, val)                } else {                    Self::search_helper(&boxed_node.right, val)                }            }        }    }}  

注意：take() 方法会将 Option 变成 None 并返回其内部值，这在递归构建树时非常有用。

第三步：测试我们的 BST

现在让我们写一个简单的 main 函数来测试插入和查找功能：

fn main() {    let mut bst = BinarySearchTree::new();    bst.insert(50);    bst.insert(30);    bst.insert(70);    bst.insert(20);    bst.insert(40);    bst.insert(60);    bst.insert(80);    println!("树结构: {:?}", bst);    println!("查找 40: {}", bst.search(40)); // true    println!("查找 25: {}", bst.search(25)); // false}  

运行这段代码，你会看到树被正确构建，并且查找功能正常工作。

进阶：中序遍历（获取有序序列）

二叉搜索树的一个重要特性是：中序遍历（左 → 根 → 右）会得到一个升序序列。我们可以添加一个遍历方法：

impl BinarySearchTree {    fn inorder(&self) -> Vec {        let mut result = Vec::new();        Self::inorder_helper(&self.root, &mut result);        result    }    fn inorder_helper(node: &Option>, result: &mut Vec) {        if let Some(boxed_node) = node {            Self::inorder_helper(&boxed_node.left, result);            result.push(boxed_node.val);            Self::inorder_helper(&boxed_node.right, result);        }    }}  

在 main 中调用 bst.inorder() 将返回 [20, 30, 40, 50, 60, 70, 80]。

总结

通过本教程，你已经掌握了如何用 Rust 实现一个基本的二叉搜索树。我们涵盖了节点定义、插入、查找和中序遍历等核心操作。这个实现虽然简单，但体现了 Rust数据结构设计中的关键思想：利用 Option 和 Box 安全地管理堆内存，同时保持类型安全。

如果你希望支持删除操作或需要多线程共享，可以考虑使用 Rc<RefCell<TreeNode>>。但对于大多数单线程场景，当前的 Box 实现已经足够高效。

希望这篇 Rust BST实现 教程对你有帮助！继续练习，你很快就能熟练运用 Rust二叉搜索树 解决实际问题了。