如何使用 Rust 对树结构中的单个节点进行多个引用

Question

尝试使用以下结构创建一棵 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列表中，即使没有这个错误，我仍然需要next_nd在将其添加到 的子级后有一个参考root_nd。我知道在 Rust 中，同一个元素不可能同时拥有多个可变引用。所以问题是如何在 Rust 中创建一个具有双向引用的树状数据结构？在我看来，这是一个冲突，因为 Rust 不需要多个引用，但我需要树中间的一个节点被他的父节点和子节点引用。

Answer 1

最近我在 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 中的树的例子：

• leetcode 95 独特的二叉搜索树

• leetcode 94 二叉树中序遍历

• leetcode 100 是同一棵树