tree structure in ruby with parent child in array

问题:

I have a array which have list of item like this

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},

... ]

If parent_id is nil then its should be the parent node, if parent_id is not nil then it should comes under the particular parent.

Based on id and parent_id, I want to provide a response like this:

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

How could I generate a responds mentioned above?

回答1:

This is easier than you think, you just need to realize a couple simple things:

1. nil is a perfectly valid Hash key.
2. You can use nil as a virtual root for your tree so that all the :parent_ids point at things in your tree.
3. You can iterate through the array and track entries in two ways at once: by :id and by :parent_id.

First a tree represented by a Hash:

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

We're going to be going from the root to the leaves so we're only interested in the children side of the parent/child relationship, hence the :children array in the default values.

Then a simple iteration that fills in the :titles and :children as it goes:

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

Note that the nodes (including the parent nodes) are automatically created by tree's default_proc the first time they're seen so the node order in arr is irrelevant.

That leaves us with the tree in tree where the keys are :ids (including the virtual root at the nil key) and the values are subtrees from that point.

Then if you look at tree[nil][:children] to peel off the virtual root, you'll see this:

[
  { :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 => [] }
  ] }
]

and that has exactly the structure you're looking for and you should be able to take it from there. That doesn't match your sample response but that's because your sample arr doesn't either.

You could also say:

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

if you preferred that rather noisy first line to a separate tree declaration.

回答2:

Some thing like this will work:

parents = arr.select{|hash| hash[:parent_id] == nil }
parents.each {|hash| print_children hash, arr, "-"}

def print_children(hash, arr, spaces)
  puts spaces + hash[:title]
  spaces = ' ' + spaces
  children = arr.select{|all_hash| all_hash[:parent_id] == hash[:id] }
  children.each { |child_hash| print_children child_hash, arr, spaces }
end