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

StackOverflow https://stackoverflow.com/questions/79041

  •  09-06-2019
  •  | 
  •  

Вопрос

У меня есть веб-система, в которой есть классическое меню «родители-потомки», сохраненное в базе данных, с идентификатором полей в качестве 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», написанный Джо Селко и охватывающий вложенные множества.

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

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

Это проблема графа.Проверить 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
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top