在預購中搜索遍歷方式

我有一個二叉搜索樹。我知道如何使用搜索屬性進行搜索。但我的任務是在不使用搜索屬性的情況下搜索樹（也就是說，在二叉樹中搜索）這是我必須搜索的方式。在預購中搜索遍歷方式

。如果您發現當前節點中的值返回它。

。否則在右邊搜索。如果沒有在右邊找到，則在左邊搜索

。如果在整個樹中找不到，則返回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值。（不在左邊搜索）。如何解決這個問題？

來源

2014-12-02 sanjay

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-02 07:04:26 iotaSingh

這是未經測試的代碼，但我會改變你的邏輯有點：

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-02 06:54:45

在預購中搜索遍歷方式

回答

相關問題