nested - 将具有父 ID 的结构列表转换为树列表

Question

我正在从数据库中提取数据集，该数据集为我提供了以下形式的结构向量:

struct Foo {
    id: i32,
    parent: Option<i32>,
    data: String,
}

我想将此数据的嵌套版本作为向量序列化并输出到 JSON:

struct Bar {
    id: i32,
    data: String,
    children: Option<Vec<Bar>>,
}

由于递归性质，我在执行此操作时遇到了一些问题。我可以使用迭代器向下一级解决问题，但当我想再次迭代同一向量时就会遇到困难。

例如 Vec<Foo> 上的方法它尝试将子 ID 嵌套到 HashMap 中:

fn build_tree(&self) -> HashMap<i32, Vec<i32>> {
    let mut tree = HashMap::new();
    for node in self.iter() {
        if let Some(parent) = node.parent {
            let leaf = tree.entry(parent).or_insert(Vec::new());
            leaf.push(node.id);
        }
    }
    tree
}

产量

{14: [15], 3: [14], 1: [2, 17], 2: [16, 18], 18: [19], 19: [20]}

但我需要的是更深层次的东西:

{3: [14: [15]], 1: [2: [16, 18: [19: [20]]], 17]}

通读this post关于将递归想法转化为迭代代码表明这种实现是可能的，但我很难从该问题中获取想法并在此处应用它们。

有人可以描述一种转换此方法的方法 Vec<Foo>到 Vec<Bar> ？我很乐意接受迭代或递归的建议；当我自己尝试递归时，我遇到了很多借用和引用问题。

Answer 1

直线解决方案涉及构建所有数据的图表并递归遍历它，返回 Bar从每个级别收集它们。

我们首先创建一个 petgraph::DiGraphMap — 一个有向图，允许我们控制节点 ID(因为我们只有数字标识符)。如果一个节点有父节点，我们确保该节点存在于图中，并添加从父节点到子节点的边。如果它没有父级，我们知道它将是我们的顶级 ID 之一，因此我们将其存放在一边以备后用:

let mut graph = DiGraphMap::new();
let mut top_level_ids = vec![];

for i in &input {
    graph.add_node(i.id);

    match i.parent {
        Some(parent_id) => {
            graph.add_node(parent_id);
            graph.add_edge(parent_id, i.id, ());
        }
        None => {
            top_level_ids.push(i.id);
        }
    }
}

接下来，我们迭代所有顶级 ID 并将它们转换为 Bar :

let result: Vec<_> = top_level_ids
    .into_iter()
    .map(|id| build_tree(&graph, id))
    .collect();

构建 Bar是问题的递归核心。我们构建另一个Bar对于每个 child ，将它们全部放入 Vec ，然后返回当前的Bar :

fn build_tree(graph: &DiGraphMap<i32, ()>, id: i32) -> Bar {
    let children = graph
        .neighbors(id)
        .map(|child_id| build_tree(graph, child_id))
        .collect();

    Bar { id, children }
}

此时，您有一个 Vec<Bar> 。这是读者的一个练习，如何正确编码以获得所需的 JSON 格式:-)。

The complete example .