Conversion de la liste de pré-commande d'un arbre binaire en post-commande et inversement

Question

Comment puis-je trouver la liste de pré-commande d'un arbre si seule la liste de post-commande est donnée et inversement. De plus, dans l’arborescence, chaque nœud non-feuille a deux enfants (c’est-à-dire que chaque nœud a deux ou zéro enfants.)

EDIT: Une autre hypothèse donnée est que l'étiquette de chaque nœud est unique et comporte un champ qui l'identifiera en tant que nœud interne ou feuille. Je pense que cela devrait permettre de lever l’ambiguïté de l’identification unique d’un arbre par un pré-ordre ou un post-ordre.

Answer 1

Sans supposer que les nœuds de l’arborescence ont un champ qui s’identifie comme étant interne ou feuille, vous ne pouvez pas trouver une réponse unique à votre question. Cette hypothèse ou cette énumération en ordre doit être disponible pour trouver un arbre unique. Dans ce cas, pour trouver une réponse possible, vous pouvez construire un arbre de la forme indiquée ci-dessous pour correspondre à une liste postorder donnée: (supposons que la liste postorder est: 1 2 3 4 5 6 7 8 9)

9[7[5[3[1,2],4],6],8]

Vous pouvez maintenant créer une liste de pré-commande en utilisant cet arbre.

En supposant que les nœuds de l’arbre aient un champ qui s’identifie comme étant interne ou feuille, nous pouvons créer un arbre unique à partir d’une liste postorder pour ce type d’arbre avec cet algorithme:

1. Balayez depuis le début de la liste de post-commande et recherchez le premier noeud interne. Ce nœud aura exactement deux enfants feuille qui le précèdent dans la liste postorder.
2. Dans votre arborescence, ajoutez ce nœud interne et définissez les deux nœuds précédents dans la liste de ses enfants.
3. Supprimez ces deux enfants de la liste et transformez ce nœud interne en feuille.
4. Allez à l'étape 1 et répétez jusqu'à ce que la liste soit vide.

Answer 2

Considérons la structure récursive d'une traversée de pré-ordre:

T(r) = [r, T(r->left), T(r->right)]
where T(r) is the preorder traversal of tree rooted at node r

Ensuite, nous savons que la racine d'un arbre décrit par T (r) est toujours le premier noeud du parcours.

Sachant cela et sachant qu'une racine est toujours plus haute dans un arbre que ses sous-arbres, réfléchissez à la manière dont vous utiliseriez ces informations pour reconstruire l'arbre. Pensez récursivement.

Mise en garde: cela ne peut être fait que s'il s'agit d'un arbre de recherche binaire , qui contraint les nœuds tels que left-child < root < right-child. En général, les arbres ne peuvent pas être reconstruits à partir d'une seule traversée. Voir cette excellente ressource pour une explication plus détaillée .

L’ambiguïté existe toujours quelle que soit la règle concernant 0 ou 2 enfants:

    4
   / \
  2   5
 / \ / \
 1 3 6 7

    4
   / \
  2   7
 / \
1   3
   / \
  5   6

Les deux ont la traversée en pré-ordre [4 2 1 3 5 6 7]

Answer 3

Par exemple: vous devez convertir le formulaire de post-commande en formulaire de précommande. Vous pouvez le faire de la manière suivante. commande postale: DEBFCA précommande: ABDECF nous voyons que A est la racine. et à partir du précommande, nous pouvons déterminer que le nœud B est laissé à A. Par conséquent, nous créons deux sous-classes qui sont (BED) (CF). À présent, lorsque nous traversons B, nous le prenons comme racine et nous voyons qu'après B, D EST PRÉSENT , cela signifie que D est laissé à B et E est à droite à B. maintenant nous traversons C. prenons-le comme une racine.