ruby – 将平面树解析为非平面树的算法

发布时间：2020-12-17 01:53:59 所属栏目：百科来源：网络整理

导读：我有以下平树： id name parent_id is_directory===========================================================50 app 0 131 controllers 50 111 application_controller.rb 31 046 models 50 112 test_controller.rb 31 031 test.rb 46 0 我试图找出一个算

我有以下平树：

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,children: [{
      id: 31,name: test.rb,is_directory: false
    }]
  }]
}]

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

我正在使用Ruby,因此我可以使用面向对象的语言功能.

解决方法

在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]

（编辑：李大同）

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