在预购中搜索遍历方式

Question

我有一个二叉搜索树。我知道如何使用搜索属性进行搜索。但我的任务是在不使用搜索属性的情况下搜索树（也就是说，在二叉树中搜索）这是我必须搜索的方式。

。如果您发现当前节点中的值返回它。

。否则在右边搜索。如果没有在右边找到，则在左边搜索

。如果在整个树中找不到，则返回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值。 （不在左边搜索）。如何解决这个问题？

Answer 1

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; 

}

Answer 2

这是未经测试的代码，但我会改变你的逻辑有点：

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

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