Récupérer tous les nœuds d'un arbre donné en Java

Question

J'essaie de créer une méthode pour collecter tous les nœuds d'une arborescence donnée passée en paramètre, mais il semble qu'elle ne lise pas la branche gauche d'un nœud .

Le code que j'ai développé jusqu'à présent est le suivant.

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; 

} 

espère que vous pouvez me aider un peu avec ce que je suis vraiment coincé avec elle en ce moment ...

Answer 1

Deux choses qui rendent le code fonctionne pas.

1. Vous ne cochez une branche d'un nœud, qui signifie que si la branche droite est en cours de vérification, celui de gauche ne sera même pas s'il y a des noeuds dans la gauche
2. vous retournez trop tôt. Vous n'avez pas besoin de revenir juste après avoir vérifié chaque succursale. Ce faisant, vous sautez à nouveau les branches de gauche si la branche droite existe.

Les correctifs suivants fonctionneront.

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: Après avoir regardé le code un peu plus. Il existe peu d'endroits où la redondance de code existe. Ils peuvent être simplifiés et nettoyés comme suit:

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; 

}