红宝石的树形结构,其父级子级为无宝石的数组格式?(tree structure in ruby with parent child in array format without gems?)

3 IT屋

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?

解决方案

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.

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



  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为



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



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


如何生成上述答复?


解决方案

这比您想象的要容易,您只需要了解一些简单的事情即可:




  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做| n | 
id,parent_id = n.values_at(:id,:parent_id)
tree [id] [:title] = n [:title]
tree [parent_id] [:children] .push (tree [id])
结束


请注意,节点(包括父节点)是由 tree 的 default_proc 第一次自动创建的,因此节点在<$ c $中的顺序c> arr 无关紧要。



这使我们只剩下 tree 中的树了键是:id s(包括 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 => []}})做| n,tree | 
#...
结束


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


本文地址:IT屋 » 红宝石的树形结构,其父级子级为无宝石的数组格式?