Rust实现二叉搜索树find函数时递归引用的疑难问题

问题分析 #

你的find函数核心问题在于RefCell的临时借用会被提前销毁：当调用node.borrow().find(value)时，borrow()返回的Ref<Node<T>>是临时变量，find函数返回的&Node<T>依赖这个临时Ref，但函数调用结束后Ref就会被drop，导致引用悬空，触发借用检查器错误。

另外代码里还有逻辑错误：二叉搜索树的方向搞反了——值更大时应该去右子树，值更小时应该去左子树，当前写法会导致查找和插入逻辑完全错误。

修正方案 #

调整find函数的返回值，让它携带Ref的生命周期，避免悬空引用。将返回类型改为Option<Ref<'_, Node<T>>>，就能正确保留借用的生命周期。

修正后的完整代码 #

use std::{cell::Ref, cell::RefCell, fmt::Debug, rc::Rc};

struct Tree<T> {
    root: Option<Rc<RefCell<Node<T>>>>,
}

#[derive(Debug)]
struct Node<T> {
    value: T,
    left: Option<Rc<RefCell<Node<T>>>>,
    right: Option<Rc<RefCell<Node<T>>>>,
}

impl<T: Ord + Debug> Tree<T> {
    #[inline]
    fn new() -> Self {
        Tree { root: None }
    }

    fn insert(&mut self, value: T) {
        match &mut self.root {
            None => self.root = Some(Rc::new(RefCell::new(Node::new(value)))),
            Some(node) => node.borrow_mut().insert(value),
        }
    }

    fn print(&self) {
        match &self.root {
            None => println!("None"),
            Some(node) => node.borrow().print(),
        }
    }

    fn find(&self, value: T) -> Option<Ref<'_, Node<T>>> {
        match &self.root {
            None => None,
            Some(node) => node.borrow().find(value),
        }
    }
}

impl<T: Ord + Debug> Node<T> {
    #[inline]
    fn new(value: T) -> Self {
        Node {
            value,
            left: None,
            right: None,
        }
    }

    fn insert(&mut self, value: T) {
        match value.cmp(&self.value) {
            std::cmp::Ordering::Equal => {
                println!("Found {:?} already exists, omit the insertion", value);
            }
            // 修正：值更大时插入右子树
            std::cmp::Ordering::Greater => match &mut self.right {
                None => self.right = Some(Rc::new(RefCell::new(Node::new(value)))),
                Some(node) => node.borrow_mut().insert(value),
            },
            // 修正：值更小时插入左子树
            std::cmp::Ordering::Less => match &mut self.left {
                None => self.left = Some(Rc::new(RefCell::new(Node::new(value)))),
                Some(node) => node.borrow_mut().insert(value),
            },
        }
    }

    fn print(&self) {
        if let Some(node) = &self.left {
            node.borrow().print();
        } else {
            println!("None");
        }
        println!("{:?}", self.value);
        if let Some(node) = &self.right {
            node.borrow().print();
        } else {
            println!("None");
        }
    }

    fn find(&self, value: T) -> Option<Ref<'_, Node<T>>> {
        match value.cmp(&self.value) {
            std::cmp::Ordering::Equal => Some(Ref::map(Ref::from(self), |n| n)),
            // 修正：值更大时去右子树查找
            std::cmp::Ordering::Greater => match &self.right {
                None => None,
                Some(node) => node.borrow().find(value),
            },
            // 修正：值更小时去左子树查找
            std::cmp::Ordering::Less => match &self.left {
                None => None,
                Some(node) => node.borrow().find(value),
            },
        }
    }
}

// unit tests
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_insert() {
        let mut tree = Tree::new();
        tree.insert(1);
        tree.insert(2);
    }

    #[test]
    fn test_find() {
        let mut tree = Tree::new();
        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(1);
        tree.insert(2);
        let found = tree.find(1).unwrap();
        println!("{:?}", found);
        tree.print()
    }

    #[test]
    fn test_print() {
        let mut tree = Tree::new();
        tree.insert(3);
        tree.insert(4);
        tree.insert(9);
        tree.insert(3);
        tree.insert(2);
        tree.insert(3);
        tree.print()
    }
}

关键修正点 #

1. 返回类型调整：将Option<&Node<T>>改为Option<Ref<'_, Node<T>>>，利用Ref管理RefCell的借用生命周期，避免悬空引用。
2. 二叉搜索树方向修正：
   • 目标值大于当前节点值时，去右子树查找/插入
   • 目标值小于当前节点值时，去左子树查找/插入
3. 当前节点返回方式：使用Ref::map(Ref::from(self), |n| n)创建指向当前节点的Ref，匹配返回类型要求。

内容的提问来源于stack exchange，提问作者TomZz