Aide sur la récursivité d'arborescence

Question

J'ai une classe Person et je veux créer un arbre. Voici le contsructor pour la classe Person.

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

c1 est l'enfant sur la gauche, et c2 est l'enfant sur la droite. Et donc dire que je crée trois personnes comme ceci:

Person c = new Person("Carl", 50, 'M', null, f); 

Person b = new Person("Barbara", 52, 'F', d, e); 

Person a = new Person("Adam", 75, 'M', b, c); 

Alors là, vous dites que Adam est le nœud racine, et l'enfant gauche d'Adam est b, qui est Barbara et son droit c qui est Carl, et ainsi de suite.

Donc ce que je veux faire est d'écrire une méthode de comptage, qui compte le nombre d'enfants, y compris this. Donc a.count() retournera 6 (si Person f n'a pas d'enfants).

Et voici le code que j'ai:

public int count() // total person count including this object 
{ 
    if(child1==null) 
     return 0; //I tried return 1 for this too didnt work 
    if (child2==null) 
     return 0; //also tried 1 for this 
    return 1+this.child1.count() +1+this.child2.count(); 
} 

J'ai couru ceci sur papier à plusieurs reprises, et il devrait trouver le bon résultat, mais il est hors de quelques pour une raison quelconque quand je lance effectivement il.

Answer 1

Votre code retourne 0 si l'un des enfants sont null. Ceci est incorrect car vous ne comptez pas pour l'autre enfant, ou this. Le nombre doit toujours être >= 1 car vous avez toujours au moins un noeud dans l'arborescence.

De même, vous ne pouvez pas retourner tout de suite si vous voyez qu'un enfant est null. Vous devez également compter l'autre enfant (s'il existe).

Voici comment je le mettre en œuvre:

public int count() // total person count including this object 
{ 
    int count = 1; // we count this node as 1 
    if (child1 != null) // if we have a left child, count its size 
     count += child1.count(); 
    if (child2 != null) // if we have a right child, count its size 
     count += child2.count() 
    return count; 
} 

Vous devez prendre en compte pour les enfants, même si l'un d'eux est null.

Answer 2

private int count() { 
    return 1 + ((this.child1 != null) ? (this.child1.count()) : (0)) + ((this.child2 != null) ? (this.child2.count()) : (0)); 
} 

Answer 3

Le résultat est faux parce que vous revenez 0 quand un enfant est nul oublier de compter le nœud lui-même ou l'autre enfant .. si c'est un, vous devez retourner quand même nœud feuille (child1 == null && child2 == null) 1.

quelque chose comme:

return 1 + (child1 == null ? 0 : child1.count()) + (child2 == null ? 0 : child2.count()) 

suivant votre code d'origine, il serait quelque chose comme:

if (child1 == null && child2 == null) 
    return 1; 
else if (child1 == null) 
    return 1 + child2.count(); 
else if (child2 == null) 
    return 1 + child1.count(); 
else 
    return 1 + child1.count() + child2.count(); 

mais dans ce cas, je dirais de rester avec réponse jjnguy qui calcule le résultat partiellement ..