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 .
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.
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.
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.
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
}
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
la source
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:
la source
TreeViewcomposant dans une application GUI.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).
la source
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:
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 .
la source