rust - 在 Rust 中建模分层树

Question

我正在尝试为 UI 库构建结构模型，其中存在一个 ViewNode，它拥有一个 RenderNode，而 RenderNode 又拥有一个 LayoutNode。这些结构应同时形成三棵不同的树。 ViewTree、RenderTree 和 Layout 树。

有没有什么方法可以在不使用 Rc 的情况下对这种所有权进行建模？我不想使用 Rc<> 因为从我的角度来看所有权很明确，树不应该拥有他们的 child (除了 ViewNode)，包装器是所有者。每一层也应该能够被拉出到一个库中，我不想强​​迫库的用户使用 Rc<>。

下面是我想要做的但行不通的。也许我应该以不同的方式解决这个问题吗？

#[derive(Debug)]
struct LayoutNode<'a> {
    // .. Some fields
    children: Vec<&'a LayoutNode<'a>>,
}

#[derive(Debug)]
struct RenderNode<'a> {
    // .. Some fields
    layout_node: LayoutNode<'a>,
    children: Vec<&'a RenderNode<'a>>,
}

#[derive(Debug)]
struct ViewNode<'a> {
    // .. Some fields
    render_node: RenderNode<'a>,
    children: Vec<ViewNode<'a>>,
}

fn make_tree<'a>() -> ViewNode<'a> {
    let layout_child = LayoutNode { children: vec![] };
    let layout = LayoutNode { children: vec![&layout_child] };

    let render_child = RenderNode { layout_node: layout_child, children: vec![] };
    let render = RenderNode { layout_node: layout, children: vec![&render_child] };

    let view_child = ViewNode { render_node: render_child, children: vec![] };
    let view = ViewNode { render_node: render, children: vec![view_child] };

    view
}


fn main() {
    println!("{:?}", make_tree())
}

Answer 1

您可以使用使用索引而不是引用计数指针的内存空间。

使用 indextree举个例子:

pub struct NodeId {
    index: usize,
}

pub struct Node<T> {
    parent: Option<NodeId>,
    previous_sibling: Option<NodeId>,
    next_sibling: Option<NodeId>,
    first_child: Option<NodeId>,
    last_child: Option<NodeId>,
    removed: bool,

    /// The actual data which will be stored within the tree
    pub data: T,
}

pub struct Arena<T> {
    nodes: Vec<Node<T>>,
}

NodeId 结构是一个简单的整数索引。

节点包含对节点(parent、previous_sibling 等)关闭的引用，以便于遍历。

此方法的一个缺点是它与手动内存管理非常相似，因为您需要确保正确添加/删除节点以避免悬挂引用。 indextree有很多error checking由于这个原因在树中添加/删除节点时。

您可能还想看看 petgraph : 虽然这是一个 Graph 而不是 Tree，但您可以将其用作树。