Получить все узлы в дереве, которые являются дочерними по отношению к другому
У меня есть веб-система, в которой есть классическое меню родителей и детей, сохраненное в базе данных, с идентификатором полей в качестве PK и parent_id, указывающим на меню владельца. (Да, я знаю, что это не очень хорошо масштабируется, но это уже другая тема).
Итак, для этих записей (пары id-parent_id):
0-7 0-4 4-9 4-14 4-16 9-6
У меня есть такое дерево:
0
├ 7
└ 4
├ 9
| └ 6
├ 14
└ 16
Мне нужно скрыть верхний узел, поэтому я должен составить список всех дочерних элементов этого определенного узла, то есть для 4 они будут (9, 6, 14, 16). Порядок не имеет значения.
Я запутался ... вписывается ли это в классические задачи о деревьях? или это графическое?
Как я могу составить эту структуру и решить эту проблему с помощью php?
Ответы 4
Это отличный шанс использовать рекурсию!
Псевдокод:
nodeList = {}
enumerateNodes(rootNode, nodeList);
function enumerateNodes(node, nodeList) {
nodeList += node;
foreach ( childnode in node.children ) {
enumerateNodes(childnode, nodeList);
}
}
Обновлено: не заметил, что ваше дерево находится в соседнем формате списка. Я бы, вероятно, просто встроил это в реальную древовидную структуру данных, прежде чем я начал бы с ней работать. Просто прокрутите все пары (создавая узлы при первом просмотре) и свяжите их. У меня считать должно быть легко ...
С моделями смежных списков очень сложно работать. Компания, с которой я сейчас работаю, использует их для иерархий, и это вызывает большие головные боли. Я успешно использовал модели вложенных множеств Celko для предыдущих работодателей, и они отлично подходят для создания, поддержки и использования иерархий (деревьев).
Я нашел эту ссылку, которая описывает их: http://www.intelligententerprise.com/001020/celko.jhtml
Но я бы также порекомендовал книгу «SQL for Smarties: Advanced SQL Programming», написанную Джо Селко и посвященную вложенным множествам.
SQL для умников Джо Селко: расширенное программирование на SQL
Это проблема с графиком. Проверьте BFS (поиск в ширину) и DFS (поиск в глубину).. Вы можете погуглить эти термины и найти сотни реализаций в Интернете.
Это тривиально с реализацией вложенного набора. Подробнее см. Здесь:
http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/
В противном случае напишите примерно так:
def get_subtree(node)
if children.size > 0
return children.collect { |n| get_subtree(n) }
else
return node
end
end
Немного поработал, чтобы преобразовать его в реальную древовидную структуру, и все прошло нормально. Спасибо!