Блог

Главная - Вопросы по программированию - Как получить путь от корня к заданному узлу в произвольном дереве?

Как получить путь от корня к заданному узлу в произвольном дереве?

#java #tree #depth-first-search

#java #дерево #поиск в глубину

Вопрос:

У меня есть это дерево:

 Harry(root)
Jane
    Joe
    Diane
        George
            Jill
                Carol
        Mary
    Mark
Bill
    Grace

Я расширил код на этой странице

с помощью этой функции, которая использует поиск в глубину.

 public static int path(Tree t, String root, String n)
{
    // Default traversal strategy is 'depth-first'
    int counter = 0;
    Iterator<Node> depthIterator = t.iterator(root);
    while (depthIterator.hasNext()) {
        Node node = depthIterator.next();
        if(node.getIdentifier().compareTo(n)==0)
        {
            System.out.println("Distance from "   root  " to "   n   " "   counter);
            return counter;
        }
        counter  ;
        System.out.println(node.getIdentifier());
    }
    return 0;
}

Моя конечная цель — найти длину пути между корнем и заданным узлом. Когда я запускаю эту функцию, расстояние от root и Joe, и, расстояние от root и Diane (которые являются братьями и сестрами) отличается, потому что оно подсчитывает шаги поиска в глубину.
Этот подход неправильный или есть способ это исправить?

Комментарии:

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

2. Если вы знаете узел, не могли бы вы поместить его в стек, затем перейти к его родительскому элементу и помещать в стек, пока не окажетесь в корне, после чего извлеките весь стек и получите нужный путь?

3. @VenomFangs Похоже, что у класса Node нет родительского элемента (узлы не знают своего родителя). Они знают только своих дочерних элементов.

4. Как насчет функции, которая возвращает глубину узла даже без использования поиска в глубину?

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

Ответ №1:

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

Вам нужно заставить ваш метод path() вызываться рекурсивно и передать значение глубины в качестве параметра для метода. И увеличивайте значение глубины для каждого рекурсивного вызова.