J'essaie d'élargir ma compréhension limitée de la récursion. Je travaille sur un arbre de recherche binaire et je tente actuellement de mettre en œuvre une fonction traversée. J'ai démarré avec une traversée de pré-commande, cela n'a pas de problème et je suis passé à l'ordre qui me semblait beaucoup plus difficile. Je ne pouvais pas comprendre une solution récursive à mienne, donc je le googla et j'ai trouvé de nombreuses variantes de la même réponse-
function inOrderHelper(root) {
if (root !== null) {
inOrderHelper(root.left);
console.log(root.data);
inOrderHelper(root.right);
}
}
3 Réponses :
ligne 2 arrête la récursivité progressive pour toujours. en bas à gauche du graphique, le nœud 2 est évalué, puis Q2 fort> p> Il utilise la nature de la pile du langage de programmation lui-même, pour garder une trace de l'endroit où il se trouve dans le graphique. Chaque fois que la fonction est appelée une nouvelle image de pile est ajoutée à la pile et chaque fois qu'une fonction est terminée, ce cadre de pile est supprimé. P> q3 strong> p> Les nœuds sont imprimés en fonction de leur position dans le graphique et non de leur valeur. P> p> 
inadorder code> est appelé avec gauche code> comme argument, qui est non défini . La ligne 2 évalue à vrai code> et retourne immédiatement. Une fois qu'il est retourné au point d'appel, l'exécution continue. La ligne 4 est évaluée, ce qui signifie 2 code> est imprimé sur la console. Ensuite, la ligne 5 est évaluée. Cela se produit chaque fois que l'algorithme frappe un nœud sans gauche ni un sous-arbre droit. P>
const root = {
data: 7,
left: {
data: 4,
left: {
data: 2
},
right: {
data: 6
}
},
right: {
data: 9
}
}
function inOrder(root) {
if (!root)
return;
inOrder(root.left);
console.log(root.data);
inOrder(root.right);
}
inOrder(root)
Upvoted. Notez cependant que l'exemple n'est pas une BST.
Grande explication! J'aimerais pouvoir accepter de multiples réponses que la réponse à ma question parce que l'éclairant la nature de la récupération de la pile était vraiment ce que le concept cliquez dans mon esprit après la lecture de JDB. Merci pour ton aide!
Le moyen le plus simple de comprendre le code est généralement de l'essayer avec un débogueur. Chrome a un Excellent débogueur que vous pouvez utiliser pour passer à travers Le code, ligne par ligne, comme il s'exécute en temps réel.
Le moyen le plus simple est d'utiliser des journaux de console pour imprimer ce qui se passe, ce qui est la façon dont la plupart des programmeurs sur un certain âge déterminaient ce qui se passait avant de faire ses débuggeurs Il est plus facile. P>
Puisque je ne peux pas m'asseoir à côté de vous avec un débogueur Open, faisons la prochaine meilleure chose et ajoutons des journaux de console afin que nous puissions voir ce qui se passe: p> Essayons un exemple BST: P> qui pourrait être construit pour regarder quelque chose comme ça dans JavaScript: p> vous pouvez Exécutez ce code dans les outils de développement de votre navigateur en collant dans la fonction ci-dessus (et saisissez Entrée), puis appelez-la comme: P> {
left: {
left: {
value: 1,
},
value: 2,
right: {
value: 3,
},
},
value: 4,
right: {
value: 5,
},
}
Comme les autres ont déclaré, en utilisant le débogueur chrome pour passer à travers ce code est un excellent moyen de commencer à comprendre ce qui se passe. Je suggère également de dessiner vos propres images similaires à ce que les autres ont montré dans leurs réponses pour vous aider à suivre ce que le débogueur fait.
Comment le programme sait-il à s'arrêter avant la fin de l'arbre? Il me semble qu'il devrait continuer à aller au nœud gauche du coureur jusqu'à ce qu'il soit NULL, à quel point il va ignorer la console.log
La fonction visit toujours le nœud gauche jusqu'à ce qu'il atteigne une feuille. Ensuite, il retourne progressivement, imprime les données et visit chaque nœud droit. Le programme se terminera après avoir visité chaque noeud de l'arbre.
Comment le programme sait-il qu'un nœud a déjà été imprimé? Il me semble que cela imprimerait simplement la valeur minimale à plusieurs reprises ou une fois avant de passer à la valeur maximale, mais apparemment, les nœuds sont vérifiés d'une manière ou d'une autre.
Il ne reste pas une trace des nœuds visités lorsque vous supposez. Il traverse aussi loin que possible sur le côté gauche de l'arbre avant de revenir à la racine et de visiter le côté droit en cours de route.
Comment toutes les valeurs sont-elles imprimées? Par exemple, si la deuxième plus petite valeur est le nœud droit de la troisième valeur la plus petite, quelle est la deuxième plus petite valeur de valeur?
car à chaque appel récursif, il imprime la valeur de la "racine" actuelle.
Vous remarquerez peut-être des réponses (dont plusieurs sont très bonnes!) Que leurs exemples ne sont pas nécessaires BSTS. C'est parce que le contenu de l'arborescence n'est pas pertinent pour la manière dont les travaux de traversée des inondérations. Tout arbre binaire peut être traversé dans une méthode des introductions. Mais une traversée d'inondation est importante pour BSTS, car c'est le moyen d'énumérer tous les éléments de manière triée.
TLDR: Cela dit visiter le nœud gauche, puis imprimez la valeur sur le nœud actuel, visitez enfin le nœud droit.