Ruby：将平面数组转换为树形表示

Question

我想编写一个函数，将带有路径信息的扁平数组转换为该数组的树形表示。

目标是将以下形式的数组转换为树形结构：

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

将其转化为以下格式之一：

[{:node=>{:name=>"a", :path=>["a"]},
  :children=>
   [{:node=>{:name=>"b", :path=>["a", "b"]},
     :children=>
      [{:node=>{:name=>"c", :path=>["a", "b", "c"]}, :children=>[]}]},
    {:node=>{:name=>"d", :path=>["a", "d"]}, :children=>[]}]},
 {: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, path, node)
  end 
end

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

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

但这种方法非常冗长，我感觉对于非常大的数据集可能不太有效。

在Ruby中，最干净、最有效的方法是什么？

- Eric

---

即使你认为自己的作品不好，也要发布出来。 - Andrew Marshall

我认为你应该尝试简化你的树形结构。例如，如果名称是唯一的，那么可以使用名称作为键，以便您可以轻松搜索。 - ShadyKiller

你为什么要在树形表示中保留:path呢？这不是结构隐含的吗？ - Jonas Elfström

问题：1）为什么期望输出是一个只有一个元素的数组，这对树结构没有任何贡献。2）元素总是按顺序排列，因此路径是递增的吗？（就像您的输入示例一样） - tokland

尝试添加答案，但正如@ShadyKiller所说，期望的输出毫无意义，因为使用数组而不是哈希表，在每个分支处都需要执行搜索以定位节点。 - tokland

Answer 1

这是我的尝试。

array = [
{ :name => "a", :path => [ 'a' ] },
{ :name => "b", :path => [ 'a', 'b' ] },
{ :name => "c", :path => [ 'a', 'b', 'c' ] },
{ :name => "d", :path => [ 'a', 'd' ] },
{ :name => "e", :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", :path=>["e"]}, :children=>[]},
  {:node=>{:name=>"a", :path=>["a"]}, :children=>[
    {:node=>{:name=>"d", :path=>["a", "d"]}, :children=>[]},
    {:node=>{:name=>"b", :path=>["a", "b"]}, :children=>[
      {:node=>{:name=>"c", :path=>["a", "b", "c"]}, :children=>[]}
    ]}
  ]}
]

- sawa

---

Ruby 有时候感觉像魔法一样。干净而有效。非常感谢！ - Eric