Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
(* 1.4 Lecture et parcours d'arbres ********************************) (* Arbres binaires *) type ('a,'b) bintree = Node of 'a * ('a,'b) bintree * ('a,'b) bintree | Leaf of 'b;; let rec printBin = function Leaf n -> print_int n | Node(x,t1,t2) -> print_char '('; printBin t1; print_char x; printBin t2; print_char ')';; let arbre = Node('+', Leaf 1, Node('*', Leaf 0, Leaf 3));; printBin arbre;; (*renvoie le nombre de caractères de l'entier *) let rec litEntier n s = match s.[n] with '0'..'9' -> 1 + litEntier (n+1) s | _ -> 0;; (* Lecture d'arbre parenthésé sans blanc *) let rec litArbreRec n s = match s.[n] with '(' -> let (t1, n1) = litArbreRec (n+1) s in let (t2, n2) = litArbreRec (n1+1) s in assert (s.[n2] = ')'); Node(s.[n1], t1, t2), n2+1 | '0'..'9' -> let l = litEntier n s in Leaf (int_of_string(String.sub s n l)), n+l | _ -> failwith "Ce n'est pas un arbre bien parenthésé";; let litArbreBin s = fst (litArbreRec 0 s);; printBin (litArbreBin "(1+(0*3))");; (* Parcours d'arbres *) type 'a tree = Tree of 'a * ('a tree) list;; let leaf_a = Tree ('a',[]);; let a = Tree('f', [Tree('g', [leaf_a]); Tree('f', [leaf_a; leaf_a])]);; let rec print = function Tree(f,[]) -> print_char f | Tree(f,l) -> print_char f; print_char '('; List.iter print l; print_char ')';; print a;; let rec litArbreRec n s = if n>=String.length s || s.[n]=')' then [], n+1 else let child, nc = if(n+1 a | _ -> failwith "Arbre préfixe mal formé";; print (litArbre "f(g(a)f(aa))");; let rec parcoursProf (Tree(c,l)) = List.iter parcoursProf l; print_char c;; parcoursProf a;; (* On suppose un seul chiffre par nombre *) let rec litArbreBinPostfixeRec l n s = if n litArbreBinPostfixeRec ((Leaf(int_of_char s.[n] - int_of_char '0'))::l) (n+1) s | _ -> (match l with t2::t1::l' -> litArbreBinPostfixeRec ((Node(s.[n], t1, t2))::l') (n+1) s | _ -> failwith "Pas assez d'arguments dans l'écriture postfixe" ) else l;; let litArbreBinPostfixe s = match litArbreBinPostfixeRec [] 0 s with [a] -> a | _ -> failwith "Trop d'arguments dans l'écriture postfixe";; printBin (litArbreBinPostfixe "103*+");; let rec nrevRec n l1 l2 = match (n,l2) with 0,_ -> (l1,l2) | _,a::l2' -> nrevRec (n-1) (a::l1) l2' | _ -> failwith "nrev: liste trop courte";; let nrev n l = nrevRec n [] l;; let rec litArbrePostfixeRec arite l n s = if n a | _ -> failwith "Trop d'arguments dans l'écriture postfixe";; print (litArbrePostfixe ['a',0;'g',1;'f',2] "agaaff");; let rec parcoursLargeurRec = function [] -> () | (Tree(c,cl))::l -> print_char c; parcoursLargeurRec (l@cl);; let parcoursLargeur a = parcoursLargeurRec [a];; parcoursLargeur a;;