У меня есть это дерево:Как получить путь от корня к данному узлу на любом дереве?
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;
}
Моя конечная цель - найти длину пути между корнем и данным узлом. Когда я запускаю эту функцию, расстояние от корня и Джо, а расстояние от корня и Дианы (которые являются братьями и сестрами) различны, поскольку они подсчитывают шаги поиска по глубине. Является ли этот подход неправильным или это способ его исправить?
Важно ли использовать Итератор глубины первого поиска? Я думаю, что итератор может быть проблематичным, потому что он прыгает в дерево (вы могли бы, например, находиться на глубине 5, а следующий узел - дочерний корень (глубина 1)). Я думаю, что писать собственную глубину первого поиска, включая подсчет глубины, было бы проще, чем использование существующего Итератора. –
Если вы знаете узел, не можете ли вы его вставить в стек, а затем перейдите к его родительскому элементу и вставьте его в стек до тех пор, пока вы не окажетесь в корневом каталоге, после чего поместите весь стек и найдите нужный путь? –
@VenomFangs Кажется, что класс Node не имеет родителя (узел Node не знает своего родителя). Они знают только своих детей. –