Je suis désespérément perdu quand il s'agit de fonctions récursives. Je dois créer une fonction récursive pour traverser un arborescence binaire et insérer un nouveau nœud entre les valeurs spécifiques. Aurais-je besoin de recopier ma fonction Traverse et de le modifier dans toutes les autres fonctions que je l'utilise? Est-ce que quelqu'un s'il vous plaît évaluer la fonction Traverse?
Je pense que mon code traversant est correct. P>
Node traverse (Node currentNode){
if (!currentNode.left.equals(null)){
traverse (currentNode.left);
return currentNode.left;
}
if (!currentNode.right.equals(null)){
traverse (currentNode.right);
return currentNode.right;
}
return currentNode;
}
3 Réponses :
Une fonction récursive renvoie la valeur d'elle-même avec un paramètre modifié ou une condition de terminaison (sortie). Par exemple, factorial: dans votre code, vous appelez une "traverse" mais ne fais rien avec le résultat ...
Lorsque votre fonction récursive se termine, votre retour final sera d'abord laissé enfant s'il existe, sinon le premier enfant juste s'il existe, sinon le nœud racine. Veuillez donner plus de détails sur la raison pour laquelle vous devez traverser L'arborescence (également, pas sûr de ce que vous vouliez dire par "Copier la fonction et le modifier dans toutes les autres fonctions", l'ensemble idée d'une fonction est de coder-appeler-plusieurs)
On dirait que vous voyez dans la méthodologie de pré-commande, mais je suis un peu sceptique quant à ce que vous souhaitez exactement accomplir sans comparer votre nœud actuel avec une valeur de base qui définit u a atteint votre destination. Je suggérerais d'éliminer un arbre simple et de visualiser les étapes. Ensuite, essayez de mettre cela en code.
Exactement. Dessinez-le sur papier et comprenez d'abord les étapes. Ensuite, insérez des instructions d'impression dans votre code afin que vous puissiez voir ce qui se passe réellement à chaque étape. Une fois que vous avez le concept de récursivité, ce n'est pas vraiment si difficile.
En ce qui concerne les arbres binaires, il existe plusieurs types de traverses qui peuvent être faits de manière récursive. Ils sont écrits dans l'ordre sont référencés puis visités (L = enfant gauche, v = visitez ce nœud, r = enfant droit).
Votre code semble exécuter la méthode de déplacement de l'après-poste, mais vous obtenez quelques objets mélangés. Premièrement, le noeud em> est ce que vous voulez traverser; Les données em> sont ce que vous voulez visiter. Deuxièmement, vous n'avez aucune raison de retourner le nœud lui-même, de la manière dont cela est mis en œuvre. Votre code ne permet pas à une condition de dire: «Je recherche Ceci STRAND> Data particulariables, avez-vous---les M. Node @ 0xDeadbeef? ', Qui serait trouvé avec une sorte d'extra Paramètre de recherche. P> Un travers de BST académique imprime uniquement les nœuds lui-même. Si vous souhaitez ajouter une fonctionnalité de recherche, ce n'est qu'un paramètre de plus, ainsi qu'une vérification supplémentaire du nœud droit. P> Voici un extrait: P> // Academic
public void traverse (Node root){ // Each child of a tree is a root of its subtree.
if (root.left != null){
traverse (root.left);
}
System.out.println(root.data);
if (root.right != null){
traverse (root.right);
}
}
// Search with a valid node returned, assuming int
public Node traverse (Node root, int data){ // What data are you looking for again?
if(root.data == data) {
return root;
}
if (root.left != null && data < root.data) {
return traverse (root.left, data);
}
if (root.right != null && data > root.data) {
return traverse (root.right, data);
}
return null;
}
Merci. Je n'avais aucune idée de ce que je faisais.
Pour l'exemple de recherche, le premier appel récursif doit vérifier que le résultat n'est pas NULL, puis vérifiez uniquement le côté droit s'il est null. Sinon, il ne retournera aucun résultat si la valeur de recherche est dans la plupart des nœuds de gauche. Node publique Traverse (Node racine, données int) {si (root.data == données) {racine de retour; } si (root.left! = null) {nœud val = traverser (root.left, données); Si (val! = null) {retour val; } elier si (racine.right! = null) {retour Traverse (racine.right, données); }} renvoie null; }
@Aaron je prie de différer.
L'algorithme de la réponse retournera «NULL» si les données ne sont pas trouvées quelque part dans la plus grande branche de gauche, il s'agira ensuite de bulles qui en résulte jusqu'au sommet, même si les données se situent ailleurs dans l'arbre. Il n'y a pas de pas pour le forcer à descendre du sentier "droit". Voir cette réponse Stackoverflow.com/a/5938541/572166
Hmm. Je vois ce que tu veux dire maintenant @aaron. Je vais modifier ça.
La méthode traverse est destinée à utiliser les éléments de votre arborescence binaire, mais vous retournez la racine gauche, la racine droite ou la racine (même si la racine est
null !). L'idée des fonctions récursives est de définir le boîtier de base, puis le code répétitif pour obtenir jusqu'à ce cas de baseQuel genre de transversal essayez-vous de faire? Est-ce une barre
? Avez-vous besoin d'insérer un nœud au bon endroit dans unBST ?Si vous parcourez la gauche, vous revenez à la dernière étape de la ligne 4 et ne traversez jamais la droite et ne revenez jamais actuellement nœud. Ça ne regarde pas bien.
Où sont les valeurs spécifiques? Votre fonction ressemble presque à une traversée de pré-commande, mais comme il n'est pas clair ce que c'est censé faire, il est impossible d'évaluer à quel point il l'obtient bien.