Quelqu'un at-il écrit ou pensé à écrire un itérateur pour un composite (arbre) sans utiliser récursion? Si oui pouvez-vous partager vos idées? ThksStructure iterator Motif composite sans récursion
Edit: Je pensais à Java pour lang.
Traversant un arbre sans récursion est assez simple. En supposant un arbre binaire, chaque noeud a vraisemblablement trois références aux autres noeuds. Enfant gauche, enfant droit et parent. en supposant donc une profondeur d'abord ordre de gauche à droite itération, vous suivez les références aux enfants gauche dans un certain temps-lop (pseudocode while current.left-child != null, current = current.left-child) s'il n'y a pas de gauche enfant, vous essayez l'enfant à droite. S'il n'y a pas droit de l'enfant soit, vous allez jusqu'à ce que vous trouviez un droit enfant (while current.right-child == null, current = current.parent)
Vous n'avez pas spécifié une langue, mais puisque vous voulez éviter récursion, je vais supposer qu'il est un impératif langue d'une certaine sorte, et ce qui précède devrait être possible.
En bref, votre itérateur doit contenir une référence au noeud courant, et quelques informations sur ce qui est comme il voyage.
Vous pourriez vous inspirer de cette question SO: Post order traversal of binary tree without recursion Tout ce dont vous avez besoin est d'étendre l'algorithme aux arbres non binaires.
D'accord avec le traversal arbre binaire, mais je ne voulais pas prendre un arbre binaire. – Vidhya
Eh bien, il est difficile de traverser un arbre sans faire une sorte de supposition sur sa structure. La même approche peut être modifiée de manière triviale pour n'importe quelle structure arborescente. Parcourez ses enfants, puis le parent et essayez le prochain nœud enfant – jalf