Учитывая «древовидную» структуру данных, распечатайте все пути от листа к корню

#computer-science

#информатика

Вопрос:

Может ли кто-нибудь направить меня в правильном направлении, пожалуйста, я не понимаю, как вернуть результаты от листа к корню

 tree = {
    "name": "root",
    "children": [
        {
            "name": "child1",
            "children": [
                {
                    "name": "grand_child1",
                    "children": []
                },
                {
                    "name": "grand_child2",
                    "children": []
                }
            ]
        },
        {
            "name": "child2",
            "children": []
        }
    ]
}
 

Редактировать:
Решением должен быть алгоритм, поскольку при увеличении глубины дерева он все равно должен работать

Комментарии:

1. Алгоритм, который вы ищете, — это «рекурсивный спуск» — вы хотите просмотреть children элемент каждого значения на карте, затем рекурсивно оценивать дочерние элементы этого объекта, пока не найдете объект с пустым списком дочерних элементов. Это ваш конечный узел.

Ответ №1:

Вы могли бы использовать рекурсию, например:

 def traverse(node, *names, amp;block)
  names.unshift(node[:name])

  yield *names and return if node[:children].empty?

  node[:children].each { |child| traverse(child, *names, amp;block) }
end
 

Метод работает на одном узле. При каждом вызове он добавляет имя узла в список собранных names (изначально пустой). Затем он снова вызывает себя для каждого дочернего элемента, передавая names . Если у узла нет дочерних элементов, он уступает names данному блоку. (который тоже передается)

Использование:

 traverse(tree) do |*names|
  p name: names
end
 

Вывод:

 {:name=>["grand_child1", "child1", "root"]}
{:name=>["grand_child2", "child1", "root"]}
{:name=>["child2", "root"]}
 

Комментарии:

1. Прекрасно! Читатели: обратите внимание, что это yield *names может быть выражено block.call *names .

Ответ №2:

 def explore_tree(tree, names=[])
  names = [tree[:name]]   names
  if tree[:children].empty?
    p names
  else
    tree[:children].each { |child| explore_tree(child, names) }
  end
end
 
 explore_tree(tree)
 

отображает

 ["grand_child1", "child1", "root"]
["grand_child2", "child1", "root"]
["child2", "root"]
 

Комментарии:

1. Обычно я даю некоторые объяснения, но в данном случае это не кажется необходимым.

Ответ №3:

 def get_paths(hash)
  # Stop method and return name if name is address
  return hash[:name] if hash[:children].empty?
  paths = [] # Declaring path variable
  # Inspecting children
  hash[:children].each do |child|
    child_paths = get_paths(child)
    if child_paths.is_a? String
      paths << [child_paths, hash[:name]]
    else
      child_paths.each { |path| path << hash[:name] }
      paths  = child_paths
    end
  end
  paths # Return paths
end

p *get_paths(tree).map { |path| path.to_s[1..-2] }
# => "grand_child1", "child1,", "root"
# => "grand_child2", "child1,", "root"
# => "child2", "root"

 

Комментарии:

1. Ваше решение будет работать, только если вы знаете глубину дерева, допустим, глубина неизвестна

2. Я не понимаю вашего комментария. Разве вы не видели, что метод работает с разной глубиной?

3. извините, я имел в виду, что ваше решение зависит от жестко заданного адреса,

4. Спасибо, Кьяра, ценю это