Как остановить поиск дерева после того, как ребенок был найден

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) является не сделано на узлах, которые не имеют Childre п.

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 класса на всех! У вас не должно быть одного, все его функции должны существовать полностью внутри класса узлов. В идеале, корневой узел - это дерево.