Извлечение всех узлов из данного дерева в Java

Question

Я пытаюсь создать метод для сбора всех узлов из данного дерева, переданных в качестве параметра, но кажется, что он не читает левую ветвь любого узла ,

Код, который я разработал до сих пор, следующий.

private ArrayList<T> collect(AVLTree<T> tree, AVLNode<T> tRoot, ArrayList<T> l) { 

    ArrayList<T> nodes = l; 

    if (tRoot == null) 
     return null; 

    else { 
     if (!nodes.contains(tRoot.element())) { 
      nodes.add(tRoot.element()); 

      if (tRoot.getRight() != null) { 
       collect(tree, tRoot.getRight(), nodes); 
       return nodes; 
      } 

      else if (tRoot.getLeft() != null) { 
       collect(tree, tRoot.getLeft(), nodes); 
       return nodes; 
      } 
     } 
    } 

    return nodes; 

} 

Надеется, что вы можете помочь мне немного с этим, как я действительно застрял с ним прямо сейчас ...

Answer 1

Две вещей, которые делают код не работает.

1. Вы только проверить одну ветвь какого-либо узла, то есть, если правая ветвь проверяется, левая не будет, даже если есть узлы в левой
2. Вы возвращающиеся слишком рано. Вам не нужно возвращаться сразу после проверки каждой ветки. Поступая таким образом, вы снова пропустите левые ветви, если существует правильная ветка.

Следующие исправления будут работать.

private ArrayList<T> collect(AVLTree<T> tree, AVLNode<T> tRoot, ArrayList<T> l) { 

    ArrayList<T> nodes = l; 

    if (tRoot == null) 
     return null; 

    else { 
     if (!nodes.contains(tRoot.element())) { 
      nodes.add(tRoot.element()); 

      if (tRoot.getRight() != null) { 
       collect(tree, tRoot.getRight(), nodes); 
      } 

      if (tRoot.getLeft() != null) { 
       collect(tree, tRoot.getLeft(), nodes); 
      } 
     } 
    } 

    return nodes; 

} 

EDIT: После глядя на код немного больше. Есть несколько мест, где избыточность кода существует. Их можно упростить и очистить до следующего:

private ArrayList<T> collect(AVLTree<T> tree, AVLNode<T> tRoot, ArrayList<T> l) { 

    ArrayList<T> nodes = l; 

    if (tRoot == null) 
     return null; 

    if (!nodes.contains(tRoot.element())) { 
     nodes.add(tRoot.element()); 
     collect(tree, tRoot.getRight(), nodes); // this is safe since null check exists at top 
     collect(tree, tRoot.getLeft(), nodes); 
    } 

    return nodes; 

}