树到数组算法(Ruby)

Question

我有一个由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}

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

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

Answer 1

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

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],[1,9],[2,3],[3,10],[4,7]]
puts build_tree(1, edges)
# {2=>{3=>{10=>{}}}, 6=>{}, 9=>{}}