Quelle est la meilleure façon de visiter tous les nœuds d'un arbre lié (tous les nœuds ont des références aux parents et à tous les enfants, les nœuds racines ont null comme parent), de sorte qu'aucun nœud n'est visité avant l'un de ses ancêtres? Points brownie pour non récursif.
10 Réponses :
Construire une liste de nœuds à la racine (niveau 0), itérer sur chaque nœud à tour de rôle et recherchez des enfants directs (dont le nœud parent est le nœud que nous recherchons actuellement) (niveau 1), lorsque vous avez terminé de niveau 0 Passez à Iterating Niveau 1, et ainsi de suite jusqu'à ce que vous n'ayez pas de nœuds non visités restants.
Utilisez un ensemble de nœuds. Mettre la racine dans l'ensemble pour commencer. Ensuite, dans une boucle, tirez un nœud hors de l'ensemble, visitez-le, puis mettez ses enfants dans l'ensemble. Lorsque l'ensemble est vide, vous avez terminé.
Vous voulez que la structure de données soit FIFO, pas seulement un ancien conteneur, de garantir la condition pré-commande.
Il n'y avait pas de telle exigence dans la question.
en pseudocode:
Vous recherchez une traversée pré-commande. Je pense que vous pouvez le faire de manière non récursive avec une queue:. Dans pseudocode:
Créez une file d'attente vide, puis poussez le nœud racine.
Ce serait une implémentation non récidive d'un algorithme reconsive . Le remplacement de la pile implicite avec une pile explicite ne tourne pas d'un algorithme récursif en une non récursive. En fait, cela ne change pas du tout l'algorithme. Ce que vous avez ci-dessus est évidemment récursif (en ce qui concerne l'algorithme).
Typiquement, lorsque les gens disent qu'ils ne veulent pas de récursion, ils se réfèrent à la récursion au niveau de la fonction. Cela satisfait à cette condition.
Eh bien, parfois oui. Cependant, le problème que nous considérons ici est spécifiquement conçu pour permettre une solution véritablement non récursive (c'est-à-dire un algorithme non récursif). Le cadeau mort est la présence de pointeurs parent. Votre solution «non récursive» n'utilise pas les pointeurs parent. Ne vous demandez-vous pas pourquoi ils sont même là? Ils sont là spécifiquement pour permettre une véritable solution non récursive, celle avec O (1) de mémoire.
Mais la plupart du temps - non. Typiquement, lorsque les gens disent qu'ils ne veulent pas de récursion, ils signifient qu'ils ne veulent pas que la mémoire de récursives de récursivité, c'est-à-dire qu'ils ne veulent pas avoir une structure de données de taille non constante pour stocker des «sous-programmes», que ce soit FIFO , Lifo ou quoi que ce soit d'autre.
@Andret: Je ne pense pas avoir jamais entendu parler de "non récursif" utilisé pour signifier "besoin d'espace constant" comme vous semblez croire. Je dois donc être en désaccord que votre usage est "typique".
@Jim Lewis: Tout d'abord, il ne s'agit pas que de "exigence d'espace constant" en général (je n'ai jamais dit cela). Il est un nombre constant de sous-tâches "planifiées" (et donc d'espace constant pour stocker ces sous-tâches). Deuxièmement, c'est dommage que vous n'ayez jamais entendu parler de cela. Parce que c'est en fait une propriété déterminante d'algorithme non récursif . Le manque de compréhension de ce que le terme "algorithme récursif" signifie et le manque de compréhension de la différence entre "algorithme" et "mise en œuvre" est plutôt applicable ces jours-ci.
Quand les gens montent avec une implémentation non récursive en mettant en œuvre des algorithmes reconsive avec une pile fabriquée à la main (par opposition à l'utilisation d'une pile fonctionnelle), puis appelez-le Algorithme non récursif ... c'est juste ... bien ... ridicule, pour le manque de meilleur mot.
@Andreyt: Et ce pourrait être un moyen facile de marcher autour des limites de la pile de fonctions dans des langages de programmation comme Python ...
pseudo code: edit : récursif ou pas?
Pour être techniquement correct, et comme indiqué par Andreyt et d'autres dans ce poste, cette approche est
D'ACCORD. Ce n'était pas une question académique. C'était une question pratique. Cela répond à une manière satisfaisante sans me faire penser ou faire de nouvelles lecture. Merci. (Cela me fera probablement penser plus tard quand je reçois le temps, mais ça va ... utile, même ...) Le travail est fait. Merci encore :)
Si vous commencez au nœud racine, et seulement visitez les parents / enfants des nœuds que vous avez déjà visités, il y a aucun moyen pour traverser l'arbre tel que vous visitez un nœud avant de visiter ses ancêtres .
Toute sorte de traversé, profondeur d'abord (à base de tâche reconsive / pile), d'une largeur d'abord (basée sur la file d'attente), de profondeur-peu limitée, ou simplement de les tirer hors d'un ensemble non ordonné, fonctionnera.
La méthode "meilleure" dépend de l'arbre. La largeur d'abord fonctionnerait bien pour un très grand arbre avec peu de branches. La profondeur d'abord fonctionnerait bien pour les arbres avec de nombreuses branches.
Étant donné que les nœuds ont réellement des pointeurs à leurs parents, il existe également un algorithme de mémoire constant, mais il est beaucoup plus lent.
Teh Op a dit " NO Node est visité avant ses ancêtres". C'est donc l'inverse.
Peut être pas. Je pensais que dans votre première phrase, vous avez prétendu que le problème ne peut pas être résolu, puisque l'ordonnance de visite requise (qui, j'ai supposée, vous avez mal compris) est impossible à satisfaire.
Je faisais le point que tout traversif (à partir du nœud racine) répondrait à l'exigence.
Si vous avez des liens vers tous les enfants et pour le parent également, alors l'algorithme non récursif est plutôt trivial. Il suffit d'oublier que vous avez un arbre. Pensez à c'est un labyrynthe où chaque liaison parent-enfant est un couloir bidirectionnel ordinaire d'une jonction à l'autre. Tout ce que vous avez à faire pour parcourir tout le labyrinthe est de se transformer en couloir suivant à gauche à chaque jonction. (En variante, pensez-y comme marquant le labyrinthe avec votre main gauche touchant toujours le mur sur le côté gauche). Si vous commencez à partir de la jonction racine (et allez-vous dans n'importe quelle direction), vous passerez à l'arbre entier toujours en visite aux parents avant les enfants. Chaque "couloir" dans ce cas sera parcouru deux fois (dans une direction et dans l'autre), et chaque "jonction" (noeud) sera visité autant de fois que de nombreux "corridors" le rejoindre.
C'est l'algorithme de mémoire constant que j'ai mentionné.
Je serais en désaccord avec la première recherche d'une première recherche car la complexité de l'espace est souvent le fléau de cet algorithme de recherche spécifique. L'utilisation d'un algorithme d'approfondissement itératif est peut-être une meilleure alternative pour ce type d'utilisation et couvre le même type de traversée que la première recherche de la largeur. Il existe des différences mineures dans le traitement de la frange de la largeur de la première recherche, il ne devrait pas être trop difficile pour (pseudo) du code.
+1 En raison de votre considération complexité spatiale - mais pourquoi ne pas simplement utiliser une première recherche de profondeur?
De nombreux arbres en pratique ont tendance à être plus profonds qu'ils ne sont «plus grands», esp. dans les processus décisionnels de l'AI. La question n'éteigne pas si l'arbre est fini, mais vous pourriez rencontrer une boucle. L'une des raisons pour lesquelles l'approfondissement itératif est apprécié est qu'il est complet (trouver une solution).
Voici une approche véritable non récursive: pas de pile, espace constant. Ce code Python suppose que chaque nœud contient une liste d'enfants, et que les objets de nœud ne définissent pas l'égalité, de sorte que la fonction "index" comparait des identités: Je suis sûr que ça pourrait être polie un peu, rendu plus concis et plus facile à lire, mais c'est le gist.
Connexes: Stackoverflow.com/Questtions/754439/itétive-tree-walking