Questions / réponses

Parcours infixe d'un ABR

Parcours infixe d'un ABR

Napisane przez: Zahra Carn ( )
Liczba odpowiedzi: 2

Bonjour,

Pour la fonction list_from_bst j'ai 4 fois le même erreur qui apparait et je n'arrive pas à voir d'où il provient. 

Ma fonction est de type: val list_from_bst : 'a tree -> 'a list = <fun>

L'erreur que j'ai dit que c'est sur le cas d'avoir fait l'insertion selon la liste [0;1].

Or list_from_bst (Bin((0,1),Empty,Bin((1,1),Empty,Empty)));;
Et list_from_bst (bst_from_list [0;1]);
Donnent tous les deux # - : int list = [0; 1]

Merci pour votre aide.

W odpowiedzi na Zahra Carn

Re: Parcours infixe d'un ABR

Napisane przez: Marc Zeitoun ( )

Je viens de tester plusieurs fois le code (actuel) et deux erreurs sont reportées par Moodle :

Échec sur les ABR construits par insertion à partir des listes suivantes :
[1; 0]
Échec sur les ABR construits par insertion à partir des listes suivantes :
[0; -1]
Effectivement, l'évaluation de  

let _ = list_from_bst (Bin((1,1),
                           Bin((0,1),Empty,Empty),
                           Empty))
donne 
- : int list = [1; 0]
alors que la liste renvoyée devrait être triée selon l'ordre croissant, donc [0; 1].

Dans le code actuel, la valeur de la racine est mémorisée dans un accumulateur avant les valeurs se trouvant dans les fils gauche et droit. Lorsqu'on renvoie l'accumulateur renversé, la clé de la racine apparaît donc en premier, ce qui n'est pas le cas dans un parcours infixe.