recherche récursive dans un arbre en Java

Question

J'ai un arbre non binaire avec des noeuds définis de la manière suivante:

public class TreeNode{ 
private String label; 
private TreeNode[] children; 

public TreeNode(String label){ 
    this.label = label; 
    children = new TreeNode[9] 
} 

Ainsi, chaque noeud a une étiquette et un tableau de taille 9 qui détient ses 9 enfants. Maintenant, dans ma classe d'arbre, je veux définir une méthode de recherche qui trouvera un nœud avec une étiquette spécifique. Voilà ce que je pouvais venir avec:

public TreeNode find(String label, TreeNode node) { 
    TreeNode result = null; 
    if (node.getLabel().equals(label)) { 
     return node; 
    } else { 
     if (node.hasChildren()){ 
      for (int i = 0; i< node.getChildren().length; i++){ 
       if (node.getChildren()[i].getLabel().equals(label)) { 
        result = node.getChildren()[i]; 
        break; 
       else 
        return find(label, node.getChildren()[i]; 
      } 
    return result; 
} 

Et le problème est qu'il va juste un niveau plus profond à chaque fois sans regarder à travers les frères et sœurs du je fournis « nœud » à la méthode.

Je suis sûr que la solution est triviale mais je n'arrive pas à l'attraper.

Il y a un similar question here et je pense que leur problème est également similaire mais je n'arrive pas à traduire la solution fournie dans mon application.

Qu'est-ce qui me manque? Merci de votre aide!

Answer 1

Vous ne devez pas utiliser return dans la boucle for sans vérifier la valeur renvoyée de l'appel récursif. En outre, appliquez l'appel récursif à tous les éléments de la boucle sans condition.

for (int i = 0; i < node.getChildren().length; i++){ 
    result = find(label, node.getChildren()[i]; 
    if(result != null) { 
     return result; 
    } 
}