我有一个由 parent_id 和 child_id 组成的分支模型。我想获得一组父/子关系,而无需为每个父子查询其子项。
对于这张表:
Parent_id | Child_id
1 | 2
1 | 6
1 | 9
2 | 3
3 | 10
4 | 7
我想得到 1 的 child ,他的 child 的 child 是这样的:
{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],[1,9],[2,3],[3,10],[4,7]]
puts build_tree(1, edges)
# {2=>{3=>{10=>{}}}, 6=>{}, 9=>{}}
关于ruby - 树到数组算法(Ruby),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8028211/