ruby如何生成一个树形结构形式的数组？

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 那么它应该属于特定的 parent 。

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

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

我如何生成上述响应？

谢谢

Answer 1

您可以使用像 Closure_tree 这样的 gem :

hash_tree provides a method for rendering a subtree as an ordered nested hash:

Tag.hash_tree
#=> {a => {b => {c1 => {d1 => {}}, c2 => {d2 => {}}}, b2 => {}}}

或Ancestry :

Ancestry can arrange an entire subtree into nested hashes for easy navigation after retrieval from the database. TreeNode.arrange could for example return:

{ #<TreeNode id: 100018, name: "Stinky", ancestry: nil>
  => { #<TreeNode id: 100019, name: "Crunchy", ancestry: "100018">
    => { #<TreeNode id: 100020, name: "Squeeky", ancestry: "100018/100019">
      => {}
    }
  }
}

参见 https://www.ruby-toolbox.com/categories/Active_Record_Nesting对于其他 gem 。

更新

如果您必须在内存中执行此操作，那么这样的事情应该可行:

nested_hash = Hash[arr.map{|e| [e[:id], e.merge(children: [])]}]
nested_hash.each do |id, item|
  parent = nested_hash[item[:parent_id]]
  parent[:children] << item if parent
end
tree = nested_hash.select { |id, item| item[:parent_id].nil? }.values

require 'pp'
pp tree

输出

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