Bonjour, serait-il possible d'avoir quelques astuces pour résoudre la question 2 de cette exercice ? J'ai du mal à appréhender le problème avec les éléments donné dans la consigne: comment retourner un arbre codé avec le début de la liste binaire et renvoyer en tuple composé d'un arbre de type stree (vraisemblablement incomplet) et de la fin de notre liste ?
Cordialemment Hugo Lecomte
L'exercice a été fait deux fois dans le semestre : une fois tel quel, une autre fois pour écrire la bijection entre mots de Dyck et arbres binaires.
Je poste donc une correction, exceptionnellement sans commentaire (puisque l'exercice a été abordé et travaillé pendant le semestre). Avec la proposition de l'énoncé, on peut obtenir une fonction comme :
let rec encode t = match t with
Leaf -> [1]
| Bin (l, r) -> 0 :: (encode l) @ (encode r)
let decode l =
let rec aux l =
match l with
| 1::tail -> Leaf,tail
| 0::tail ->
let (t1, tail1) = aux tail in
let (t2, tail2) = aux tail1 in
Bin(t1,t2), tail2
| _ -> failwith "Only binary strings are allowed"
in let t,tail = (aux l) in
if tail = []
then t
else failwith "Ill-formed binary string"
Merci beaucoup !
let bfs t =
Une simulation du parcourt en largeur avec l'utilisation de deux piles
let rec dyck_to_planar l =
let rec aux l acc = match l,acc with
|[],_-> acc
|Down::tail,_->aux tail (Node(0,[])::acc)
|Up::tail,x::acctail-> aux tail (Node(0, [x])::acctail)
|_-> failwith "pas un mot de dyck"
in aux (List.rev l) [];;
Et je ne parviens pas non plus à faire fonctionner dyck_to_planar
Cordialement