Получить все узлы в дереве, которые являются дочерними элементами другого.
Вопрос
У меня есть веб-система, в которой есть классическое меню «родители-потомки», сохраненное в базе данных, с идентификатором полей в качестве 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?
Решение
Это идеальный шанс использовать рекурсию!
Псевдокод:
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 для умников:Advanced SQL Programming», написанный Джо Селко и охватывающий вложенные множества.
Это проблема графа.Проверить BFS (поиск в ширину) и DFS (поиск в глубину)..Вы можете поискать в Google эти термины и найти сотни реализаций в сети.
Это тривиально при реализации вложенного набора.Подробнее см. здесь:
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