深入理解Rust二叉搜索树删除操作（手把手教你实现BST节点删除）

什么是二叉搜索树（BST）？

二叉搜索树是一种特殊的二叉树，其中每个节点满足以下性质：

• 左子树的所有节点值 < 当前节点值
• 右子树的所有节点值 > 当前节点值
• 左右子树也分别是二叉搜索树

这种结构使得查找、插入和删除操作平均时间复杂度为 O(log n)。

BST删除的三种情况

删除节点时，我们需要考虑三种情况：

1. 叶子节点（无子节点）：直接删除即可。
2. 只有一个子节点：用其子节点替代它。
3. 有两个子节点：找到中序后继（右子树中的最小值）或中序前驱（左子树中的最大值），用该值替换当前节点，再删除那个后继/前驱节点。

Rust BST 基础结构定义

首先，我们定义树节点和树本身的结构。注意 Rust 中使用 Option<Box<Node>> 来表示可能为空的子节点。

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

实现删除操作

接下来是核心部分——实现 delete 方法。我们将采用递归方式处理。

impl BST {    pub fn delete(&mut self, val: i32) {        self.root = Self::delete_node(self.root.take(), val);    }    fn delete_node(node: Option>, val: i32) -> Option> {        match node {            None => None,            Some(mut boxed_node) => {                if val < boxed_node.val {                    // 在左子树中删除                    boxed_node.left = Self::delete_node(boxed_node.left.take(), val);                    Some(boxed_node)                } else if val > boxed_node.val {                    // 在右子树中删除                    boxed_node.right = Self::delete_node(boxed_node.right.take(), val);                    Some(boxed_node)                } else {                    // 找到要删除的节点                    if boxed_node.left.is_none() {                        return boxed_node.right;                    } else if boxed_node.right.is_none() {                        return boxed_node.left;                    }                    // 两个子节点都存在：找右子树的最小值（中序后继）                    let mut successor = boxed_node.right.as_mut().unwrap();                    while successor.left.is_some() {                        successor = successor.left.as_mut().unwrap();                    }                    // 将后继值赋给当前节点                    let successor_val = successor.val;                    // 删除后继节点（它最多只有一个右子节点）                    boxed_node.right = Self::delete_node(boxed_node.right.take(), successor_val);                    boxed_node.val = successor_val;                    Some(boxed_node)                }            }        }    }}

辅助方法：插入与中序遍历

为了测试删除功能，我们还需要插入和遍历方法：

impl BST {    pub fn insert(&mut self, val: i32) {        self.root = Self::insert_node(self.root.take(), val);    }    fn insert_node(node: Option>, val: i32) -> Option> {        match node {            None => Some(Box::new(Node::new(val))),            Some(mut boxed_node) => {                if val < boxed_node.val {                    boxed_node.left = Self::insert_node(boxed_node.left.take(), val);                } else if val > boxed_node.val {                    boxed_node.right = Self::insert_node(boxed_node.right.take(), val);                }                Some(boxed_node)            }        }    }    pub fn inorder(&self) {        Self::inorder_traversal(&self.root);        println!();    }    fn inorder_traversal(node: &Option>) {        if let Some(ref n) = node {            Self::inorder_traversal(&n.left);            print!("{} ", n.val);            Self::inorder_traversal(&n.right);        }    }}

完整测试示例

fn main() {    let mut bst = BST::new();    bst.insert(50);    bst.insert(30);    bst.insert(70);    bst.insert(20);    bst.insert(40);    bst.insert(60);    bst.insert(80);    println!("初始中序遍历:");    bst.inorder(); // 输出: 20 30 40 50 60 70 80    bst.delete(20); // 删除叶子节点    println!("删除20后:");    bst.inorder(); // 输出: 30 40 50 60 70 80    bst.delete(30); // 删除有一个子节点的节点    println!("删除30后:");    bst.inorder(); // 输出: 40 50 60 70 80    bst.delete(50); // 删除有两个子节点的节点    println!("删除50后:");    bst.inorder(); // 输出: 40 60 70 80}

总结

通过本教程，你已经掌握了 Rust BST实现 中最关键的删除操作。理解三种删除场景并正确处理所有权（Ownership）是Rust编程的核心挑战。希望这个 Rust数据结构教程 能帮助你巩固知识。

记住，二叉搜索树节点删除 不仅是面试高频题，也是理解递归和内存管理的绝佳练习。多动手写代码，你会越来越熟练！

如果你觉得有帮助，不妨自己尝试扩展功能，比如删除多个值、添加查找方法等。祝你在Rust学习之旅中不断进步！