ruby-on-rails - ruby 中的树结构与父子数组格式没有 gem ？

Question

我有一个数组，其中包含这样的项目列表

arr = [
  {:id=>1,  :title=>"A",      :parent_id=>nil}, 
  {:id=>2,  :title=>"B",      :parent_id=>nil},
  {:id=>3,  :title=>"A1",     :parent_id=>1}, 
  {:id=>4,  :title=>"A2",     :parent_id=>1},
  {:id=>5,  :title=>"A11",    :parent_id=>3}, 
  {:id=>6,  :title=>"12",     :parent_id=>3},
  {:id=>7,  :title=>"A2=121", :parent_id=>6}, 
  {:id=>8,  :title=>"A21",    :parent_id=>4},
  {:id=>9,  :title=>"B11",    :parent_id=>2}, 
  {:id=>10, :title=>"B12",    :parent_id=>2},

... ]

如果 parent_id 为 nil 那么它应该是父节点，如果 parent_id 不为 nil 那么它应该在特定的父节点下。

基于 id 和 parent_id，我想提供这样的响应:

-A
  -A1
    -A11
    -A12
      -A123
  -A2
    -A21
-B
  -B1
    -B11
    -B12

我如何生成上述响应？

Answer 1

这比您想象的要容易，您只需要了解几件简单的事情:

1. nil 是一个完全有效的哈希键。
2. 您可以使用 nil 作为树的虚拟根，以便所有 :parent_id 都指向树中的对象。
3. 您可以同时通过两种方式遍历数组和跟踪条目:通过 :id 和通过 :parent_id。

首先是一个哈希表示的树:

tree = Hash.new { |h,k| h[k] = { :title => nil, :children => [ ] } }

我们将从根到叶，因此我们只对父/子关系的子端感兴趣，因此 :children 数组的默认值。

然后是一个简单的迭代，填充 :title 和 :children:

arr.each do |n|
  id, parent_id = n.values_at(:id, :parent_id)
  tree[id][:title] = n[:title]
  tree[parent_id][:children].push(tree[id])
end

请注意，节点(包括父节点)在第一次出现时由 tree 的 default_proc 自动创建，因此 中的节点顺序arr 是无关紧要的。

这给我们留下了 tree 中的树，其中键是 :id(包括 nil 键处的虚拟根)和这些值是从该点开始的子树。

然后如果你查看 tree[nil][:children] 剥离虚拟根，你会看到这个:

[
  { :title => "A", :children => [
    { :title => "A1", :children => [
      { :title => "A11", :children => [] },
      { :title => "12", :children => [
        { :title => "A2=121", :children => [] }  
      ] }
    ] },
    { :title => "A2", :children => [
      { :title => "A21", :children => [] }   
    ] }
  ] },
  { :title => "B", :children => [
    { :title => "B11", :children => [] },
    { :title => "B12", :children => [] }
  ] }
]

这正是您正在寻找的结构，您应该能够从那里获取它。这与您的示例响应不匹配，但那是因为您的示例 arr 也不匹配。

你也可以说:

tree = arr.each_with_object(Hash.new { |h,k| h[k] = { :title => nil, :children => [ ] } }) do |n, tree|
  #...
end

如果您更喜欢嘈杂的第一行而不是单独的 tree 声明。