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

问题描述

我有以下扁平树:

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

我正试图找出一种算法，将其转换为以下树结构:

and I am trying to figure out an algorithm for getting this into the following tree structuree:

[{
  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；等等).

Can someone point me in the right direction? I'm looking for steps (eg. build an associative array; loop through the array looking for x; etc.).

我正在使用Ruby，所以我可以使用面向对象的语言功能.

I'm using Ruby, so I have object-oriented language features at my disposal.

推荐答案

在ruby中，您应该能够在线性时间O(n)中使用哈希轻松地完成此操作.

In ruby, you should be able to easily do it in linear time O(n) with a Hash.

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

这篇关于将平面树解析为非平面树的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！