ruby 中的树结构，父子采用数组格式，没有 gem？

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

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

我怎样才能生成上面提到的响应？

这比你想象的要容易，你只需要意识到一些简单的事情：

1. nil是一个完全有效的哈希键。
2. 您可以使用nil作为树的虚拟根，以便所有:parent_ids 指向树上的东西。
3. 您可以通过两种方式一次性遍历数组并跟踪条目：:id and by :parent_id.

首先是一棵由哈希表示的树：

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

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

然后一个简单的迭代填充:titles and :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's default_proc第一次看到它们时，节点顺序是arr是无关紧要的。

这让我们留下了树tree钥匙在哪里:ids（包括位于nilkey），值是从该点开始的子树。

然后如果你看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宣言。