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

在您的版本中，您返回的解决方案唯一要求右侧或左侧的节点不为空。只有找到解决方案时，您才必须返回解决方案。

于 2014-12-02T06:54:45.513 回答
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 回答