Получить все узлы в дереве, которые являются дочерними по отношению к другому

Question

У меня есть веб-система, в которой есть классическое меню parent-children, сохраненное в базе данных, с полями id как 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?

Answer 1

С соседними моделями списков очень сложно иметь дело. Компания, с которой я сейчас работаю, использует их для иерархии, и это вызывает большие головные боли. Я успешно использовал модели вложенных множеств Celko для предыдущих работодателей, и они отлично работают для создания, поддержки и использования иерархий (деревьев).

Я нашел эту ссылку, которая описывает их: http://www.intelligententerprise.com/001020/celko.jhtml

Но я бы также порекомендовал книгу «SQL для умных людей: расширенное программирование на SQL», написанную Джо Селко, которая охватывает вложенные множества.

SQL Джо Селко для умников: Расширенное программирование на SQL

Деревья и иерархии Джо Селко в SQL для умников

Answer 2

Это идеальный шанс использовать рекурсию!

Псевдо-код:

nodeList = {}
enumerateNodes(rootNode, nodeList);

function enumerateNodes(node, nodeList) {
   nodeList += node;
   foreach ( childnode in node.children ) {
       enumerateNodes(childnode, nodeList);
   }
}

Редактировать: не заметил, что ваше дерево в формате списка смежных. Я, вероятно, просто встроил бы это в фактическую структуру данных дерева, прежде чем начать работать с ней. Просто переберите все пары (создавая узлы при первом их появлении) и связывая их. Я думаю это должно быть легко ...

Answer 3

Это тривиально для реализации с вложенным множеством. Смотрите здесь для более подробной информации:

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

Answer 4

Это проблема с графиком. Проверьте BFS (поиск в ширину) и DFS (поиск в глубину). . Вы можете найти эти термины в Google и найти сотни реализаций в Интернете.