0

二分探索木があります。検索プロパティを使用して検索する方法を知っています。しかし、私の仕事は、検索プロパティを使用せずにツリーを検索することです (たとえば、二分木で検索します)。これが私の検索方法です。

1 . 現在のノードで値が見つかった場合は、それを返します。

2 . そうでなければ右に検索します。右に見つからない場合は、左に検索します

3 . ツリー全体で見つからない場合は null を返します。

これは私が試したものです。

public Node search(int val)
{
    Node target = this;
    if(target.getVal() == val)
        return this;
    else if(target.getRight() == null && target.getLeft() == null)
        return null;
    if(target.getRight() != null)
    {
        return target.getRight().search(id);
    }
    if(target.getLeft() != null)
    {
        return target.getLeft().search(id);
    }
    return null;
}

私のコードの問題は、右の子が存在し、右に val が見つからない場合、null値を取得していることです。(左側を検索していません)。これを解決するには？

4

2 に答える 2

0 
public Node search(int val)
{
    Node target = this;
    if(target.getVal() == val)
        return this;
    else if(target.getRight() == null && target.getLeft() == null)
        return null;
    if(target.getRight() != null)
    {
        return target.getRight().search(id); //here lies the problem
    }
    if(target.getLeft() != null)
    {
        return target.getLeft().search(id);
   }
return null;

}

コードの問題は、検索対象のノードの右側のサブツリーで検索結果を返すことです。

更新されたコードは次のとおりです

public Node search(int val)
{
    Node target = null;
    if(this.getVal() == val)
    {
        return this;
    }
    else if(this.getRight() == null && this.getLeft() == null)
        return target;
    if(this.getRight() != null)
    {
        target = this.getRight().search(id);
    }
    if(target==null && this.getLeft() != null)
    {
        target = this.getLeft().search(id);
   }
   return target;

}

于 2014-12-02T07:04:26.563 に答える
0

これはテストされていないコードですが、ロジックを少し変更します。

public Node search(int val)
{
    if(this.getVal() == val)
        return this;

    if (this.getRight() != null) {
        Node right = this.getRight().search(id);
        if (right != null)
            return right;
    }

    if (this.getLeft() != null) {
        Node left = this.getLeft().search(id);
        if (left != null)
            return left;
    }

    return null;
}

あなたのバージョンでは、右側または左側のノードがnullでないという唯一の要件を持つソリューションを返しています。解決策が見つかった場合にのみ、解決策を返す必要があります。

于 2014-12-02T06:54:45.513 に答える