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

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