如何使用Rust在树形结构中为单个节点拥有多个引用

Question

如何使用Rust在树形结构中为单个节点拥有多个引用

4

尝试使用以下结构在Rust中创建一棵树：

pub struct Node{
    pub children: Vec<Box<Node>>,
    pub parent: Option<Box<Node>>,
    pub value: f32,
    //.....
}

构建新节点时，使用以下功能：

pub fn build_node(parent: Option<Box<Node>>)-> Node{
    Node{
        children: vec![],
        parent,
        value: 0.0,

    }
}

当尝试添加节点时，例如：

let mut root_nd = tree::build_node(None, 5, state);
let mut next_nd = tree::build_node(Some(Box::new(root_nd)), 2);
root_nd.children.push(Box::new(next_nd));

由于我借用了root_nd，然后尝试将next_nd添加到root.children列表中，因此会出现错误。即使没有这个错误，我仍然需要在将其添加到root_nd的子项之后引用next_nd。我知道在 Rust 中不可能同时拥有同一元素的多个可变引用。那么问题是如何在 Rust 中制作具有双向引用的类似树状数据结构？在我的脑海中，这是一个冲突，因为 Rust 不希望有多个引用，但是我需要树中间的一个节点被他的父节点和子节点都引用。

- Miguel

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Psidom · Accepted Answer

最近我一直在使用Rust处理树结构。要在Rust中处理树结构，你需要使用 Rc（单线程引用计数指针）以便拥有多个所有权。同时还需要 RefCell 来实现内部可变性，因为编译器不允许有多个可变引用。有了 Rc 和 RefCell，你可以定义下面这样的 TreeNode：

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

pub struct TreeNode {
    pub children: Vec<Rc<RefCell<TreeNode>>>,
    pub parent: Option<Rc<RefCell<TreeNode>>>,
    pub value: f32,
}

下面是一种创建相互引用的两个节点的方法：

impl TreeNode {
  #[inline]
  pub fn new(value: f32) -> Self {
    TreeNode {
      value,
      children: vec![],
      parent: None
    }
  }
}

let mut root_nd = Rc::new(RefCell::new(TreeNode::new(5.0)));
let mut child_nd = Rc::new(RefCell::new(TreeNode::new(2.0)));

child_nd.borrow_mut().parent = Some(root_nd.clone());  // use Rc::clone to create a new reference to root_nd
root_nd.borrow_mut().children.push(child_nd.clone());

由于我们使用 Rc::clone 来创建对节点的新引用，root_nd 和 child_nd 没有被消耗，后续程序仍然可以访问它们。

更多关于 Rust 中树的示例: