Алгоритм разбора плоского дерева на неплоское дерево

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

Может ли кто-нибудь указать мне правильное направление? Я ищу шаги (например, создать ассоциативный массив; цикл по массиву в поисках х; и т. Д.).

Я использую 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" # 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)

Плюсы:

• как и должно быть

Минусы:

• Ruby потерпит неудачу , если у нас будет > = 3000 узлов (это происходит из-за того, что у 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)

Плюсы:

• Рубиновый стиль

Минусы:

• мы модифицируем объект Я, это недостаточно хорошо.

Результат обоих способов:

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

Резюме

Для производства лучше использовать второй способ, возможно, есть более оптимальный способ реализовать его.
Надеюсь, что написанное будет полезно

Answer 3

1. Сборка стека и заполнение его корневым элементом.
2. Пока (в стеке есть элементы):
3. Вытащите элемент из стека и добавьте его туда, где он находится в дереве.
4. Найдите все дочерние элементы этого элемента в вашем массиве и поместите их в стек.

Чтобы добавить элемент в дерево (шаг 3), вам нужно сначала найти их родителя. Древовидная структура данных должна позволять вам делать это довольно быстро, или вы можете использовать словарь, который содержит узлы дерева, проиндексированные по id.

Если вы упомянули, на каком языке вы используете, может быть предложено более конкретное решение.

Answer 4

Вот несколько изменений, которые мне пришлось внести в ответ @ daniel-beardsley, чтобы он работал на меня.

1) Так как я начинал с отношения activeRecord, я начал с as_json для преобразования в хеш. Обратите внимание, что все ключи были строками, а не символами.

2) в моем случае родительские элементы имели родительское значение ноль, а не 0.

3) Я получил ошибку компиляции в выражении «continue», поэтому я изменил это на «next» ( может кто-нибудь объяснить это мне - возможно, это была опечатка @ 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]