Trier lettres de l'alphabet en utilisant un arbre binaire

Question

je suis tombé sur une question d'entrevue qui stipule: Comment vous représenter les lettres A, B, C, D, E, F et G dans un ordre de tri en utilisant une représentation arborescente binaire?

Je suis vraiment perplexe. Si nous prenons G pour être la racine de l'arbre, alors l'enfant de gauche aurait E et l'enfant de droite serait F de sorte que le sous-arbre de droite soit "plus grand que" le sous-arbre de gauche. Ensuite, pour le noeud E, son enfant à gauche serait A et l'enfant à droite B et l'enfant à gauche de F serait C et son enfant à droite serait D.

Est-ce correct ou quelqu'un d'autre a-t-il une réponse différente?

Answer 1

L'arborescence binaire que vous avez décrite est Binary heap, généralement utilisée pour implémenter la file d'attente de priorité.

Utilisez à la place Binary search tree, qui conserve les clés dans un ordre trié.

Answer 2

Si vous utilisez les lettres de A à G comme ensemble complet, l'arbre binaire trié ressemblerait à ceci:

 D 
    B  F 
A C E G