0

二分木を再帰的に検索するために、以下のコードを記述しました。system.outステートメントが実行されていても、returnステートメントは再帰全体から戻っていないため、このメソッドはtrueを返しません。

再帰全体からどのように戻ることができるかを誰かが提案できますか？

public static boolean isElementinTree(int num, BinaryTreeNode root) 
{
    if (root != null)
    {
        int rootVal = root.getData();
        BinaryTreeNode left = root.getLeft();
        BinaryTreeNode right = root.getRight();
        if (left != null)
        {
            isElementinTree(num,left);

        }
        if (right != null)
        {
            isElementinTree(num,right);
        }
        if (num == rootVal)
        {
            System.out.println("------ MATCH -----");               
            return true;
        }           
    }   
    return false;
}
4

5 に答える 5

11

これが問題です：

if (left != null)
{
    isElementinTree(num,left);

}
if (right != null)
{
    isElementinTree(num,right);
}

そのような場合はメソッドを呼び出していますが、結果は無視しています。見つかった場合はすぐに戻るように、それぞれを変更したいのではないかと思います。

if (left != null && isElementinTree(num, left))
{
    return true;
}
if (right != null && isElementinTree(num, right))
{
    return true;
}

または、全体をより宣言的にするために、より簡単に行うことができます。

public static boolean isElementinTree(int num, BinaryTreeNode root) 
{
    return root != null && (root.getData() == num ||
                            isElementInTree(num, root.getLeft()) ||
                            isElementInTree(num, root.getRight()));
}

isElementInTree最初の部分ですでに保護しているので、nullの2番目の引数で呼び出すのは問題ありません。

于 2012-08-07T13:52:01.313 に答える
1

このような単純なソリューションの何が問題になっていますか？

public static boolean isElementinTree(int num, BinaryTreeNode root)
{
    return root != null &&                           //The tree is non-null
           (num == root.getData() ||                 //We have num in this node OR
            isElementInTree(num, root.getLeft()) ||  //We have num in left subtree OR
            isElementInTree(num, root.getRight()) ); //We have num in right subtree
}
于 2018-12-18T13:09:24.390 に答える
0

値がブランチの1つにあるかどうかを確認し、その結果を保存する必要があります。

変数を初期化しますboolean found = false;。

再帰呼び出しを行うときは、次のようなことを行う必要があります。

found = isElementinTree(num,left)

右側も同じです。

最後に、falseを返す代わりに、値がブランチで見つかったかどうかを確認します。return found;

また、最初に各ブランチを検索するのではなく、最初に探している番号がノード自体にないかどうかを確認してください。ifの順序を切り替えるだけです。

于 2012-08-07T13:52:02.350 に答える
0

探している要素が左または右のサブツリーで見つかった場合は、このファクトを呼び出し元に返す必要があります。

    if (left != null)
    {
        if(isElementinTree(num,left)) return true;
    }
    if (right != null)
    {
        if(isElementinTree(num,right)) return true;
    }

左のツリー、右のツリー、および現在のノードのいずれにも見つからない場合にのみ、最終的に最終にフォールスルーしますreturn false。

于 2012-08-07T13:58:51.467 に答える
0

再帰ソリューション：

boolean isElementinTree (int num, BinaryTreeNode root)
{
  if(root == null)
   return false;

  if(root.value == num)
   return true;

  boolean n1 = isElementinTree(num,root.getLeft());
  boolean n2 = isElementinTree(num,root.getRight());

  return n1 ? n1 : n2;

}
于 2013-08-01T00:57:52.100 に答える