Examen de la question à propos de l'insertion d'un vide arbre de recherche binaire

Je vais avoir des difficultés dans l'interprétation d'une certaine question à propos de l'insertion d'éléments à un arbre de recherche binaire. Je suis familier avec la précommande, postorder, et aussitôt traversals, mais je suis familier avec la question suivante:

Supposons que nous insérer les éléments 3, 5, 6, 1, 2, 4, 7 dans cet ordre dans un vide au départ binaires un arbre de recherche.

Si je ne suis qu'une série de chiffres qui sont insérés dans l'ordre, comment suis-je censé faire un arbre de recherche binaire? Serait-3 est la racine? Et je voudrais juste équilibre les autres numéros de la bonne sous-arbre par moi-même? Ne serait-il pas beaucoup d'interprétations dans ce cas? Y a t'il une convention qui est suivie?

Grâce.

OriginalL'auteur Jigglypuff | 2011-06-26

  1. 4

    Lorsque vous ajoutez un élément de l'arbre, l'arbre n'est pas réorganisées. Le nouvel élément est ajouté à un nœud feuille. Cela signifie que lorsque vous ajoutez 3, 3 sera le nœud racine de la raison. Lorsque vous ajoutez 5, il sera sur la droite de la 3, etc. Cela se traduit dans l'arbre suivant:

       3
 /  \
1     5
 \   /\
  2 4   6
         \
          7
    Est-il un moyen de savoir où mettre le 7? Parce que ne pourrait-elle pas également à aller vers la droite de la 4 ou 2?
    7 est plus grand que 3, donc il va sur le droit de 3. Il est plus grand que 5, donc, il va à la droite de 5, etc.
    Oh, je vois. Je vous remercie. J'avais mal compris la chose tout ce temps de réflexion, vous ne regarder l'immédiat les nœuds et non ceux qui sont venus avant.

    OriginalL'auteur Sjoerd

  2. 2

    Sans de plus amples informations sur les règles applicables à la façon dont l'arbre est équilibré, je suppose que c'est en se référant à un "naïf" déséquilibré arbre.

    Donc:

             3
  /-----/\-----\
 1               5
  \--\       /--/\--\
      2     4         6
                       \-\
                          7
    Merci de répondre

    OriginalL'auteur Oliver Charlesworth

  3. 1

    Oui, 3 est la racine, parce que, après la première insertion de l'ensemble de l'arbre a un seul élément. En gardant la même logique, si (nombre, à gauche, à droite) représente un nœud, vous bénéficiez de:

    1. (3,,)

    2. (3,,(5,,))

    3. (3,,(5,,(6,,)))

    4. (3,(1,,),(5,,(6,,)))

    5. (3,(1,,2),(5,,(6,,)))

    6. (3,(1,,2),(5,(4,,),(6,,)))

    7. (3,(1,,2),(5,(4,,),(6,,7)))

    Merci pour la réponse

    OriginalL'auteur Petar Ivanov