Arbre binaire récursif Java

Question

Bienvenue! J'ai une méthode statique publique récursive nommée moins qui prend un nœud d'arbre (un arbre binaire original, pas vraiment un arbre de recherche) et un paramètre int qui retourne si toutes les valeurs dans l'arbre sont inférieures à l'entier. Donc, je voudrais utiliser un public class TN { public int value; public TN left, right; public TN(int v, TN l, TN r) {value = v; left = l; right = r;} } Alors, ma méthode ressemblerait à ceci:

public static boolean less(TN s, int toFind){ 
if (s == null) 
    return true; 
else{ 
if(s.value <= toFind) 
    return less(s.left, toFind) && less(s.right, toFind); // right here do I return true? or do I have to somehow recall recursively 
else 
    return false; 
} 

Je me demandais si cela avait raison ou suis-je manque quelque chose ??? Dois-je retourner vrai et faux ??

Answer 1

return less(s, toFind); 

devrait être:

return less(s.left, toFind) && less(s.right, toFind); 

Je ne sais pas pourquoi la fonction est statique.

Comme mentionné précédemment, votre première partie devrait être juste:

if (s == null) return true; 

(EDIT:. Cela vous permettra d'obtenir un vrai résultat lorsque tous les nœuds satisfont à la condition Vous avez un == là-dedans qui devrait être un <). EDIT: Ok, vous avez beaucoup de problèmes que ceux que j'ai mentionnés. Vous devez logiquement parcourir votre code.

Vous devez traverser votre arborescence, vous devrez donc appeler votre fonction sur vos nœuds enfants. Ensuite, vous devez renvoyer true comme résultat par défaut. De cette façon, lorsque vous atteignez un nombre supérieur à ce que vous cherchez, vous pouvez retourner false immédiatement sans traverser aucun des enfants. J'espère vous avoir suffisamment aidé avec la logique pour que vous puissiez passer à travers le reste vous-même.

Answer 2

Tout d'abord, if (s = null) devrait être if (s == null) comme vous faites une comparaison, ne définissant pas la valeur de s à null.

L'instruction return less(null, toFind); continue d'appeler votre méthode - vous déborderez votre pile.

Answer 3

Il y a beaucoup plus élégant, OO façons d'écrire ceci. Ma recommandation serait de faire de less() une fonction membre non statique de la classe TN. De cette façon, si le nœud racine de l'arbre est appelé root, il suffit d'appeler root.less(). Chaque appel au less() appellera alors left.less() et right.less().

Depuis que vous avez publié un exemple de code qui ne serait même pas compilé, je me demande si vous utilisez un IDE, ou même essayé de compiler votre classe en utilisant javac. Je recommande fortement d'avoir Eclipse, Netbeans ou un autre IDE si vous êtes nouveau sur Java.

Answer 4

Notez comment votre fonction ne peut jamais renvoyer true car chaque fois que vous terminez la récursivité, vous renvoyez false? Et le problème est dans votre premier chèque. Vous dites que "toutes les valeurs dans l'arbre sont inférieures à l'entier." Eh bien, dans un arbre vide, toutes les valeurs (dont il n'y en a aucune) sont en effet inférieures à tout nombre entier, donc vous devriez retourner true dans ce cas. De plus, alors que vous dites "inférieur à", vous comparez pour l'égalité, vous vérifiez donc si toutes les valeurs sont égales à l'entier, pas moins que cela.