Trouver un arbre binaire donné uniquement traversée en ordre

Question

On me donne une traversée en ordre et j'ai besoin de trouver un arbre binaire. J'ai référé mes sites et la plupart d'entre eux ont dit que ce n'était pas possible. Cependant, je pense qu'un arbre binaire non-unique est possible. Puis-je trouver un arbre binaire en utilisant simplement une traversée donnée? Si non, puis-je trouver une traversée de pré-commande correspondante à partir de la traversée donnée?

J'ai essayé de convertir l'ordre en pré-commande en sélectionnant le noeud central de l'ordre en tant que racine mais je ne suis pas sûr si c'est correct. Guidez-moi s'il-vous-plaît.

Merci.

Answer 1

juste le traversal Étant donné dans l'ordre des nœuds, et pas plus d'informations sur la question, vous pouvez trouver un arbre binaire, mais comme vous l'avez dit, il n'y aura pas une solution unique (surtout si l'arbre ne doit pas être équilibré). Par conséquent, vous pouvez à nouveau trouver une traversée de précommande. Par exemple, si votre traversée d'ordre est [1,2,3,4,5,6,7,8], alors même si l'arbre est équilibré, il existe plusieurs possibilités pour le nœud racine (à savoir 4 ou 5). Si l'arbre n'est pas doit être équilibré, vous pouvez potentiellement choisir l'un de ceux-ci comme le nœud racine.

Voici un exemple d'un arbre non équilibré vous pourriez construire après avoir choisi arbitrairement 4 comme nœud racine:

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

traversal Pré-commande pour cet arbre rapporterait 4,3,2,1,6,5,7,8. Encore une fois, si les seules exigences sont que vous trouverez juste un arbre binaire, cela est tout aussi valable que la mise en 1 comme nœud racine et de faire tout le reste un nœud à droite:

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

Le traversal précommande cet arbre serait 1,2,3,4,5,6,7,8. Puisque ces arbres génèrent tous les deux la même traversée d'ordre, mais différents traversées de pré-commande, il n'est pas garanti qu'il s'agisse d'une seule arborescence unique ou même d'une unique traversée de pré-commande pour une traversée d'ordre donnée.

Answer 2

Pour plus d'un nœud, il n'existe pas d'arborescence de recherche binaire unique contenant la traversée inorder.

Mais si vous voulez un arbre, puis juste effectuer une lecture aléatoire aléatoire de séquence afinde puis insérez la séquence aléatoire résultant dans un arbre de recherche binaire