Arbre binaire de afinde et postorder

J'ai juste commencé à étudier l'Arbre Binaire. Est-il un algorithme pour trouver l'arbre binaire de la structure,compte tenu de la Afinde et Postorder OU Afinde et Précommande? J'ai essayé de le faire manuellement,mais il ne sort jamais correct.Pour eg.-Ces deux sont valables Afinde et Postorder de la traversée d'un arbre:

Afinde: D B F E A G C L J H K
Postorder : D F E B G L J K H C A

Clairement Un est la racine que c'est le dernier élément dans Postorder. Maintenant, en regardant dans Afinde,le sous-arbre gauche devient: {D B F E} et de droit de la sous-arborescence devient: {G C L J H K}. La racine du sous-arbre droit serait l'avant-dernier élément en précommande je.e C. je peut maintenant diviser davantage le sous-arbre droit(avec C en tant que root), donnant {G} comme sous-arbre droit et {L J H K} comme de gauche. Donc j'ai cette structure:

                               A
                                \
                                 C
                                / 
                               G

Mais,quel que soit l'algorithme I s'appliquent,à côté semble fonctionner différemment pour les différents arbres . Quelqu'un veuillez expliquer.

  • divide […subtree] with C as root), giving {G} as right subtree and {L J H K} as left - ce a les "étiquettes" de gauche et de droite inversée
InformationsquelleAutor Kanwaljeet Singh | 2012-09-23
  1. 1

    Si je comprends ce que votre demande, votre tentative de reconstituer la structure sous-jacente pour un arbre binaire de l'algorithme de recherche compte tenu de ces données brutes, il est pré-et post-état. Si c'est le cas, vous pourriez être en bas d'un chemin difficile puisque, bien que l'algorithme de base est le même, il pourrait y avoir des nuances selon le développeur de construire l'algorithme puisque, dans la pratique, il est souvent le cas, les développeurs ne pas construire une pure mise en œuvre de ces algorithmes.

    Si votre juste essayer d'obtenir une meilleure compréhension des arbres binaires, ce qui peut expliquer un peu mieux: http://www.youtube.com/watch?v=ZkH3SSPwcwI

    • Oui c'est exactement ce que je veux savoir. L'obtention de la structure en arborescence donné tous les deux de la traversée. BTW, Le lien a été utile en me faisant comprendre le parcours de schéma par le biais de la récursivité. Pas tranquille, ce que je cherche
    InformationsquelleAutor Dave
  2. 0

    Laissez-les aussitôt et précommande traversals être donnée dans les tableaux de iorder et porder respectivement.

    La fonction pour construire l'arbre sera désigné par buildTree(i,j,k) où i,j reportez-vous à la plage de la afinde tableau pour être regardé et k est la position de la précommande tableau.

    Appel Initial sera buildTree(0,n-1,0)

    L'algorithme a les étapes suivantes:

    1. Traverse porder depuis le début. Le premier nœud est la racine, nous avons alors le sous-arbre gauche, puis le sous-arbre droit. Créer un noeud avec ce que l'élément.

    2. Recherche le nœud dans la iorder tableau. Supposons que son trouvé à x. Décrémenter k. k correspond à la position dans la porder tableau nous vivons actuellement. k doit être passé par référence.

    3. Enfin remplir la gauche de l'enfant et de droit de l'enfant avec la valeur de retour des appels récursifs
      gauche de l'enfant = buildTree(i,x-1,k)
      droit de l'enfant = buildTree(x+1,j,k)

    4. Dans la déclaration de fin le nœud

    PS: j'Ai le code avec l'algorithme ci-dessus à

    http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=477

    InformationsquelleAutor Jonh