如何在發現孩子後停止樹搜索

Question

以下是無法返回正確的子節點，即使它實際上在樹的上方找到孩子。它發現它後，似乎放棄了孩子，廣告繼續搜索樹的其餘部分。

private Node<K, V> getNode(K key, ArrayList<Node<K, V>> children){ 
    if (children == null) return null; 

    if (root.getKey().equals(key)) return root; 

    for (Node<K, V> child : children) { 
     if (child.getKey().equals(key)) return child; 
     getNode(key, child.getChildren()); 
    } 

    return null; 
} 

我用下面的代碼進行了測試：

Tree<Integer, String> tree = new Tree<>(1, "1"); 

tree.addChild(1, new Node<>(2, "2")); 
tree.addChild(1, new Node<>(3, "3")); 
tree.addChild(1, new Node<>(4, "4")); 
tree.addChild(2, new Node<>(5, "5")); 

System.out.println(tree.addChild(5, new Node<>(6, "6"))); 
System.out.println(tree.addChild(5, new Node<>(7, "7"))); 

但是，控制檯輸出false兩次，即使它應該是true。儘管我在樹上添加了一個，但找不到關鍵字爲5的孩子。

Answer 1

的問題是，當你在一個子樹尋找一個孩子，你忽略了返回值：

if (child.getKey().equals(key)) 
{ 
    // This is fine 
    return child; 
} 
else 
{ 
    // This is bad: you ignore the return value. 
    getNode(key, child.getChildren()); 
} 

要解決，獲取返回值，並返回它，如果它是不null，像這樣：

if (child.getKey().equals(key)) 
{ 
    return child; 
} 
else 
{ 
    Node<K, V> res = getNode(key, child.getChildren()); 
    if (res != null) { 
     return res; 
    } 
} 

此外，你的代碼將錯過情況當值存儲在根，根一直沒有孩子，因爲root.getKey().equals(key)是不上沒有兒童遊樂節點完成ñ。

Answer 2

寫return getNode(key, child.getChildren())在else聲明。它的方式來處理遞歸。

 .... 
     else 
     { 
     return getNode(key, child.getChildren()); 
     } 

Answer 3

經過重大的重新格式化工作之後，我將您的代碼重構爲更清晰的形式。雖然實質上不同，以下是邏輯上等同於您的代碼：

private Node<K, V> getNode(K key, ArrayList<Node<K, V>> children){ 
    if (children == null) return null; 

    if (root.getKey().equals(key)) return root; 

    for (Node<K,V> child : children) { 
     if (child.getKey().equals(key)) return child; 
     getNode(key, child.getChildren()); 
    } 

    return null; 
} 

現在，我們可以挑選除了代碼，並修復它。

第一個問題是，您沒有在方法前記錄javadoc註釋並記錄其參數並返回@param和@return。這就是你需要解決的問題。

其次，此方法應作爲Node類的類方法實施，並應爲public。那就是：

class Node<K,V> { 

// ... whatever else this class has in it ... 

    public K getKey() { /* ... stuff ... */ } 

    ArrayList<Node<K,V>> children = new ArrayList<>(); 

    public Node<K, V> getNode(K key){ 
     if (children == null) return null; 

     if (key.equals(this.getKey())) return this; 

     for (Node<K,V> child : children) { 
      if (child.getKey().equals(key)) return child; 
      child.getNode(key); 
     } 

     return null; 
    } 
} 

而且，因爲我們現在已經保證了children總是被初始化，並且完全在我們的控制之下，我們可以擺脫虛假null檢查。

public Node<K, V> getNode(K key){  
    if (key.equals(this.getKey())) return this; 

    for (Node<K,V> child : children) { 
     if (child.getKey().equals(key)) return child; 
     child.getNode(key); 
    } 

    return null; 
} 

現在，你是冗餘檢查孩子。由於getNode()已經檢查是否this是正確的節點，沒有理由單獨檢查當前節點的每個孩子

public Node<K, V> getNode(K key){  
    if (key.equals(this.getKey())) return this; 

    for (Node<K,V> child : children) 
     child.getNode(key); 

    return null; 
} 

現在，我們已經擺脫了這麼多的代碼，它應該是相當明顯的是什麼問題實際上是：上層方法實際上從未實際上通過搜索孩子找到節點。一個簡單的改變就足以解決這個問題，雖然：

public Node<K, V> getNode(K key){  
    if (key.equals(this.getKey())) return this; 

    for (Node<K,V> child : children){ 
     Node<K,V> result = child.getNode(key); 
     if(result != null) return result; 
    } 

    return null; 
} 

請注意，我們不應該被檢查，如果孩子是null。這應該由我們暴露了添加新值的方法來處理，我們不應該將國外的節點到樹：

public boolean put(K key, V value){ 
    children.add(new Node<>(key, value)); 
} 

還有一兩件事：有沒有必要一個單獨的Tree類在所有！你不應該有一個，它的所有功能應該完全存在於節點類中。理想情況下，根節點是樹。