转化与父母标识结构的列表为树木

我从给我的形式结构的载体的数据库中提取数据集的列表：转化与父母标识结构的列表为树木

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阅读有关车削recursiv Ë想法付诸迭代的代码表明，这样的实现是可能的，但我已经从困难这一问题采取的思路和这里应用它们。

有人能描述这种转变对Vec<Foo>一个Vec<Bar>的方法？我会对迭代或递归建议感到满意;当我自己尝试递归时，我在借用和引用时遇到了很多问题。

来源

2017-10-20 Geodesic

@trentcl：我很乐意与递归建议过，我只是有很多的问题与借入和引用，当我试图这条路线我自己。 – Geodesic

直线解决方案包括建立所有数据的图表和递归遍历它，从每个级别返回Bar并加以收集。有向图，使我们能够控制的节点ID（因为我们只是数字标识符） -

我们通过创建一个petgraph::DiGraphMap开始。如果一个节点有一个父节点，我们确保该节点存在于该图中，并从父节点向该子节点添加一条边。如果没有父母，我们知道这将是我们的顶级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每个孩子，他们的东西全部变成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。

来源

2017-10-20 17:51:11 Shepmaster

完美！正是我所追求的。感谢您将我介绍给petgraph，这无疑将在未来派上用场。 – Geodesic

转化与父母标识结构的列表为树木

回答

相关问题