Rust实现二叉搜索树递归insert方法的编译错误及相关疑问

我正在学习Rust，尝试将一段Java实现的二叉搜索树改写为Rust版本，写出的代码如下：

use std::cmp::Ordering;

// Node of this BST, the two generic types are key and value
struct Node<K:Ord, V> {
    key: K,
    value: V,
    left: Option<Box<Node<K, V>>>,
    right: Option<Box<Node<K, V>>>,
    number_of_nodes: i32,
}

impl<K: Ord, V> Node<K, V> {
    // Create a new node
    fn new(key: K, value: V, number_of_nodes: i32) -> Node<K, V>{
        Node {
            key,
            value,
            left: None,
            right: None,
            number_of_nodes,
        }
    }
}

struct BST<K: Ord ,V> {
    root: Option<Box<Node<K, V>>>,
}

impl<K: Ord, V> BST<K, V> {
    // Get the size of this BST
    fn size(&self) -> i32 {
        size(&self.root)
    }

    // Search for key. Update value if found, otherwise insert the new node
    fn put(&self, key: K, value: V) {
        self.root = put(&self.root, key, value)
    }
}

// Function for recursively get the size of a sub BST 
fn size<K: Ord, V>(node: &Option<Box<Node<K, V>>>) -> i32 {
    match node {
        Some(real_node) => real_node.number_of_nodes,
        None => 0,
    }
}

// Function for recursively put a new node to this BST
fn put<K: Ord, V>(node: &Option<Box<Node<K, V>>>, key: K, value: V) -> &Option<Box<Node<K, V>>>{
    match node {
        None => {
            let new_node = Some(Box::new(Node::new(key, value, 1)));
            return &new_node;
        },
        Some(real_node) => {
            match key.cmp(&real_node.key) {
                Ordering::Less => real_node.left = *put(&real_node.left, key, value),
                Ordering::Greater => real_node.right = *put(&real_node.right, key, value), 
                Ordering::Equal => real_node.value = value,
            }
            real_node.number_of_nodes = size(&real_node.right) + size(&real_node.left) + 1;
            node
        },
    }
}

这段代码无法编译，在self.root = put(&self.root, key, value)行出现错误：

mismatched types
expected enum 'Option<Box<Node<K, V>>>' found reference '&Option<Box<Node<K, V>>>'

我尝试修改&self为self或self.root为*self.root，但出现更多错误。我参考的Java实现如下：

public class BST<Key extends Comparable<Key>, Value>
{
    private Node root;              //root of BST

    private class Node
    {
        private Key key;            // key
        private Value val;          // associated value
        private Node right, left;   // left and right subtrees
        private int N;              // number of nodes in subtree

        public Node(Key key, Value val, int N)
        {
            this.key = key;
            this.val = val;
            this.N = N;
        }
    }

    // Returns the number of key-value pairs in this symbol table.
    public int size()
    {
        return size(root);
    }

    // Return number of key-value pairs in BST rooted at x
    private int size(Node x)
    {
        if (x == null) return 0;
        else return x.N;
    }

    public void put(Key key, Value val)
    {
        root = put(root, key, val);
    }

    private Node put(Node x, Key key, Value val)
    {
        if (x == null) return new Node(key, val, 1);
        int cmp = key.compareTo(x.key);
        if (cmp < 0) x.left = put(x.left, key, val);
        else if (cmp > 0) x.right = put(x.right, key, val);
        else x.val = val;
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
} 

我的问题如下：

1. 如何修复该类型不匹配错误？
2. 递归函数put的正确返回类型是&Option<Box<Node<K, V>>>还是Option<Box<Node<K, V>>>？二者有何区别？
3. 我当前的Java代码改写思路是否正确？rust-analyzer仅报告类型不匹配错误，但我不确定代码能否按预期运行，且我并未完全理解Rust中结构体/枚举引用的处理逻辑。

解答 #

1. 修复类型不匹配错误

核心问题是误用了引用和所有权，修改后的可编译代码如下：

use std::cmp::Ordering;

struct Node<K: Ord, V> {
    key: K,
    value: V,
    left: Option<Box<Node<K, V>>>,
    right: Option<Box<Node<K, V>>>,
    number_of_nodes: i32,
}

impl<K: Ord, V> Node<K, V> {
    fn new(key: K, value: V, number_of_nodes: i32) -> Node<K, V> {
        Node {
            key,
            value,
            left: None,
            right: None,
            number_of_nodes,
        }
    }
}

struct BST<K: Ord, V> {
    root: Option<Box<Node<K, V>>>,
}

impl<K: Ord, V> BST<K, V> {
    // 新增默认构造函数，用于创建空BST
    fn new() -> Self {
        BST { root: None }
    }

    fn size(&self) -> i32 {
        size(&self.root)
    }

    // 修改为&mut self，因为需要修改root字段的值
    fn put(&mut self, key: K, value: V) {
        self.root = put(self.root.take(), key, value);
    }
}

fn size<K: Ord, V>(node: &Option<Box<Node<K, V>>>) -> i32 {
    match node {
        Some(real_node) => real_node.number_of_nodes,
        None => 0,
    }
}

// 修改参数和返回类型为Option<Box<Node<K, V>>>，通过所有权转移实现递归修改
fn put<K: Ord, V>(mut node: Option<Box<Node<K, V>>>, key: K, value: V) -> Option<Box<Node<K, V>>> {
    match node {
        None => Some(Box::new(Node::new(key, value, 1))),
        Some(mut real_node) => {
            match key.cmp(&real_node.key) {
                Ordering::Less => real_node.left = put(real_node.left.take(), key, value),
                Ordering::Greater => real_node.right = put(real_node.right.take(), key, value),
                Ordering::Equal => real_node.value = value,
            }
            real_node.number_of_nodes = size(&real_node.right) + size(&real_node.left) + 1;
            Some(real_node)
        }
    }
}

关键修改点：

• 将BST::put的接收器改为&mut self，因为需要修改root字段的内容
• 递归put函数接收Option<Box<Node<K, V>>>（转移所有权），返回同样类型，避免悬垂引用
• 使用.take()方法取出Option中的值（转移所有权），传递给递归调用，再将返回值赋值回节点的left/right
• 匹配Some时使用mut real_node，获得节点的可变权限，允许修改内部字段

2. 递归put的正确返回类型

正确的返回类型是Option<Box<Node<K, V>>>，二者的核心区别：

• &Option<Box<Node<K, V>>>是引用类型，它指向已经存在的Option实例，但你在None分支创建的new_node是函数内的局部变量，返回它的引用会导致悬垂引用（函数结束后局部变量被销毁，引用指向无效内存），Rust的所有权系统会直接禁止这种行为。
• Option<Box<Node<K, V>>>是值类型，它直接持有节点的所有权，递归过程中可以通过转移所有权来传递节点，修改后再返回新的所有权，完全符合Rust的内存安全规则。

3. 改写思路的正确性

整体思路是正确的：你按照Java实现的递归逻辑，用Rust的Option<Box<Node>>对应Java的Node引用（null对应None），递归修改并返回节点的逻辑和Java版本一致。

但Rust的所有权系统和Java的垃圾回收模型差异很大：Java中可以随意修改对象的字段，而Rust要求必须拥有可变权限（mut）才能修改，同时不能返回指向局部变量的引用。之前的代码错误正是因为忽略了这些规则，误用了引用而非所有权转移。修改后的代码可以按照预期运行，实现和Java版本一致的二叉搜索树插入/更新逻辑。

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