Utilisez une traversée dans l'arborescence pour déterminer si une BST ou un tas

Question

Compte tenu de ces listes de traversée dans l'ordre:

1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19
2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17

Je dois déterminer si chacune de ces listes représente un tas de BST / min ou maximum valide, ou aucun.
J'essayais de comprendre comment aborder cela, mais en plus de brute-forcer chaque option possible, je ne pouvais pas comprendre un moyen "intelligent" de résoudre ce problème.

Quels indicateurs puis-je utiliser, s'il y en a ou la manière de résoudre ce problème serait littéralement brute de forcer chaque option?

Answer 1

Aucun d'entre eux ne peut être une BST.Une traversée dans l'ordre d'une BST visit les sommets dans l'ordre non diminuant de leurs clés (il est facile de prouver par induction).

Pour déterminer s'ils sont des tas, remarquez que par le nombre d'éléments de la liste que vous connaissez déjà la topologie de l'arborescence (les tas sont complètement des arbres binaires jusqu'au niveau unique et toutes les feuilles de laLe dernier niveau est emballé sur le côté gauche).Ensuite, l'exercice se résume à écrire les clés données dans le même ordre de traversée et de vérification si la propriété du tas contient.

Dans l'exemple spécifique, la première séquence ne peut pas être une traversée en ordre d'un tas puisque l'arbre résultant aurait un chemin avec des touches 23 $, 1, 53 $ (dans l'ordre croissant de profondeur). Le même argument s'applique à la deuxième séquence pour un chemin avec des touches 71 $, 32, 49 $ .