2016-10-21 17 views
0

У меня есть это дерево:Как получить путь от корня к данному узлу на любом дереве?

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

Я продлил код в this page

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

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; 
} 

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

+0

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

+1

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

+1

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

ответ

0

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

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

Смежные вопросы