ルートから任意のツリー上の与えられたノードへのパスを取得する方法は？

Question

私はこの木を持っている：

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

最終的な目標は、ルートとノードの間のパスの長さを見つけることです。この関数を実行すると、ルートとジョーからの距離と、ルートとダイアン（兄弟である）からの距離が異なります。これは、深さ優先検索のステップを数えるためです。 このアプローチは間違っているのですか、それを修正する方法ですか？

Answer 1

深度を見つけるためのカウンターの使用が間違っています。あなたが示したコードでは、イテレータのアイテムだけを数えています。

path（）メソッドを再帰的に呼び出させ、深さの値をメソッドのパラメータとして渡す必要があります。各再帰呼び出しの深さ値をインクリメントします。