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

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]