Recherche d'un noeud dans un arbre en Java

Question

J'ai un arbre binaire fait avec le constructeur suivant:

public Person(String name, int age, char gender, Person c1, Person c2) 

où c1 est l'enfant gauche et c2 est l'enfant droit.

Je souhaite écrire une méthode qui recherche un nom particulier dans une génération maximale. Donc, comme a.depthFirstSearch(Eva, 1); où Eva est le nom à rechercher et 1 est le nombre maximum de générations (ou de niveaux) que je peux regarder.

Voici ce que j'ai: EDIT:

public Person depthFirstSearch(String name, int maxGeneration) 
{ 
    { 
Person temp; 
if (maxGeneration>1){ 
    if (this.name.equals(name)){ 
     temp=this; 
     return temp; 
     } 
    else{ 
    if (child1!=null) 
     temp=child1.depthFirstSearch(name, maxGeneration-1); 
    if (child2!=null) 
     temp=child1.depthFirstSearch(name, maxGeneration-1); 
    } 
} 
return null; 
} 
} 

Il y a deux problèmes ici. Je pense que la profondeur est réinitialisée à 0 chaque fois que la fonction s'appelle elle-même, donc je sais que je peux soit garder la trace de la profondeur ailleurs ou trouver une alternative. L'autre problème, je pense, est que child2 n'est jamais vraiment atteint, puisque je reviens à child1. Je ne suis pas vraiment sûr de comment cela fonctionne, donc si quelqu'un pouvait expliquer ça, ce serait génial. Des suggestions pour certaines corrections? De plus, on me dit que je dois d'abord chercher la profondeur, c'est-à-dire regarder d'abord les générations les plus profondes. Je ne suis pas vraiment sûr de ce que cela signifie et de la différence avec la logique que j'utilise dans ma mise en œuvre.

Answer 1

Puisque vous décrémentez maxGeneration dans chaque appel récursif, vous n'avez pas besoin de la variable depth du tout: quand maxGeneration == 0 simplement vous ne cherchez pas plus et retour null.

En ce qui concerne votre autre problème, au lieu de renvoyer directement la valeur de child1.depthFirstSearch(...), stockez la valeur dans une variable temporaire. Si ce n'est pas null, vous avez trouvé le noeud, alors retournez-le immédiatement, sinon continuez la recherche sous child2.

---

Mise à jour:

Il devrait être if (maxGeneration >= 1) ... (supérieur ou égal à), sinon le dernier appel avec maxGeneration == 1 retournera toujours null. Sinon, vous pouvez simplement vérifier 0 et return null:

if (maxGeneration == 0) 
    return null; 

// rest of your code 

En outre, vous n'utilisez pas encore la valeur de retour pour vérifier si le noeud a été effectivement trouvé dans le sous-arbre gauche ou non. À l'heure actuelle, même si vous trouvez le nœud sous child1, vous regardez toujours sous child2 et vous finirez par retourner null, ce qui est faux. Vous devez rechercher sous child2 que si la recherche est retourné à gauche null:

Person temp; 
if (child1 != null) { 
    temp = child1.depthFirstSearch(name, maxGeneration-1); 
    if (temp != null) 
    return temp; // found the node, just return 
} 
// otherwise the following code will execute 
if (child2 != null) { 
    temp = child2.depthFirstSearch(name, maxGeneration-1); 
    if (temp != null) 
    return temp; // found the node, just return 
} 
// didn't find node under either child 
return null;