如何用安全的 Rust 表达相互递归的数据结构？

我正在尝试在 Rust 中实现类似场景图的数据结构。我想要一个与此 C++ 代码等效的代码safe Rust:

struct Node
{
    Node* parent; // should be mutable, and nullable (no parent)
    std::vector<Node*> child;

    virtual ~Node() 
    { 
        for(auto it = child.begin(); it != child.end(); ++it)
        {
            delete *it;
        }
    }

    void addNode(Node* newNode)
    {
        if (newNode->parent)
        {
            newNode->parent.child.erase(newNode->parent.child.find(newNode));
        }
        newNode->parent = this;
        child.push_back(newNode);
    }
}

我想要的属性：

• 父母拥有孩子的所有权
• 可以通过某种引用从外部访问节点
• 触动一个人的事件Node可能会改变整棵树

Rust 试图通过禁止您做可能不安全的事情来确保内存安全。由于此分析是在编译时执行的，因此编译器只能推断已知安全的操作子集。

在 Rust 中，你可以轻松存储either对父级的引用（通过借用父级，从而防止突变）or子节点列表（通过拥有它们，这给你更多的自由），但是not both（不使用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 https://doc.rust-lang.org/stable/std/borrow/trait.Borrow.html允许直接值、借用指针、Boxes, Rc's, etc.

现在，我们来谈谈zippers https://en.wikipedia.org/wiki/Zipper_%28data_structure%29。在函数式编程中，拉链用于“集中”数据结构的特定元素（列表、树、映射等），以便访问该元素需要恒定的时间，同时仍然保留该数据结构的所有数据。如果您需要导航树并且mutate它在导航过程中，同时保留向上导航树的能力，然后您可以将树变成拉链并通过拉链执行修改。

以下是我们如何实现拉链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> {
        // Remove the specified child from the node's children.
        // A NodeZipper shouldn't let its users inspect its parent,
        // since we mutate the parents
        // to move the focused nodes out of their list of children.
        // We use swap_remove() for efficiency.
        let child = self.node.children.swap_remove(index);

        // Return a new NodeZipper focused on the specified child.
        NodeZipper {
            node: child,
            parent: Some(Box::new(self)),
            index_in_parent: index,
        }
    }

    fn parent(self) -> NodeZipper<T> {
        // Destructure this NodeZipper
        let NodeZipper { node, parent, index_in_parent } = self;

        // Destructure the parent NodeZipper
        let NodeZipper {
            node: mut parent_node,
            parent: parent_parent,
            index_in_parent: parent_index_in_parent,
        } = *parent.unwrap();

        // Insert the node of this NodeZipper back in its parent.
        // Since we used swap_remove() to remove the child,
        // we need to do the opposite of that.
        parent_node.children.push(node);
        let len = parent_node.children.len();
        parent_node.children.swap(index_in_parent, len - 1);

        // Return a new NodeZipper focused on the parent.
        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 }
    }
}

要使用这个拉链，您需要拥有树的根节点的所有权。通过获得节点的所有权，拉链可以移动物体以避免复制或克隆节点。当我们移动拉链时，我们实际上会丢弃旧拉链并创建一个新拉链（尽管我们也可以通过变异来做到这一点）self，但我认为这样更清晰，而且它可以让您链接方法调用）。

如果上述选项不令人满意，并且您必须绝对将节点的父节点存储在节点中，那么下一个最佳选项是使用Rc<RefCell<Node<T>>>参考父母和Weak<RefCell<Node<T>>>给孩子们。Rc https://doc.rust-lang.org/stable/std/rc/struct.Rc.html启用共享所有权，但会增加运行时执行引用计数的开销。RefCell https://doc.rust-lang.org/stable/std/cell/struct.RefCell.html启用内部可变性，但会增加在运行时跟踪活动借用的开销。Weak https://doc.rust-lang.org/stable/std/rc/struct.Weak.html就好像Rc，但它不会增加引用计数；这用于中断引用循环，这将防止引用计数降至零，从而导致内存泄漏。参见DK的回答 https://stackoverflow.com/a/36168774/234590对于使用的实现Rc, Weak and RefCell.