搜索節點的樹在Java中

Question

我有下面的構造做了一個二叉樹：

public Person(String name, int age, char gender, Person c1, Person c2) 

c1爲左子和c2是正確的孩子。

我想編寫一個方法來搜索最大代中的特定名稱。就像a.depthFirstSearch(Eva, 1);這裏Eva是搜索的名字，1是我可以查看的世代（或層次）的最大數量。

這是我有： 編輯：

public Person depthFirstSearch(String name, int maxGeneration) 
{ 
    { 
Person temp; 
if (maxGeneration>1){ 
    if (this.name.equals(name)){ 
     temp=this; 
     return temp; 
     } 
    else{ 
    if (child1!=null) 
     temp=child1.depthFirstSearch(name, maxGeneration-1); 
    if (child2!=null) 
     temp=child1.depthFirstSearch(name, maxGeneration-1); 
    } 
} 
return null; 
} 
} 

這裏有兩個問題。我認爲深度在每次函數調用時都被重置爲0，所以我知道我可以跟蹤其他地方的深度或找到替代方法。我認爲另一個問題是，child2從來沒有真正到達過，因爲我在child1返回。我不確定這是如何工作的，所以如果有人能夠解釋這一點，那會很棒。任何修復建議？

另外，我被告知必須先搜索深度，意味着首先深入探索更深的世代。我不確定這意味着什麼，以及它與我在實現中使用的邏輯有多麼不同。

Answer 1

既然你在每次遞歸調用遞減maxGeneration，你不需要depth變量都：當maxGeneration == 0你根本就沒有任何搜索更多返回null。

至於你的其他問題，而不是直接返回child1.depthFirstSearch(...)的值，存儲在一個臨時變量的值。如果不是null，則找到該節點，請立即返回，否則請繼續搜索child2。

---

更新：

它應該是（大於或等於）if (maxGeneration >= 1) ...，否則與maxGeneration == 1最後一次通話將始終返回null。或者，你可以檢查0和返回null：

if (maxGeneration == 0) 
    return null; 

// rest of your code 

此外，你還沒有使用的返回值來檢查，如果該節點是在左子樹或者沒有實際找到。現在，即使您找到child1下的節點，您仍然可以看到child2，並且您最終會返回null，這是錯誤的。您需要child2下搜索只在左搜索返回null：

Person temp; 
if (child1 != null) { 
    temp = child1.depthFirstSearch(name, maxGeneration-1); 
    if (temp != null) 
    return temp; // found the node, just return 
} 
// otherwise the following code will execute 
if (child2 != null) { 
    temp = child2.depthFirstSearch(name, maxGeneration-1); 
    if (temp != null) 
    return temp; // found the node, just return 
} 
// didn't find node under either child 
return null;