Utilité de la traversée pré et post-ordre des arbres binaires

Cela peut être très naïf, mais je me demandais, le contexte des arbres binaires (simples, triés et équilibrés), de tous les types de parcours:

• pré-commande en profondeur
• profondeur d'abord dans l'ordre
• profondeur après la commande
• largeur en premier

quelle est l'utilité réelle de celles pré et post-commande? Je veux dire, y a-t-il un type et / ou une configuration d'arbre binaire dans lequel la traversée pré et / ou post-ordre donnerait un (certains) avantage (s) par rapport aux deux autres?

AFAICS, il existe certains types et configurations d'arbres binaires pour lesquels l'ordre et la largeur en premier pourraient donner un certain avantage:

• pour un arbre binaire équilibré, toute traversée en profondeur d'abord utilisera moins d'espace de stockage en mémoire que la largeur en premier (par exemple, pour un arbre binaire équilibré de 6 ou 7 nœuds, la hauteur est de 2, donc toute traversée en profondeur d'abord devra stocker un maximum de 2 nœuds à un moment donné, tandis que le dernier niveau a 3 ou 4 nœuds, la traversée en largeur doit donc stocker jusqu'à 3 ou 4 nœuds à un moment donné). Dans ce cas, l'utilisation de la traversée dans l'ordre utilise le moins de mémoire et visite les nœuds dans leur ordre naturel.

• pour un arbre binaire non équilibré, s'il est proche du pire scénario d'insertion, le traverser en premier utiliserait moins de mémoire que n'importe lequel des parcours en profondeur. Dans ce cas, l'ampleur offre donc un avantage. La traversée dans l'ordre présente encore l'avantage de visiter les valeurs dans leur ordre naturel.

Cependant, je ne peux pas penser à une situation où la pré et la post-traversée donneraient un avantage sur les deux autres.

L' article wikipedia a une belle description concise du moment où vous souhaitez utiliser les différents types de recherche en profondeur d'abord:

• La pré-commande de la traversée lors de la duplication des nœuds et des valeurs peut créer un doublon complet d'un arbre binaire. Il peut également être utilisé pour créer une expression de préfixe (notation polonaise) à partir d'arbres d'expression: parcourez l'arbre d'expression de manière pré-ordonnée.
• La traversée dans l'ordre est très couramment utilisée sur les arbres de recherche binaire car elle renvoie les valeurs de l'ensemble sous-jacent dans l'ordre, selon le comparateur qui a configuré l'arbre de recherche binaire (d'où le nom).
• La traversée post-commande lors de la suppression ou de la libération de nœuds et de valeurs peut supprimer ou libérer un arbre binaire entier. Il peut également générer une représentation postfixe d'un arbre binaire.

Cela se résume aux besoins logistiques d'un algorithme. Par exemple, si vous n'utilisez pas la traversée post-commande pendant la suppression, vous perdez les références dont vous avez besoin pour supprimer les arbres enfants.

Vous devez faire diverses choses avec des arbres, comme traduire entre la structure de données et une représentation série, comme sur un fichier ou dans une langue.

Par exemple, supposons que vous ayez un arbre d'analyse comme celui-ci:

    *
   / \
  +   \
 / \   \
A   B   C

Vous pouvez le sérialiser * + A B Cen le parcourant dans l'ordre des préfixes, ou A B + C *en le parcourant dans l'ordre des suffixes. Si vous travaillez avec des processeurs de langage, ces choses doivent être de seconde nature.

L'intérêt d'avoir différents algorithmes pour gérer les arbres binaires n'est pas de faire des choses avec les arbres. À ce niveau abstrait, un ordre est en grande partie aussi bon que n'importe quel autre, car vous n'obtenez que des symboles abstraits de la procédure.

Mais les arbres sont généralement utilisés pour représenter des choses intéressantes, et cela peut faire une grande différence dans le résultat. Par exemple, si les nœuds représentent des états de recherche dans une recherche complète à travers un grand domaine (peut-être même un domaine infini), la décroissance en premier par rapport au traitement en premier détermine non seulement l'ordre dans lequel les résultats sont trouvés, il peut même déterminer si vous trouver des solutions . Le point est plus facile à voir avec des domaines infinis: si vous descendez avec précaution, vous pourriez ignorer une solution qui se trouve assez haut dans l'arbre, simplement parce que vous avez pris un mauvais virage. Mais dans la pratique, comme la mémoire et les disques sont également finis, cela s'applique même aux domaines qui sont tout simplement très grands plutôt que vraiment infinis.