树到数组算法(Ruby)

发布时间：2020-12-17 02:42:30 所属栏目：百科来源：网络整理

导读：我有一个由parent_id和child_id组成的分支模型.我希望获得一系列父/子关系,而不查询其子项的每个父项. 对于此表： Parent_id | Child_id1 | 21 | 61 | 92 | 33 | 104 | 7 我想要1个孩子,他的孩子的孩子是这样的： {2 = {3 = {10}},6,9} 没有查询每个父母的子

我有一个由parent_id和child_id组成的分支模型.我希望获得一系列父/子关系,而不查询其子项的每个父项.

对于此表：

Parent_id | Child_id
1         | 2
1         | 6
1         | 9
2         | 3
3         | 10
4         | 7

我想要1个孩子,他的孩子的孩子是这样的：

{2 => {3 => {10}},6,9}

没有查询每个父母的子女.

是否有一种算法可以有效地实现这一目标,还是需要通过每个父母？谢谢.

解决方法

一口气先搜索将完成这项工作.

def build_tree(i,edges)
    list = {}
    out_nodes = edges.select {|e| e[0] == i}.map {|e| e[1]}.uniq
    out_nodes.each {|n| list[n] = build_tree(n,edges)}
    list
end

edges = [[1,2],[1,6],9],[2,3],[3,10],[4,7]]
puts build_tree(1,edges)
# {2=>{3=>{10=>{}}},6=>{},9=>{}}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!