Ruby：以树形表示变换平面数组

发布时间：2020-12-17 02:14:31 所属栏目：百科来源：网络整理

导读：我正在尝试编写一个函数来将带有路径信息的平面数组转换为该数组的树形表示. 目标是转换如下数组： [{ :name = "a",:path = [ 'a' ] },{ :name = "b",:path = [ 'a','b' ] },{ :name = "c",'b','c' ] },{ :name = "d",'d' ] },{ :name = "e",:path = [ 'e' ]

我正在尝试编写一个函数来将带有路径信息的平面数组转换为该数组的树形表示.

目标是转换如下数组：

[
{ :name => "a",:path => [ 'a' ] },{ :name => "b",:path => [ 'a','b' ] },{ :name => "c",'b','c' ] },{ :name => "d",'d' ] },{ :name => "e",:path => [ 'e' ] }
]

像这样：

[{:node=>{:name=>"a",:path=>["a"]},:children=>
   [{:node=>{:name=>"b",:path=>["a","b"]},:children=>
      [{:node=>{:name=>"c","b","c"]},:children=>[]}]},{:node=>{:name=>"d","d"]},{:node=>{:name=>"e",:path=>["e"]},:children=>[]}]

我得到的最接近的结果是使用以下代码：

class Tree

  def initialize
    @root = { :node => nil,:children => [ ] } 
  end 

  def from_array( array )
    array.inject(self) { |tree,node| tree.add(node) }
    @root[:children]
  end 

  def add(node)
    recursive_add(@root,node[:path].dup,node)
    self
  end 

  private

  def recursive_add(parent,path,node)
    if(path.empty?)
      parent[:node] = node
      return
    end 
    current_path = path.shift
    children_nodes = parent[:children].find { |child| child[:node][:path].last == current_path } 
    unless children_nodes
      children_nodes = { :node => nil,:children => [ ] } 
      parent[:children].push children_nodes
    end 
    recursive_add(children_nodes,node)
  end 
end

flat = [ 
  { :name => "a",:path => [ 'e' ] } 
]

require 'pp'
pp Tree.new.from_array( flat )

但它非常冗长,我觉得它对于非常大的集合可能不是很有效.

在ruby中实现这一目标的最简洁,最有效的方法是什么？

解决方法

这是我的尝试.

array = [
{ :name => "a",:path => [ 'e' ] }
]

array
.sort_by{|h| -h[:path].length}
.map{|h| {node: h,children: []}}
.tap{|array| 
  while array.first[:node][:path].length > 1
    child = array.shift
    array
    .find{|h| h[:node][:name] == child[:node][:path][-2]}[:children]
    .push(child)
  end
}

# => [
  {:node=>{:name=>"e",:children=>[]},{:node=>{:name=>"a",:children=>[
    {:node=>{:name=>"d",{:node=>{:name=>"b",:children=>[
      {:node=>{:name=>"c",:children=>[]}
    ]}
  ]}
]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!