用于将平面树解析为非平面树的算法

我有以下扁平树:

id name parent_id is_directory =========================================================== 50 app 0 1 31 controllers 50 1 11 application_controller.rb 31 0 46 models 50 1 12 test_controller.rb 31 0 31 test.rb 46 0 

我试图找出一个算法,将其纳入以下树结构:

 [{ id: 50, name: app, is_directory: true children: [{ id: 31, name: controllers, is_directory: true, children: [{ id: 11, name: application_controller.rb is_directory: false },{ id: 12, name: test_controller.rb, is_directory: false }], },{ id: 46, name: models, is_directory: true, children: [{ id: 31, name: test.rb, is_directory: false }] }] }] 

有人能指出我正确的方向吗? 我正在寻找步骤(例如,构建一个关联数组;遍历数组寻找x;等等)。

我正在使用Ruby,因此我可以使用面向对象的语言function。

在ruby中,您应该能够使用Hash 在线性时间O(n)中轻松完成。

 # Put all your nodes into a Hash keyed by id This assumes your objects are already Hashes object_hash = nodes.index_by {|node| node[:id]} object_hash[0] = {:root => true} # loop through each node, assigning them to their parents object_hash.each_value {|node| continue if node[:root] children = object_hash[node[:parent_id]][:children] ||= [] children << node } #then your should have the structure you want and you can ignore 'object_hash' variable tree = object_hash[0] 

我用递归和非递归的方式研究了这个问题。 我在这里放了两个变种:
"parend_id" = "head_id" # for those examples

Recursivly:

 require 'pp' nodes = [{"id"=>"1", "name"=>"User №1 Pupkin1", "head_id"=>nil}, {"id"=>"2", "name"=>"User №2 Pupkin2", "head_id"=>"1"}, {"id"=>"3", "name"=>"User №3 Pupkin3", "head_id"=>"2"}] def to_tree(nodes, head_id = nil) with_head, without_head = nodes.partition { |n| n['head_id'] == head_id } with_head.map do |node| node.merge('children' => to_tree(without_head, node['id'])) end end pp to_tree(nodes) 

优点:

  • 应该如此

缺点!:

  • 如果我们有> = 3000个节点, Ruby就会失败 (这是因为当ruby需要返回时,ruby对点(函数)有堆栈限制) 如果输出有“pp”,它将在> = 200个节点上失败

非recursevly,周期:

 require 'pp' nodes = [{"id"=>"1", "name"=>"User №1 Pupkin1", "head_id"=>nil}, {"id"=>"2", "name"=>"User №2 Pupkin2", "head_id"=>"1"}, {"id"=>"3", "name"=>"User №3 Pupkin3", "head_id"=>"2"}] def to_tree(data) data.each do |item| item['children'] = data.select { |_item| _item['head_id'] == item['id'] } end data.select { |item| item['head_id'] == nil } end pp to_tree(nodes) 

优点:

  • 更多ruby风格

缺点:

  • 我们修改自我对象,这是不够的好。

两种方式的结果是:

 [{"id"=>"1", "name"=>"User №1 Pupkin1", "head_id"=>nil, "children"=> [{"id"=>"2", "name"=>"User №2 Pupkin2", "head_id"=>"1", "children"=> [{"id"=>"3", "name"=>"User №3 Pupkin3", "head_id"=>"2", "children"=>[]}]}]}] 

恢复

对于生产来说,最好使用第二种方式,可能有一种更优化的方式来实现它。
希望写的将是有用的

  1. 构建一个堆栈并使用根元素填充它。
  2. 虽然(堆栈中有元素):
  3. 从堆栈中弹出一个元素并将其添加到树中所属的位置。
  4. 在数组中查找此元素的所有子元素并将它们推入堆栈。

要向树中添加元素(步骤3),您需要先找到它们的父元素。 树数据结构应该允许您非常快速地执行此操作,或者您可以使用包含由id索引的树节点的字典。

如果你提到你正在使用哪种语言,可以建议更具体的解决方案。

以下是我对@ daniel-beardsley的回应所做的一些改变,以使其适合我。

1)因为我从一个activeRecord关系开始,我开始做一个“as_json”转换为哈希。 请注意,所有键都是字符串,而不是符号。

2)在我的情况下,没有父母的项目的父级值为nil而不是0。

3)我在“继续”表达式上遇到了编译错误,因此我将其更改为“下一步”( 有人可以向我解释一下 – 也许这是@ daniel-beardsley转换为ruby时的拼写错误?)

4)我的父母被删除的项目发生了一些崩溃。 我添加了代码来忽略这些 – 如果你愿意的话,你也可以放在root上

 object_hash = myActiveRecordRelation.as_json.index_by {|node| node["id"]} object_hash[nil] = {:root => true} object_hash.each_value {|node| next if node[:root] next if node["parent_id"] && !object_hash[node["parent_id"]] # throw away orphans children = object_hash[node["parent_id"]][:children] ||= [] children << node } tree = object_hash[nil]