ruby - 将单级 JSON 邻接列表转换为嵌套的 JSON 树

Question

在 Rails 4 项目中，我有一个单级邻接表，它是从关系数据库构建到 JSON 对象中的。看起来像

{
    "6": {
        "children": [
            8,
            10,
            11
        ]
    },
    "8": {
        "children": [
            9,
            23,
            24
        ]
    },
    "9": {
        "children": [
            7
        ]
    },
    "10": {
        "children": [
            12,
            14
        ]
    ...
}

现在我想把它变成一个 JSON 结构，供 jsTree 使用，看起来像

{
   id: "6",
   children: [
            { id: "8", children: [ { id: "9", children: [{id: "7"}] }]
            { id: "10", children: [ { id: "12",...} {id: "14",...} ] }
 ...and so on
}

我在构建这种树时面临的问题是在 JSON 的嵌套级别上进行回溯。算法教科书中的示例不足以与我的经验相匹配，我的经验是通过将一些基本数据(如数字或字符串)插入堆栈来简单地处理回溯问题。

感谢任何有关构建此类树的实用方法的帮助。

Answer 1

假设有一个根元素(因为它是一棵树)，您可以使用非常短的递归方法来构建树:

def process(id, src)
  hash = src[id]
  return { id: id } if hash.nil? 
  children = hash['children']
  { id: id, children: children.map { |child_id| process(child_id.to_s, src) } }
end

# the 'list' argument is the hash you posted, '6' is the key of the root node
json = process('6', list)

# json value:
#
# {:id=>"6", :children=>[
#   {:id=>"8", :children=>[
#     {:id=>"9", :children=>[
#       {:id=>"7"}]}, 
#     {:id=>"23"}, 
#     {:id=>"24"}]}, 
#   {:id=>"10", :children=>[
#     {:id=>"12"}, 
#     {:id=>"14"}]}, 
#   {:id=>"11"}]}

我添加了 return { id: id } if hash.nil? 行，因为您的输入哈希不包含 child 7、11、12、14、23、24 的条目。如果他们的条目就像下面一样，您可以删除该行。

"7" => { "children" => [] },
"11" => { "children" => [] },
"12" => { "children" => [] },
"14" => { "children" => [] },
"23" => { "children" => [] },
"24" => { "children" => [] }

在那种情况下，该方法将产生 {:id=>"7", :children=>[]} 而不是 {:id=>"7"} 如果你愿意，你可以通过包含一个 children.empty? 检查来改变它，在这种情况下返回一个只有 :id 键的散列(就像我在hash.nil? 检查)。但是，就一致性而言，我可能更喜欢将 children 键作为值与一个空数组一起出现，而不是完全省略它。