Rust试图通过禁止可能不安全的操作来确保内存安全。由于此分析在编译时执行，因此编译器只能推理已知为安全的一部分操作。
在Rust中，您可以轻松地存储父节点的引用（通过借用父节点，从而防止变异）或子节点列表（通过拥有它们，这给了您更多的自由），但不能同时拥有两者（不使用unsafe的情况下）。这对于您的addNode实现尤其有问题，因为它需要对给定节点的父节点进行可变访问。但是，如果将parent指针存储为可变引用，则由于特定对象只能使用单个可变引用，因此访问父节点的唯一方法是通过子节点，并且您只能拥有单个子节点，否则您将拥有两个可变引用到同一父节点。
如果您想避免不安全的代码，有许多替代方案，但它们都需要做出一些牺牲。
最简单的解决方案是直接删除
parent字段。在遍历树时，我们可以定义一个单独的数据结构来记录节点的父节点，而不是将其存储在节点本身中。
首先，让我们定义
Node:
#[derive(Debug)]
struct Node<T> {
data: T,
children: Vec<Node<T>>,
}
impl<T> Node<T> {
fn new(data: T) -> Node<T> {
Node { data: data, children: vec![] }
}
fn add_child(&mut self, child: Node<T>) {
self.children.push(child);
}
}
我添加了一个data字段，因为树节点没有数据是不太有用的！
现在让我们定义另一个结构体来跟踪我们导航时的父节点：
#[derive(Debug)]
struct NavigableNode<'a, T: 'a> {
node: &'a Node<T>,
parent: Option<&'a NavigableNode<'a, T>>,
}
impl<'a, T> NavigableNode<'a, T> {
fn child(&self, index: usize) -> NavigableNode<T> {
NavigableNode {
node: &self.node.children[index],
parent: Some(self)
}
}
}
impl<T> Node<T> {
fn navigate<'a>(&'a self) -> NavigableNode<T> {
NavigableNode { node: self, parent: None }
}
}
如果您在导航树时不需要改变树的结构，并且可以保留父NavigableNode对象（这对于递归算法很有效，但如果您想将NavigableNode存储在其他数据结构中并保留它，则效果不佳），则此解决方案可以很好地工作。使用除了借用指针之外的其他东西来存储父节点可以减轻第二个限制；如果您希望获得最大的通用性，则可以使用Borrow trait来允许直接值、借用指针、Box、Rc等。
现在，让我们谈谈
拉链。在函数式编程中，拉链用于“聚焦”于数据结构（列表、树、映射等）的特定元素，以便访问该元素需要恒定时间，同时仍保留该数据结构的所有数据。如果您需要在导航期间对树进行
变异，同时保留向上导航的能力，则可以将树转换为拉链，并通过拉链执行修改。
以下是如何为上面定义的
Node实现拉链：
#[derive(Debug)]
struct NodeZipper<T> {
node: Node<T>,
parent: Option<Box<NodeZipper<T>>>,
index_in_parent: usize,
}
impl<T> NodeZipper<T> {
fn child(mut self, index: usize) -> NodeZipper<T> {
let child = self.node.children.swap_remove(index);
NodeZipper {
node: child,
parent: Some(Box::new(self)),
index_in_parent: index,
}
}
fn parent(self) -> NodeZipper<T> {
let NodeZipper { node, parent, index_in_parent } = self;
let NodeZipper {
node: mut parent_node,
parent: parent_parent,
index_in_parent: parent_index_in_parent,
} = *parent.unwrap();
parent_node.children.push(node);
let len = parent_node.children.len();
parent_node.children.swap(index_in_parent, len - 1);
NodeZipper {
node: parent_node,
parent: parent_parent,
index_in_parent: parent_index_in_parent,
}
}
fn finish(mut self) -> Node<T> {
while let Some(_) = self.parent {
self = self.parent();
}
self.node
}
}
impl<T> Node<T> {
fn zipper(self) -> NodeZipper<T> {
NodeZipper { node: self, parent: None, index_in_parent: 0 }
}
}
要使用这个Zipper，您需要拥有树的根节点所有权。通过拥有节点的所有权，Zipper可以移动东西以避免复制或克隆节点。当我们移动Zipper时，实际上是放弃旧的Zipper并创建一个新的（尽管我们也可以通过突变
self来完成，但我认为那样更清晰，而且它还可以让您链接方法调用）。
如果以上选项不令人满意，您绝对必须在节点中存储父节点，则下一个最佳选项是使用
Rc<RefCell<Node<T>>> 来引用父节点和
Weak<RefCell<Node<T>>> 来引用子节点。
Rc 允许共享所有权，但增加了运行时引用计数的开销。
RefCell 允许内部可变性，但增加了运行时活动借用的跟踪开销。
Weak 类似于
Rc，但它不会增加引用计数；这是用来打破循环引用的，否则将防止引用计数降为零，导致内存泄漏。
请参见 DK.'s 的答案，其中使用了
Rc、
Weak 和
RefCell 实现。
std::vector<std::unique_ptr<Node>> children;？此外，为什么析构函数要声明为虚函数？这是一个接口吗？ - Matthieu M.