Rust使用Rc指针实现树结构遇可变性问题与E0507编译报错

你的方法签名确实存在错误，这是编译失败的直接原因：

• add_to_children、set_as_parent两个方法的接收者定义为mut self，代表调用方法时会获取当前Node实例的所有权。但你调用方法时拿到的是&mut Rc<Node>类型，Rc不允许把内部包裹的值直接move出来，自然会触发cannot move out of an Rc的编译错误。
• 除此之外你的设计还有一个逻辑漏洞：Rc默认提供的是不可变共享访问，就算修正了方法签名，你也没法直接修改Rc内部Node的parent、children字段，必须搭配内部可变性类型才能修改内部状态。

注意：父子节点双向持有对方的Rc强引用会形成循环引用，两个节点的引用计数永远无法降到0，会造成内存泄漏，生产环境尽量避免这种写法。

用Rc<RefCell<Node>>包裹节点，通过RefCell提供内部可变性，同时把方法接收者改成可变借用&mut self（借用实例而非拿走所有权），代码如下：

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
enum Expr {
    B(i128),
    A(Rc<Expr>, Rc<Expr>),
    O(Rc<Expr>, Rc<Expr>),
}

#[derive(Debug)]
struct Node {
    data: Rc<Expr>,
    parent: Option<Rc<Node>>,
    children: Vec<Rc<Node>>,
}

impl Node {
    // 构造方法直接返回包裹了Rc<RefCell<>>的节点，方便后续操作
    fn new(data: Rc<Expr>) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Self {
            data,
            parent: None,
            children: Vec::new(),
        }))
    }

    // 接收者改为&mut self，可变借用当前实例，不拿走所有权
    fn add_to_children(&mut self, node: Rc<Node>) {
        self.children.push(node);
    }

    fn set_as_parent(&mut self, node: Rc<Node>) {
        self.parent = Some(node);
    }

    fn link_parent_child(parent: &Rc<RefCell<Node>>, child: &Rc<RefCell<Node>>) {
        // 通过borrow_mut()获取内部节点的可变引用，再调用方法
        parent.borrow_mut().add_to_children(Rc::clone(child));
        child.borrow_mut().set_as_parent(Rc::clone(parent));
    }
}

fn main() {
    let expr1 = Rc::new(Expr::B(1));
    let expr2 = Rc::new(Expr::B(2));
    let parent_node = Node::new(expr1);
    let child_node = Node::new(expr2);

    Node::link_parent_child(&parent_node, &child_node);

    println!("父节点子节点数：{}", parent_node.borrow().children.len());
    println!("子节点是否绑定父节点：{}", child_node.borrow().parent.is_some());
}

如果追求性能和内存安全，更推荐以下两种实现方式：

• 弱引用破环：父节点持有子节点的Rc<RefCell<Node>>强引用，子节点持有父节点的Weak<RefCell<Node>>弱引用。弱引用不增加强引用计数，不会形成循环引用，需要访问父节点时再通过upgrade()方法尝试获取强引用即可，是Rust生态实现双向关联结构的通用做法。
• 索引式存储：把所有节点统一存在一个Vec<Node>里，父子关系直接用usize类型的下标索引记录。这种方案没有引用计数的运行时开销，也没有RefCell的运行时借用检查开销，性能最好，也不会出现循环引用问题，适合节点数量可控、结构不需要频繁共享的场景。

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