Quand utiliser la stratégie d'annulation des commandes préalables, des commandes en cours et des commandes ultérieures ?
Avant de comprendre dans quelles circonstances il convient d'utiliser le pré-ordre, l'ordre interne et le post-ordre pour un arbre binaire, vous devez comprendre exactement comment chaque stratégie de traversée fonctionne. Prenons l'exemple de l'arbre suivant.
La racine de l'arbre est 7 le nœud le plus à gauche est 0 le nœud le plus à droite est 10 .
![enter image description here]()
Traversée d'un ordre préalable :
Résumé : Commence à la racine ( 7 ), se termine au nœud le plus à droite ( 10 )
Séquence de navigation : 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 d'inversion : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Traversée post-ordre :
Résumé : commence par le nœud le plus à gauche ( 0 ), se termine par la racine ( 7 )
Séquence d'inversion : 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7
Quand utiliser Pré-commande, En cours de commande ou 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 étant la rapidité, choisissez la stratégie qui vous permet d'accéder le plus rapidement aux nœuds dont vous avez besoin.
-
Si vous savez que vous devez explorer les racines avant d'inspecter les feuilles, vous choisissez 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 post-ordre car vous ne perdez pas de temps à inspecter les racines à la recherche de feuilles.
-
Si vous savez que l'arbre a une séquence inhérente dans les nœuds, et que vous voulez aplatir l'arbre pour lui redonner sa séquence d'origine, alors une commande en ordre doit être utilisé. L'arbre sera aplati de la même manière qu'il a été créé. Un parcours avant ou après l'ordre peut ne pas ramener l'arbre dans la séquence qui a été utilisée pour le créer.
Algorithmes récursifs pour le préordre, l'ordre interne et l'ordre externe (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
}
