将扁平树解析为非扁平树的算法

Question

我有以下扁平树：

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，因此我可以使用面向对象的语言功能。

Answer 1

在 ruby​​ 中，您应该能够使用哈希在线性时间 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]

Answer 2

我已经用递归和非递归研究了这个问题。我在这里放置了 2 个变体：
"parend_id" = "head_id" # 对于这些示例

递归：

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 个节点

非递归，有循环：

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​​ 风格

缺点：

• 我们修改了 self 对象，这还不够好。

两种方式的结果都是：

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

Resume

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

Answer 3

1. 构建一个堆栈并用根元素填充它。
2. While（堆栈中有元素）：
3. 从堆栈中弹出一个元素并将其添加到树中它所属的位置。
4. 在数组中找到该元素的所有子元素并将它们推入堆栈。

要将元素添加到树中（步骤 3），您需要首先找到它们的父元素。树数据结构应该允许您很快地做到这一点，或者您可以使用包含按 id 索引的树节点的字典。

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

Answer 4

以下是我必须对 @daniel-beardsley 的回复进行的一些更改，以使其对我有用。

1）由于我是从 activeRecord 关系开始的，所以我首先执行“as_json”来转换为哈希值。请注意，所有键都是字符串，而不是符号。

2) 在我的例子中，没有父项的项的父值为 nil 而不是 0。

3) 我在“继续”表达式上遇到编译错误，所以我将其更改为“下一个”（有人可以向我解释一下吗< /strong> - 也许这是 @daniel-beardsley 在转换为 ruby​​ 时出现的拼写错误？）

4）我在删除父项的项目时遇到了一些崩溃。我添加了代码来忽略这些 - 如果您愿意，您也可以将其放在根目录中

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]