Quand utiliser les stratégies de traversée d'arbre de recherche binaire Preorder, Postorder et Inorder

97

J'ai réalisé récemment que tout en ayant utilisé l'abondance de BST dans ma vie, je n'ai même jamais envisagé d'utiliser autre chose que la traversée Inorder (alors que je suis conscient et je sais à quel point il est facile d'adapter un programme pour utiliser la traversée pré / post-commande).

En réalisant cela, j'ai sorti certains de mes anciens manuels sur les structures de données et j'ai cherché un raisonnement derrière l'utilité des traversées de pré-commande et de post-commande - ils n'ont cependant pas dit grand-chose.

Quels sont quelques exemples d'utilisation pratique de la pré-commande / post-commande? Quand cela a-t-il plus de sens que dans l'ordre?

John Humphreys - W00TE
la source

Réponses:

135

Quand utiliser la stratégie de traversée des précommandes, des commandes et des post-commandes

Avant de pouvoir comprendre dans quelles circonstances utiliser la pré-commande, dans l'ordre et la post-commande pour un arbre binaire, vous devez comprendre exactement comment fonctionne chaque stratégie de traversée. Utilisez l'arborescence suivante comme exemple.

La racine de l'arbre est 7 , le nœud le plus à gauche est 0 , le nœud le plus à droite est 10 .

entrez la description de l'image ici

Parcours de précommande :

Résumé: commence à la racine ( 7 ), se termine au nœud le plus à droite ( 10 )

Séquence de traversée: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Traversée dans l'ordre :

Résumé: commence au nœud le plus à gauche ( 0 ), se termine au nœud le plus à droite ( 10 )

Séquence de traversée: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Traversée post-commande :

Résumé: commence par le nœud le plus à gauche ( 0 ), se termine par la racine ( 7 )

Séquence de traversée: 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

Quand utiliser la pré-commande, la commande ou la post-commande?

La stratégie de traversée choisie par le programmeur dépend des besoins spécifiques de l'algorithme en cours de conception. L'objectif est la vitesse, alors choisissez la stratégie qui vous apporte les nœuds dont vous avez besoin le plus rapidement.

  1. Si vous savez que vous devez explorer les racines avant d'inspecter les feuilles, vous choisissez la précommande car vous rencontrerez toutes les racines avant toutes les feuilles.

  2. Si vous savez que vous devez explorer toutes les feuilles avant les nœuds, vous sélectionnez la post-commande car vous ne perdez pas de temps à inspecter les racines à la recherche de feuilles.

  3. Si vous savez que l'arborescence a une séquence inhérente dans les nœuds et que vous souhaitez l'aplatir dans sa séquence d'origine, une traversée dans l'ordre doit être utilisée. L'arbre serait aplati de la même manière qu'il a été créé. Un parcours de pré-commande ou de post-ordre peut ne pas dérouler l'arborescence dans la séquence qui a été utilisée pour le créer.

Algorithmes récursifs pour la pré-commande, la commande et la post-commande (C ++):

struct Node{
    int data;
    Node *left, *right;
};
void preOrderPrint(Node *root)
{
  print(root->name);                                  //record root
  if (root->left != NULL) preOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) preOrderPrint(root->right);//traverse right if exists
}

void inOrderPrint(Node *root)
{
  if (root.left != NULL) inOrderPrint(root->left);   //traverse left if exists
  print(root->name);                                 //record root
  if (root.right != NULL) inOrderPrint(root->right); //traverse right if exists
}

void postOrderPrint(Node *root)
{
  if (root->left != NULL) postOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) postOrderPrint(root->right);//traverse right if exists
  print(root->name);                                   //record root
}
Eric Leschinski
la source
3
Qu'en est-il des traversées non récursives? Il me semble qu'il est beaucoup plus facile de parcourir un arbre de manière non récursive en pré-ordre par rapport à in-order / post-order, car il ne nécessite pas de revenir aux nœuds précédents.
bluenote10
@ bluenote10 Pouvez-vous expliquer ce que vous voulez dire? En pré-commande, vous «retournez» toujours vers un nœud pour traiter son enfant droit après avoir traité son enfant gauche. Bien sûr, vous pouvez utiliser une file d'attente de "nœuds non encore visités", mais c'est en fait juste un échange de stockage implicite (pile) contre une file d'attente explicite. Dans toutes les méthodes de traversée, les enfants de gauche et de droite doivent être traités, ce qui signifie qu'après avoir fait l'un d'eux, vous devez "retourner" au parent.
Joshua Taylor
@JoshuaTaylor: Oui, ils sont tous de la même classe de complexité, mais si vous regardez les implémentations typiques, la post-commande est probablement un peu plus délicate.
bluenote10
2
Le cheminement de précommande donne les valeurs des nœuds dans une séquence d'insertion. Si vous souhaitez créer une copie de l'arborescence, vous devez parcourir l'arborescence source de cette manière. Le cheminement dans l'ordre donne les valeurs de nœud triées. En ce qui concerne la traversée post-ordre, vous pouvez utiliser cette méthode pour supprimer tout l'arbre car il visite les nœuds feuilles en premier.
albin
Je pense que c'est vrai même si l'arbre n'est pas bien ordonné, je veux dire que dans l'ordre ne donnerait pas la séquence triée si la séquence n'était pas triée au début.
CodeYogi
29

Précommande: permet de créer une copie d'un arbre. Par exemple, si vous souhaitez créer une réplique d'un arbre, placez les nœuds dans un tableau avec un parcours de pré-commande. Effectuez ensuite une opération d' insertion sur une nouvelle arborescence pour chaque valeur du tableau. Vous vous retrouverez avec une copie de votre arbre d'origine.

Dans l'ordre:: Utilisé pour obtenir les valeurs des nœuds dans un ordre non décroissant dans un BST.

Post-commande:: permet de supprimer un arbre de la feuille à la racine

Viraj Nimbalkar
la source
2
c'est une excellente réponse concise qui m'a aidé à comprendre les cas d'utilisation de pré-commande et de post-commande. bien que cela puisse être évident étant donné que la question le mentionne directement, mais notez que c'est le cas pour les arbres binaires de RECHERCHE et ne fonctionne pas nécessairement pour les arbres binaires généraux. par exemple, vous ne pouvez pas nécessairement utiliser la traversée de pré-commande pour copier un arbre binaire général, car la logique d'insertion pendant le processus de copie ne fonctionnerait pas.
markckim
7
Dans l'ordre:: Pour obtenir les valeurs du nœud dans l'ordre "non décroissant" - et non "non croissant"
rahil008
26

Si je voulais simplement imprimer le format hiérarchique de l'arbre dans un format linéaire, j'utiliserais probablement le parcours de précommande. Par exemple:

- ROOT
    - A
         - B
         - C
    - D
         - E
         - F
             - G
Oliver Charlesworth
la source
4
Ou dans un TreeViewcomposant dans une application GUI.
svick
4

Le pré et le post-ordre concernent respectivement des algorithmes récursifs descendants et ascendants. Si vous voulez écrire un algorithme récursif donné sur des arbres binaires de manière itérative, c'est ce que vous ferez essentiellement.

Observez en outre que les séquences pré et post-ordre spécifient ensemble complètement l'arbre en question, ce qui donne un codage compact (au moins pour les arbres clairsemés).

Raphael
la source
1
Je pense que vous essayez de dire quelque chose d'important, pouvez-vous expliquer la première moitié?
CodeYogi
@CodeYogi De quoi avez-vous besoin d'expliquer spécifiquement?
Raphael
1
"Le pré et le post-ordre concernent des algorithmes récursifs descendants et ascendants" Je pense que vous voulez dire que dans le premier cas, le nœud est traité avant d'appeler l'une des méthodes récursives et vice-versa dans le dernier, à droite ?
CodeYogi
@CodeYogi Oui, en gros.
Raphael
2

Il y a des tonnes d'endroits où vous voyez cette différence jouer un rôle réel.

Un excellent que je soulignerai est la génération de code pour un compilateur. Considérez la déclaration:

x := y + 32

La façon dont vous généreriez du code pour cela est (naïvement, bien sûr) de générer d'abord du code pour charger y dans un registre, charger 32 dans un registre, puis générer une instruction pour ajouter les deux. Parce que quelque chose doit être dans un registre avant de le manipuler (supposons que vous pouvez toujours faire des opérandes constants mais peu importe), vous devez le faire de cette façon.

En général, les réponses que vous pouvez obtenir à cette question se résument essentiellement à ceci: la différence importe vraiment lorsqu'il y a une certaine dépendance entre le traitement de différentes parties de la structure de données. Vous voyez cela lors de l'impression des éléments, lors de la génération de code (l'état externe fait la différence, vous pouvez également l'afficher de manière monadique, bien sûr), ou lorsque vous effectuez d'autres types de calculs sur la structure qui impliquent des calculs en fonction des enfants traités en premier .

Kristopher Micinski
la source