Quand faut-il utiliser les stratégies de précommande, de post-commande et de recherche de l’arbre de recherche binary?

Je me suis rendu compte récemment que, bien qu’ayant utilisé l’abondance de BST dans ma vie, je n’avais jamais envisagé d’utiliser autre chose que la traversée Inorder (bien que je sache et qu’il est facile d’adapter un programme à la traversée pré / post-commande).

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

Quels sont les exemples d’utilisation de pré-commande / post-commande en pratique? Quand est-ce que cela a plus de sens que dans l’ordre?

    Quand utiliser la stratégie de traversée de pré-commande, en cours et post-commande

    Avant de pouvoir comprendre dans quelles circonstances utiliser un précommande, un ordre et un post-ordre pour un arbre binary, vous devez comprendre exactement comment fonctionne la stratégie de parcours. Utilisez l’arbre suivant 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 .

    entrer la description de l'image ici

    Traversée 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 d’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 transversale: 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 parcours choisie par le programmeur dépend des besoins spécifiques de l’algorithme en cours de conception. L’objective est la rapidité, choisissez donc la stratégie qui vous apporte le plus rapidement les nœuds dont vous avez besoin.

    1. Si vous savez que vous devez explorer les racines avant d’inspecter les feuilles, vous devez pré-commander 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 aplatir l’arborescence dans sa séquence d’origine, il convient d’utiliser une traversée dans l’ordre . L’arbre serait aplati de la même manière qu’il a été créé. Une traversée de pré-commande ou de post-ordre peut ne pas dérouler l’arborescence dans la séquence utilisée pour la créer.

    Algorithmes récursifs pour pré-commande, en ordre et 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 } 

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

     - ROOT - A - B - C - D - E - F - G 

    Pré-commande / En commande / Post-commande Utilisation: mots simples

    Pré-commande: Permet de créer une copie de l’arborescence Exemple: Si vous souhaitez créer une réplique d’une arborescence et avez besoin de valeurs de noeud dans un tableau et que vous insérez ces valeurs à partir de l’index 0 pour aboutir à une nouvelle arborescence, vous obtenez une réplique

    Dans l’ordre:: Pour obtenir des valeurs de noeud dans un ordre non croissant

    Post-commande:: lorsque vous souhaitez supprimer un arbre de feuille en racine

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

    Un bon exemple 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érez du code pour cela est (naïvement, bien sûr) de générer d’abord du code pour charger y dans un registre, de charger 32 dans un registre, puis de générer une instruction pour append les deux. Parce que quelque chose doit être dans un registre avant de le manipuler (supposons que vous puissiez toujours faire des opérandes constants, mais peu importe), vous devez le faire de cette façon.

    En général, les réponses à cette question se résument essentiellement à ceci: la différence est vraiment importante lorsqu’il existe 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 du code (l’état externe fait la différence, bien sûr, vous pouvez voir cela de manière monadique) ou lorsque vous effectuez d’autres types de calculs sur la structure. .

    Les pré et post-ordres concernent respectivement les algorithmes récursifs de haut en bas et de bas en haut. Si vous voulez écrire un algorithme récursif donné sur les arbres binarys 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 l’arbre en question, produisant un codage compact (pour les arbres rares au moins).