在没有宝石的数组格式的父母孩子的红宝石树结构？

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_ids指向树中的事物.
3. 您可以一次遍历数组并以两种方式跟踪条目:by :id和by :parent_id.

首先是由哈希代表的树:

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

我们将从根到叶子,所以我们只对父/子关系的子端感兴趣,因此:children数组在默认值中.

然后是一个简单的迭代,填充:titles并: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声明.