Est-il possible de décider de l'équivalence structurelle de deux arbres de recherche binaires juste avec les résultats des traversées, pre order, in order et post order. Supposons que je n'ai que les tableaux de résultats de toutes les traversées. Je sais que la traversée en ordre seule ne peut pas aider. Mais, je ne pouvais pas visualiser les résultats des autres traversées. Je comprends que BFS aide. Je veux savoir ce qu'il en est pour les traversées pré et post ordonnées. Et si possible, veuillez poster des liens sur ce sujet.
Réponses
Trop de publicités?
La réponse est : on peut récupérer un arbre de recherche binaire à partir de sa traversée pré-ordonnée .
Je ne suis pas sûr de votre formation mathématique, alors n'hésitez pas à demander plus d'explications si vous en avez besoin.
Pour simplifier, je suppose que les nœuds sont étiquetés par l'entier 1,2... n où n est le nombre de nœuds. Alors la traversée en pré-ordre de l'arbre t donne une permutation de [n] = {1,2,...,n} qui ont une propriété particulière : chaque fois que vous avez une lettre b dans votre permutation, vous ne pouvez pas trouver deux lettres consécutives ca après le b dans la permutation telle que a<b<c . On dit d'une telle permutation qu'elle éviter le motif b-ac (les - représentent un nombre arbitraire de lettres).
Par exemple, 4 2 1 3 évite b-ac alors que 3 1 4 2 ne le fait pas car 3 - 4 2.
Il s'agit en fait d'une équivalence : Une permutation est la lecture pré-ordonnée d'un arbre s'il est évité b-ac.
On sait qu'il existe autant d'arbres de taille n que de permutations évitant b-ac ; il s'agit donc d'une bijection. Leur nombre est connu sous le nom de nombre catalan. Vous pouvez probablement trouver cela comme exercice dans le livre de Stanley "enumerative combinatorics".
Voici une explication plus algorithmique :
RecTree: Recovering a tree from is Pre-order traversal:
input: list l
output: tree t
b <- l[0]
find an index i such that
- for 1<=j<=i then l[j] < b and
- for i<j<=n then l[j] > b
if there isn't exists such an index return Failure
else return Node(key=b, RecTree(l[1..i]), RecTree(l[i+1..n]))En conséquence
Deux arbres de recherche binaires sont égaux si et seulement s'ils ont la même traversée préordonnée.
Est-ce que cela a un sens pour vous ?
Quelques références supplémentaires
jgroenen
Points
954
