#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. Спасибо, Кьяра, ценю это