je cherche un algo recursif permettant de transformer un arbre N-aire en arbre binaire.
 
Merci
 

 
contexte?

simple algo qui a partir d'un arbre n aire le transforme en binaire

ben ça se fait pas comme ça, t'as bien des règles de transformation nan ?

type 'a narytree =  
  | Nnode of 'a * 'a narytree list  
  | Nleaf;;
type 'a binarytree =  
  | Bnode of 'a * 'a binarytree * 'a binarytree  
  | Bleaf;;
 
let n2b n =  
  let rec n2b' = function  
    | Nleaf -> Bleaf
    | Nnode(e, l) ->  
      let rec listToB = function
        | [] -> Bleaf
        | Nleaf::xs -> listToB xs
        | Nnode(v, l)::xs -> Bnode( v, (listToB l), (listToB xs))
      in Bnode(e, Bleaf, (listToB l))
  in n2b' n;;
 
let v1 =  
Nnode(10, [
  Nnode(11, [
    Nnode(21, [Nleaf]);  
    Nnode(22, [Nleaf]);
    Nnode(23, [Nleaf])
  ]);  
  Nnode(12, [Nleaf]);
  Nnode(13, [
    Nnode(31, [Nleaf]);  
    Nnode(32, [Nleaf]);
    Nnode(33, [Nleaf])
  ])
]);;
 
tiens,en O'caml style curryfié, j'ai choisi mes règles vu que tu te décides pas

Tu dois bien avoir une propriété à conserver dans la transformation, non ? Sinon ta question n'a aucun sens : tu prends tes éléments n'importe comments, et tu créé ton arbre binaire n'importe comment.
 
Bref, explique ce que tu veux.

surtout que ça dépend de l'usage, en faisant le truc, je me suis dit que j'allais conserver la transitivité mais en réfléchissant, sur un arbre binaire, on a :
filgauche < noeudcourant < filsdroit
Mais sur un arbre Naire, à part:
premierfils < deuxièmefils < troisièmefils ...
je vois pas comment placer placer le noeud courant là-dedans.

Il y a bijection entre les arbres binaires et les arbres n-aires.
 
La relation de transformation est simple :

• le premier fils de l'arbre n-aire est le fils gauche de l'arbre binaire,
• le second fils de l'arbre n-aire est le fils droit de l'arbre binaire,
• le troisième fils de l'arbre n-aire est le fils droit du fils droit de l'arbre binaire,
• le quatrième fils de l'arbre n-aire est le fils droit du fils droit du fils droit de l'arbre binaire,
• etc., en ajoutant des fils droits.