Эффективный способ пройти через дерево объектов?

Question

У меня есть набор TreeNodes, каждый из которых имеет идентификатор, коллекцию родительских узлов и коллекцию дочерних узлов.

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

Я также хотел бы иметь возможность делать это в направлении «вверх» через родительские узлы.

Есть ли простой алгоритм для этого?

РЕДАКТИРОВАТЬ: О, и я хотел бы иметь возможность выводить идентификаторы всех узлов в данной цепочке ...

Answer 1

Вы ищете Ширина вначале или Поиск в глубину . Сначала это не более чем следующее (это поиск в глубину).

Visit(Node node)
{
    foreach (Node childNode in node.Children)
    {
        Visit(childNode);
    }

    DoStuff(node);
}

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

И, кстати, если у TreeNode несколько родителей, это не дерево, а узел графа.

Answer 2

Возможно, вы захотите проверить depthFirstEnumeration() и breadthFirstEnumeration() на DefaultMutableTreeNode. Однако это не решает проблему желания перемещаться по дереву снизу вверх.

Answer 3

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

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

- РЕДАКТИРОВАТЬ -

Если у узла может быть более одного родителя, вы имеете дело с графом. Есть также алгоритмы обхода графа (см. Таблицу сбоку).

Убедитесь, что, если у вашего графа есть цикл, у вас не будет бесконечного цикла