La traversée en précommande est-elle la même que la recherche en profondeur en premier?

13

Il me semble que la traversée en pré-ordre et DFS sont les mêmes que dans les deux cas, nous traversons de la racine jusqu'à la branche gauche et revenons à la racine puis à la branche droite récursivement. Pourriez-vous me corriger si je me trompe?

Merci d'avance!

algorithms trees binary-tree graph-traversal Srikanth Kandalam
la source

Réponses:

10

la traversée pré-commande est une traversée, elle visite chaque nœud dans un arbre binaire

Depth First Search est une recherche, il fait le tour d'un graphe arbitraire à la recherche d'un certain nœud (qu'il fonctionne mieux dans un graphe non cyclique (aka arbre) est sans importance)

cela seul est une différence assez grande pour les appeler des noms de différence

monstre à cliquet
la source
1
+1, mais j'aimerais ajouter que les traversées pré et post-commande ne sont que des cas particuliers de la stratégie DFS plus générale.
Frank
1
La traversée en précommande ne signifie-t-elle pas simplement le traitement des nœuds avant leurs enfants? Où dit-on que les nœuds forment un arbre binaire, ou même un arbre?
Kilian Foth
@KilianFoth Je m'attendrais à ce que l'implication d'un nœud ayant des enfants (par opposition aux voisins) implique une structure arborescente car elle suggère une hiérarchie de nœuds. Le sommet de la hiérarchie étant la racine de l'arbre. Mais je peux imaginer que la traversée pré-ordre et la traversée post-ordre aient du sens sur n'importe quel arbre, même ceux qui ne sont pas binaires.
YoungJohn
1

Oui, mais cela devrait être le contraire: DFSest similaire à PreOrder.
Le terme PreOrderest plus pertinent pour les arbres binaires et les analyseurs.
Il est utilisé pour comparer avec les autres ordres traversal d'un arbre binaire: InOrder, PostOrderet PreOrder.
Le tri topologique est similaire à la traversée Post Order (pousser le nœud dans la pile après avoir visité tous les nœuds adjacents).

user640554
la source
Mes pensées sont similaires à cette réponse. Plus précisément, une précommande est une implémentation spécifique de la catégorie parente de DFS. La traversée des enfants en pré-commande est rigide à gauche puis à droite; alors que pour le DFS générique (parent), l'ordre de traversée des enfants n'est pas défini et pourrait être n'importe quel ordre.
Jerred S.10
-1

Pour parcourir un arbre binaire en précommande, les opérations suivantes sont effectuées

  1. Visitez la racine
  2. Traverser le sous-arbre gauche
  3. Traverser le sous-arbre droit

C'est dans l'image ci-dessous que la traversée de l'ordre préalable serait, 1,2,3,6,4,5,7,8,9,10,11,12

Dans la même image 1,2,3,4,5,6,7,8,9,10,11,12 serait pour DFS

Source DFS: http://datastructuresnotes.blogspot.in/2009/02/binary-tree-traversal-preorder-inorder.html

Source de précommande: Wiki

DFS

Zedaiq
la source
9
Ce n'est pas un arbre binaire. C'est un arbre, mais pas binaire.
Manoj R
Que se passe-t-il lorsque "6" a des sous-nœuds?
Marjan Venema
Vous demandez DFS ou pré-commande?
Zedaiq
@ManojR Je l'ai obtenu de la source mentionnée ci-dessus.
Zedaiq
la pré-commande dans ce graphique donne la même réponse
Charles Chow