Convertir Précommande inscription d'un arbre binaire de postorder et vice versa
Comment puis-je trouver la précommande liste d'un arbre, si seulement la postorder liste est donnée et vice versa. Aussi, dans l'arbre, chaque nœud non-feuille a deux enfants (c'est à dire que Chaque nœud a deux ou zéro des enfants.)
EDIT: Autre, compte tenu de l'hypothèse est que l'étiquette de chaque nœud est unique et possède un champ qui permettra de l'identifier comme un noeud interne ou d'une feuille. Je pense qu'elle devrait se débarrasser de l'ambiguïté d'un seul précommande ou postorder être en mesure d'identifier de manière unique un arbre.
OriginalL'auteur Jaelebi | 2009-08-02
Vous devez vous connecter pour publier un commentaire.
Sans supposer que les nœuds dans l'arbre ont un champ qui idenrify eux-mêmes en tant qu'interne ou de la feuille, vous ne pouvez pas trouver une réponse unique pour votre question. Cette hypothèse ou afinde liste doit être disponible pour trouver un arbre unique.
Dans ce cas, de trouver une réponse possible, vous pouvez construire un arbre de la forme présentée ci-dessous correspond à aucune donnée postorder d'inscription: (à supposer que postorder liste est: 1 2 3 4 5 6 7 8 9)
Maintenant, vous pouvez faire précommande liste à l'aide de cet arbre.
En supposant que les nœuds dans l'arbre ont un champ qui s'identifient en tant qu'interne ou de la feuille, on peut faire un arbre unique d'un postorder de liste de ce genre d'arbres avec cet algorithme:
Non, ce ne serait pas le rendre unique. Considérons cet exemple: 5[1,4[2,3]] et 5[3[1,2],4]. Précommande de la traversée de deux, arbres de résultats 1 2 3 4 5.
Que faire si le nœud a un champ qui a été en mesure d'identifier une feuille ou d'un noeud interne?
Qui le rendent unique. Je poste une réponse pour elle.
OriginalL'auteur Mohammad Alinia
Considérer la structure récursive d'une précommande de la traversée:
Alors nous savons que la racine d'une arborescence décrite par T(r) est toujours le premier nœud dans la traversée.
Sachant cela et sachant qu'une racine est toujours plus élevée dans un arbre de ses sous-arbres, pensez à comment vous pouvez utiliser cette information pour reconstruire l'arbre. Penser de manière récursive.
Mise en garde: ce ne peut être fait que si c'est un binaires de recherche arbres, ce qui limite les nœuds tels que
left-child < root < right-child
. En général, les arbres ne peuvent pas être reconstruites à partir d'une seule traversée. Voir cette excellente ressource pour une explication plus détaillée.Ambiguïté existe toujours, indépendamment de la règle sur 0 ou 2 enfants:
Les deux ont la précommande de la traversée [4 2 1 3 5 6 7]
J'ai édité ma réponse à montrer un contre-exemple prouvant que l'ambiguïté existe toujours.
Vous devez imprimer le postorder de la traversée pour les deux arbres à prouver l'ambiguïté, puisque seulement traversals sont comparés.
Si chaque nœud a un champ qui a été en mesure d'identifier une feuille ou d'un noeud interne?
oui, cela fonctionne ensuite. Intéressant de côté, vous pouvez reconstruire l'arbre, si vous aviez à la fois avant et après la traversée de l'ordre, comme je l'ai rappel.
OriginalL'auteur alanlcode
Par exemple:
vous devez convertir postorder formulaire de précommande forme.cela peut être fait de la manière suivante.
ordre de poste: DEBFCA
précommande: ABDECF
nous voyons que A est la racine. et à partir de précommande, nous pouvons déterminer que le nœud B est à gauche de A. par conséquent, nous devons créer deux sous-classes qui sont (LIT) (CF).maintenant, quand on traverse B nous prendre comme une racine et nous voyons que, après B, D EST PRÉSENT ,cela signifie que D est à gauche de B et E est en droit de B .maintenant, nous traversons C. le prendre comme une racine.alors F est présent après le C de sorte qu'il est pris comme de gauche.
OriginalL'auteur anjali kumari