0
J'ai cet arbre:Comment obtenir le chemin de la racine à un nœud donné sur un arbre arbitraire?
Harry(root)
Jane
Joe
Diane
George
Jill
Carol
Mary
Mark
Bill
Grace
J'ai étendu le code dans this page
avec cette fonction qui utilise la profondeur première recherche.
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;
}
Mon objectif final est de trouver la longueur d'un chemin entre la racine et un nœud donné. Lorsque j'exécute cette fonction, la distance entre la racine et Joe, et la distance entre la racine et Diane (qui sont frères et sœurs) est différente car elle compte les étapes de la recherche en profondeur en premier. Cette approche est-elle incorrecte ou est-ce un moyen de la réparer?
Est-il important que vous utilisiez l'itérateur de la première recherche en profondeur? Je pense que l'itérateur peut être problématique car il saute dans l'arbre (vous pourriez par exemple être à une profondeur de 5 et le prochain nœud est un enfant de la racine (profondeur 1)). Je pense que l'écriture de votre première recherche de profondeur, y compris un compte de profondeur serait plus facile que d'utiliser l'Iterator existant. –
Si vous connaissez le nœud, ne pouvez-vous pas le pousser dans une pile, puis aller à son parent et pousser dans une pile jusqu'à ce que vous êtes à la racine, après quoi pop la pile entière et avoir le chemin que vous voulez? –
@VenomFangs Il semble que la classe Node n'ait pas de parent (le nœud ne connaît pas le parent parent). Ils ne connaissent que leurs enfants. –