Алгоритм рекурсивного прохождения леса детей

Question

Пожалуйста, дайте мне знать, если это плохая практика или что-то плохое. Дело в том, что в моей программе мне нужно создать метод, который проходит через корневой элемент и все дочерние узлы этого элемента. Мои элементы такие:

|--ID--|--Parent--|--Additinal info--|
|  1   |    0     | root element     |
|  2   |    0     | root elemnet     |
|  3   |    1     |child element of 1|
|  4   |    1     |child element of 1|
|  5   |    3     |child element of 3|
--------------------------------------

Теперь, если я хочу получить все дочерние элементы элемента с идентификатором 1 (независимо от того, имеет ли он 1000 дочерних элементов или просто 2, как в этом примере), я хочу, чтобы мой метод принес это мне, но я не уверен, как это сделать ? Все эти элементы находятся в списке, и это то, с чем я работаю. Каждый раз, когда я нахожу элемент, который мне нужно проверить, есть ли у него дочерние элементы, то же самое относится и к дочерним элементам. Это потому, что мне нужно выводить элементы в правильном порядке. Я думал о том, чтобы сделать это, поэтому сначала я делаю карту макета, а затем использую карту для вывода, но я вроде как застрял с идеей.

Есть какие-нибудь подсказки?

Answer 1

Как и многие из этих проблем с деревом, волшебное слово здесь - рекурсия. Порядок, который вы описываете в таблице, это порядок по идентификаторам, который не совсем соответствует глубине или ширине. Но все в порядке, все, что вам нужно, это поместить узлы в некую базу данных, которая вернет их в нужном вам порядке. Таким образом, общий план

• рекурсивно «пройтись» по дереву, чтобы найти все узлы; вставьте узлы в strcuture данных, который упорядочивает их по ID
• печать упорядоченных узлов

Рекурсивная часть также проста:

• начало с корневого узла

• если корневого узла нет в списке узлов, добавьте его

• взять первый дочерний узел и сделать то же самое.

Так что-то вроде (псевдокод):

dfs(node, nodelist):
   if node not in nodelist
      insert node in nodelist
   for each child node n
      dfs(n, nodelist)

Answer 2

Вы должны реализовать что-то вроде: цикл в списке и для каждого текущего элемента списка, поиск количества дочерних элементов, например, количества элементов в списке, где element.Parent = currentElementofList.Id .If число дочерних элементов этого элемента больше нуля, вы должны получить эти дочерние элементы, и это продолжается до тех пор, пока в списке больше не будет элементов для зацикливания.

Answer 3

Ваш подход к представлению иерархических данных очень неэффективен, когда речь идет об обходе дочерних узлов. В основном вам нужно выполнить один запрос на узел.

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

Answer 4

Вам нужна модель списка смежности .

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

Answer 5

Звучит как проблема обхода графа, поэтому я бы преобразовал этот список в структуру графа (используя списки смежности ), а затем перебрал его либо с помощью DFS , либо BFS. .