la reconstruction d'un arbre à partir de sa précommande et postorder listes

Vous ne pouvez pas utiliser une seule liste, parce que vous n'allez avoir aucun sens de la profondeur de l'arbre. Ainsi, vous avez certainement besoin de deux ou plusieurs listes.

Voici ma tentative de solution:

Utiliser votre précommande de la traversée comme un moyen de connaître le classement des données. Cela a un sens, parce que vous savez que le premier nœud est le top, et vous savez que de nouvelles données à la gauche de la traversée appartient à la gauche de l'arbre, etc.

Votre post afin de traversée peut déterminer la profondeur de l'arbre. Par exemple, disons que j'ai une structure comme ceci:

      1
  2   5   6
 3 4  7

Where 2 is the parent of 3 and 4, and 5 is the parent of 7.

Preorder: 1 2 3 4 5 7 6
Postorder: 3 4 2 7 5 6 1

Nous savons que nous commencez avec 1, car il est le premier nœud dans la précommande de la traversée. Ensuite, nous regardons le prochain numéro 2. Dans le poste de commande, parce que le numéro 2 vient AVANT que le nœud 1, nous savons que 2 doit être un enfant de 1. Nous examinerons ensuite 3. 3 vient avant 2, et donc 3 est un enfant de 2. 4 est avant le 2 mais après le 3, donc nous savons que 4 est un enfant de 2, mais PAS un enfant de 3. Etc.

Maintenant, cela peut ne pas fonctionner si les nœuds ne sont pas uniques, mais à tout le moins, un début de solution.

Edit: L'ordre des enfants est préservé grâce à cette solution, tout simplement en raison de connaître l'ordre des nœuds via la précommande de la traversée, puis de connaître la structure via le postorder traversée.

Edit2: La preuve en est peut-être là: http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel2%2F215%2F626%2F00017225.pdf%3Farnumber%3D17225&authDecision=-203

Je pense que vous devez vous procurer le document, mais...

Voici une preuve écrite présentée à être une solution:

http://www14.informatik.tu-muenchen.de/lehre/2007WS/fa-cse/tutorials/tutorial09-solutions.pdf

Envisager l'arbitraire d'un arbre T que le quadruple (A, B, C, D), où A est le nœud racine, B est le nœud racine du premier enfant, C est un vecteur de non-vide, les enfants de B, et D est un vecteur de non-vide frères et sœurs de B. éléments de La C et D sont eux-mêmes des arbres.

Tout de A, B, C et D peut être vide. Si B est vide, et doit donc être C et D; si A, alors tout.

Depuis les nœuds sont uniques, les ensembles de nœuds contenus n'importe où dans C et D sont disjoints, et ne contient ni A ou B.

Fonctions pre() et post() générer des séquences ordonnées de la forme:

pre(T) = [A, B, pré(C), pré(D)]

post(T) = [post(C), B, post(D), A]

où la fonction appliquée à un vecteur est défini à la concaténation des séquences résultant de l'application de la fonction à chaque élément à son tour.

Considérons maintenant le cas:

• si A est vide, la sortie de ces deux fonctions est la séquence vide []
• si B est vide, la sortie de ces deux fonctions est juste [A]
• si C et D sont vides, pre(T) = [A, B] et post(T) = [B, A]
• si seulement C est vide, pre(T) = [A, B, D'] et post(T) = [B, D", A] (où les premiers indiquent une certaine permutation des nœuds contenus dans D)
• si seulement D est vide, pre(T) = [A, B, C'] et post(T) = [C", B, A]
• si rien n'est vide, pre(T) = [A, B, C', D'] et post(T) = [C", B, D", A]

Dans tous les cas, nous pouvons sans ambiguïté partition les membres des deux sorties de séquences en séquences, en utilisant A et B (si présent) comme délimiteurs.

La question est, peut-on également partition le vecteur des séquences? Si nous le pouvons, les uns peuvent être traitées de manière récursive et nous y sommes.

Depuis le résultat de pre() sera toujours une chaîne de séquences de départ avec Une nœuds, et le résultat de post() sera toujours une chaîne de séquences fin avec Une nœuds, en effet, on peut les diviser, fourni que l'Un des nœuds ne sont jamais vides.

C'est là que le processus tombe dans le cas binaire (voire aucune) des arbres fixes avec des enfants qui peuvent indépendamment être vide. Dans notre cas, cependant, nous avons défini C et D, ne contiennent que des non-nœuds vides, et donc la reconstruction est garanti pour fonctionner.

Euh, je pense que oui, de toute façon. Évidemment, c'est juste un argument, pas une preuve formelle!

Comme déjà souligné par d'autres, un arbre binaire peut pas être reconstruit en utilisant uniquement des pré-et post-ordre de la traversée. Un nœud enfant unique a ambigu traversals qui ne peuvent pas déterminer si c'est la gauche ou la droite de l'enfant par exemple, envisager la suite de précommande et postorder traversals:
précommande: a,b
postorder b,un

Il peut produire à la fois des arbres suivants

un un
\ /
b b
Il n'est tout simplement pas possible de savoir si b est une droite ou gauche d'enfant sans informations supplémentaires comme afinde traversée.

Il n'est pas possible de construire un général de l'Arbre Binaire de précommande et postorder traversals (Voir ceci). Mais si savoir que l'Arbre Binaire est Complet, on peut construire l'arbre sans ambiguïté. Nous comprenons ce avec l'aide de l'exemple suivant.

Considérons les deux tableaux en tant que pré[] = {1, 2, 4, 8, 9, 5, 3, 6, 7} et après[] = {8, 9, 4, 5, 2, 6, 7, 3, 1};
Dans le pré[], l'élément le plus à gauche est la racine de l'arbre. Depuis l'arbre est plein et la taille de la matrice est plus que de 1. La valeur 1 dans le pré[], doit être laissé à l'enfant de la racine. Donc, nous savons que 1 est racine et 2 est à gauche de l'enfant. Comment trouver tous les nœuds dans le sous-arbre gauche? Nous savons que 2 est une racine de tous les nœuds dans le sous-arbre gauche. Tous les nœuds avant le 2 en post[] doit être dans le sous-arbre gauche. Maintenant, nous savons que 1 est une racine, des éléments {8, 9, 4, 5, 2} sont dans le sous-arbre gauche, et les éléments de {6, 7, 3} sont dans le sous-arbre droit.

              1
            /  \
           /     \
 {8, 9, 4, 5, 2}     {6, 7, 3}

Nous récursive de suivre l'approche ci-dessus et obtenir l'arbre suivant.

      1
    /  \
  2       3
/ \     / \

4 5 6 7
/\

8 9