Discussion :

[kromartien]

Bonjour.

Je voudrai une technique (un algorithme) pour lire l'ensemble des feuilles d'un arbre binaire, et placer ses feuilles dans un tableau, associé à la suite de bits correspondant à chaque feuille. Pouvez vous m'aider s'il vous plaît ?

Merci beaucoup.

Kromartien.

[SpiceGuid]

1. le type 'a tree est un type arbre binaire avec des données aux noeuds et aux feuilles
2. le type fold est le type des fonctions qui parcourrent les cellules d'un 'a tree
3. la fonction leaves est une fonction de type fold qui ne parcourre que les feuilles (dans l'ordre infixe)

Code Caml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
type 'a tree = 
  | Nil
  | Leaf of 'a 
  | Node of 'a tree * 'a * 'a tree

type ('a,'b) fold = ('a -> 'b -> 'b) -> 'b -> 'a tree -> 'b

let leaves : ('a,'b) fold = fun f init t ->
  let rec loop acc = function
  | Nil -> acc
  | Leaf a -> f a acc
  | Node (l,a,r) -> loop (f a (loop acc l)) r
  in loop init t

[kromartien]

ok , merci beaucoup... Finalement j'avais trouvé un truc qui m'allait bien, donc je peux dire que c'est résolu.

Ton code est du Ocaml, si je ne m'abuse. Bon, je fais quelque chose en C, donc ce n'est pas forcément ce qu'il y a de plus proche.

Merci beaucoup néanmoins.

Au revoir.