0

二分木を検索して、ノードに格納されている文字列を見つけようとしています。

public void traverse (BinaryTreeNode root){ 
    if (root.leftchild != null){
        traverse (root.leftchild);
    }
        System.out.println(root.character);
    if (root.rightchild != null){
        traverse (root.rightchild);
    }
}

これは問題なく機能し、ツリー内のすべてのノードが表示されます。(コードは別の古いスタックオーバーフローの質問のコードから作成されました!私の問題は、root.character を入力された文字列と比較する方法であり、一致する場合は再帰から抜け出します。誰かがいくつかのヒントをドロップできる場合は、それを感謝します.

    public BinaryTreeNode traverse (BinaryTreeNode root, String inString){ // Each child of a tree is a root of its subtree.
    if (root.character != null) {
        if (root.character.equalsIgnoreCase(inString)) {
            System.out.println("root.charcter: " + root.character + " char " + inString);
            return root;
        }
    }
    if (root.leftchild != null){
        traverse (root.leftchild, inString);
    }

    if (root.rightchild != null){
        traverse (root.rightchild, inString);
    }

    return null;
}

上記のコードは機能しているようですが、正しい BinaryTreeNode を返しますが、ノードが見つかったときに再帰を停止する方法を考えていないため、最後に null も返します。

4

1 に答える 1

1

検索する文字列を渡さずにトラバース関数を呼び出しています...多くの場合、戻り値もありません。

関数がいつ再帰を終了するか (その場合はノードを返す) と、終了せずにツリーの残りを探索するときに関数が何をすべきかについて、もう少し考える必要があります。

たとえば、疑似コードで (プログラミングを行います):

findNode(root, query) {
  // nothing to search, not found
  if root==null return null  

  // Found it!
  if root.name==query return root

  // This is when we recurse left, stop if we found a result
  leftResult = findNode(root.left, query)
  if leftResult!=null return leftResult

  // else try to the right, stop if we found a result
  rightResult = findNode(root.right, query)
  if rightResult!=null return rightResult

  // Nothing else to try, not found
  return null
}
于 2012-11-21T21:10:19.930 に答える