Démontrer ou réfuter: Si vous avez obtenu une traversée de pré-commande d'un arbre de recherche binaire, vous pouvez uniquement déterminer cet arbre de recherche binaire

Question

Ceci est une tâche que j'ai trouvée depuis un ancien examen et je l'essaie parce qu'elle peut poser une question similaire le vendredi.

Pour la solution j'ai la solution bon marché mais je pense que tout question de définition d'arbre de recherche binaire.

-je faire d'abord l'arbre:

1 
\ 
    1 
    \ 
    1 

et voici la deuxième arbre

1 
/
    1 
/
1 

Lorsque vous faites pré commande traversal vous avez même sortie pour les deux arbres .. parce que même élément, et les deux ont arbre dégénéré. Mais tu n'as pas le même arbre! Donc, la déclaration est fausse.

Seul problème est mon arbre de recherche binaire arbre ... Je pense que oui parce que l'arbre de recherche binaire l'élément peut avoir un élément supérieur/inférieur? S'il vous plaît halp quand j'ai demandé à notre professeur, il dit que je peux lui demander quand les vacances sont terminées, mais quand les vacances sont finis mon examen est terminé .... Pas de bonne chose pour moi.

Answer 1

Votre réponse est parfaitement satisfaisante compte tenu de la définition standard des BST. Par la définition standard, les BST peuvent avoir des éléments répétés et des éléments identiques peuvent aller dans les deux sous-arbres.

Si la question vise le cas où il n'y a pas de doublons, ou si les doublons doivent exister uniquement dans le sous-arbre gauche (ou seulement le sous-arbre droit), une traversée de précommande est suffisante pour reconstruire l'arbre. Si les doublons ne sont pas autorisés, construisez l'arborescence récursivement comme suit: faites de la racine le premier nœud, puis faites récursivement les sous-arborescences gauche et droite en utilisant comme traverses d'entrée les portions de la traversée originale avec des nœuds inférieurs à (pour gauche sous-arbre) et supérieur à (pour le sous-arbre droit) le noeud racine. Si les doublons sont autorisés mais sont contraints à la sous-arborescence gauche ou droite, alors utilisez la même procédure mais en ajoutant "ou égal" au plus petit ou au plus grand, mais pas aux deux.