td-arbre.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[10]\", line 227, characters 0-0:\nError: Syntax error\n"
     ]
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type ('a, 'b) arbre =\n",
       "    Interne of 'a * ('a, 'b) arbre * ('a, 'b) arbre\n",
       "  | Feuille of 'b\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val hauteur : ('a, 'b) arbre -> int = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val taille : ('a, 'b) arbre -> int = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val dernier : ('a, 'b) arbre -> 'b = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val affiche_prefixe : (int, int) arbre -> unit = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val affiche_infixe : (int, int) arbre -> unit = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val affiche_postfixe : (int, int) arbre -> unit = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type ('a, 'b) token = N of 'a | F of 'b\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val postfixe_naif : ('a, 'a) arbre -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val post_fixe : ('a, 'b) arbre -> ('a, 'b) token list = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val prefixe : ('a, 'b) arbre -> ('a, 'b) token list = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val infixe : ('a, 'b) arbre -> ('a, 'b) token list = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val post_fixe_term : ('a, 'b) arbre -> ('a, 'b) token list = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val etiquettes_largeur : ('a, 'b) arbre -> ('a, 'b) token list = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val lire_etiquette : bool list -> ('a, 'a) arbre -> 'a = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val incremente : (int, int) arbre -> bool list -> (int, int) arbre = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val affiche_avec_adresse : int -> bool list -> unit = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tableau_adresses : (int, int) arbre -> unit = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type 'a pile = 'a list ref\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val pile_vide : '_weak12 list ref = {contents = []}\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val pop : 'a list ref -> 'a = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val push : 'a -> 'a list ref -> unit = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type cote = G | D\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type arbre = Feuille | Noeud of arbre * arbre\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type arbre_annote = N of int * arbre_annote * arbre_annote | F\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val card : arbre_annote -> int = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val annote : arbre -> arbre_annote = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type ('a, 'b) arbre =\n",
    "  | Interne of 'a * ('a, 'b) arbre * ('a, 'b) arbre\n",
    "  | Feuille of 'b ;;\n",
    "\n",
    "\n",
    "\n",
    "(* faire des terminalisations aussi*)\n",
    "\n",
    "\n",
    "let rec hauteur a = match a with\n",
    "  |Feuille f -> 0\n",
    "  |Interne (_,g,d) -> 1+max (hauteur g) (hauteur d) ;;\n",
    "\n",
    "\n",
    "let rec taille a = match a with\n",
    "  |Feuille  f -> 1\n",
    "  |Interne (_,g,d) -> 1+ taille g + taille d ;;\n",
    "\n",
    "\n",
    "let rec dernier a = match a with\n",
    "  | Feuille f -> f\n",
    "  |Interne (_,g,d) -> dernier d ;;\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "let rec affiche_prefixe a = match a with\n",
    "  |Feuille f -> print_newline (print_int f)\n",
    "  |Interne (x,g,d) -> print_newline (print_int x) ; affiche_prefixe g ; affiche_prefixe d ;;\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "let rec affiche_infixe a = match a with\n",
    "  |Feuille f -> print_newline (print_int f)\n",
    "  |Interne (x,g,d) -> affiche_infixe g ; print_newline (print_int x) ;  affiche_infixe d ;;\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "let rec affiche_postfixe a = match a with\n",
    "  |Feuille f -> print_newline (print_int f)\n",
    "  |Interne (x,g,d) ->  affiche_postfixe g ; affiche_postfixe d ; print_newline (print_int x) ;;\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "type ('a, 'b) token = N of 'a | F of 'b ;;\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "let rec postfixe_naif a = match a with\n",
    "  |Feuille f -> [f]\n",
    "  |Interne (x,g,d) -> postfixe_naif g @ postfixe_naif d @ [x] ;;\n",
    "\n",
    "\n",
    "\n",
    "let rec post_fixe a =\n",
    "  let rec aux a l = match a with\n",
    "  | Feuille f -> (F f )::l\n",
    "  |Interne (x,g,d) -> (N x)::(aux d (aux g l))\n",
    "  in List.rev_append (aux a []) [] ;;\n",
    "\n",
    "\n",
    "let rec prefixe a =\n",
    "  let rec aux a l = match a with\n",
    "  |Feuille f -> (F f )::l\n",
    "  |Interne (x,g,d) -> aux d (aux g ((N x)::l))\n",
    "  in List.rev_append (aux a []) [] ;;\n",
    "\n",
    "\n",
    "let rec infixe a =\n",
    "  let rec aux a l = match a with\n",
    "  |Feuille f -> (F f)::l\n",
    "  |Interne (x,g,d) -> aux d (( N x)::(aux g l))\n",
    "  in List.rev_append (aux a []) [] ;;\n",
    "\n",
    "\n",
    "let rec post_fixe_term a = \n",
    "  let rec aux f e = match f with\n",
    "  |[]->e\n",
    "  |a::r -> match a with\n",
    "  |Feuille m -> aux r (F m::e)\n",
    "  |Interne (x,g,d) -> aux (d::g::r) (( N x)::e) (* l'ordre est choisi pour respecter l'ordre postfixe inverse*)\n",
    "  in List.rev_append (aux [a] []) [] ;;\n",
    "\n",
    "(* utiliser une file*)\n",
    "\n",
    "let rec etiquettes_largeur a =\n",
    "  let rec aux file u =\n",
    "    match Queue.pop file with\n",
    "    |Feuille f when Queue.is_empty file -> (F f)::u\n",
    "    |Feuille f -> aux file ((F f)::u)\n",
    "    |Interne (x,g,d) -> Queue.push g file ; Queue.push d file ; aux file ((N x)::u)\n",
    "  in let m = Queue.create () in Queue.push a m ; List.rev_append (aux m []) [] ;;\n",
    "\n",
    "\n",
    "\n",
    "let rec lire_etiquette u a =\n",
    "  match u,a with\n",
    "  |[],Feuille f -> f\n",
    "  |[],Interne (x,_,_) -> x\n",
    "  |x::r,Interne (_,g,d) when x -> lire_etiquette r d\n",
    "  |x::r,Interne (_,g,d) -> lire_etiquette r g\n",
    "  |_,Feuille f -> failwith \"error\" ;;\n",
    "\n",
    "\n",
    "let rec incremente a u =\n",
    "  match a,u with\n",
    "  |Feuille f,[] -> Feuille (f+1)\n",
    "  |Interne (x,g,d),[]-> Interne (x+1,g,d)\n",
    "  |Interne (m,g,d),x::r when x -> Interne (m,g, incremente d r)\n",
    "  |Interne (m,g,d),x::r -> Interne (m,incremente g r,d)\n",
    "  |Feuille f,_ -> failwith \"error\" ;;\n",
    "\n",
    "\n",
    "let affiche_avec_adresse x adresse =\n",
    "    List.iter (fun b -> print_int (if b then 1 else 0)) adresse;\n",
    "    Printf.printf \" : %i\\n\" x ;;\n",
    "\n",
    "\n",
    "let tableau_adresses a =\n",
    "  let rec aux a cour = match a with\n",
    "    |Feuille f -> affiche_avec_adresse f cour\n",
    "    |Interne (x,g,d) ->  affiche_avec_adresse x cour  ; aux g (false::cour) ; aux d (true::cour)\n",
    "  in aux a [];;\n",
    "\n",
    "\n",
    "\n",
    "(* refaire le type pile *)\n",
    "\n",
    "type 'a pile = 'a list ref ;;\n",
    "\n",
    "let pile_vide = ref [] ;;\n",
    "\n",
    "let pop pile = match !pile with\n",
    "  |[] -> failwith \"impossible\"\n",
    "  |x::r -> x ;;\n",
    "\n",
    "let push x pile = pile := (x::(!pile)) ;;\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "(*\n",
    "let lire_largeur u = (* mettre sous le module Queue*)\n",
    "  let rec aux file u = match u with\n",
    "  |[] -> pop file\n",
    "  |x::r -> match x with\n",
    "    |F f -> push (Feuille f ) file ; aux file r\n",
    "    |N x -> let a = pop file in let b = pop file in push  (Interne (x,b,a))file ; aux file r\n",
    "  in let m = file_vide in aux m u ;;*)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "type cote = G | D ;;\n",
    "  (* arbre binaire entier non étiqueté *)\n",
    "type arbre = Feuille | Noeud of arbre * arbre ;;\n",
    "  (* on annote chaque noeud interne avec le cardinal du sous-arbre\n",
    "  correspondant *)\n",
    "type arbre_annote =\n",
    "  | N of int * arbre_annote * arbre_annote\n",
    "  | F;;\n",
    "\n",
    "let card = function\n",
    "  | F -> 1\n",
    "  | N(taille, _, _) -> taille ;;\n",
    "\n",
    "let rec annote a = match a with\n",
    "  |Feuille  -> F\n",
    "  |Noeud (g,d) -> let a,b = annote g,annote d in match a,b with\n",
    "    |F,F -> N (2,a,b)\n",
    "    |F,N (x,_,_) |N (x,_,_),F -> N (x+1,a,b)\n",
    "    |N (x,_,_),N (y,_,_) -> N (x+y+1,a,b) ;;\n",
    "\n",
    "\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[27]\", line 11, characters 0-0:\nError: Syntax error\n"
     ]
    }
   ],
   "source": [
    "\n",
    "\n",
    "let insere b x t = (* faire un parcours préfixe après*) (*ne pas oublier d'augmenter le cardinal de chaque père après *)(* x est le noeud à avoir dans l'ordre préfixe*)\n",
    "  let rec aux b x t =  match b,t with\n",
    "  |F,D when x=1 -> (N (3,F,F),2)\n",
    "  |F,G when x=1 -> (N(3,F,F) , 1)\n",
    "  |N (taille,g,d),G when x=1 -> (N (taille+1,F,b),1) (* A FINIR *)\n",
    "  |N (taille,g,d),D when x=1 -> (N  (taille+1,b,F),taille +1)\n",
    "  |N (taille,g,d),_ ->let t1 = card g in if t1<x then aux d (x-t1) t else aux g (t1-1) t\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[30]\", line 6, characters 5-8:\n6 |     |F f -> push (Feuille f) pile ; aux pile r\n         ^^^\nError: The constructor F expects 0 argument(s),\n       but is applied here to 1 argument(s)\n"
     ]
    }
   ],
   "source": [
    "\n",
    "let lire_postfixe u  = \n",
    "  let rec aux pile u = match u with\n",
    "  |[] -> pop pile \n",
    "  |x::r -> match x with\n",
    "    |F f -> push (Feuille f) pile ; aux pile r\n",
    "    |N m -> let a = pop pile in let b = pop pile in push (Interne (m,b,a)) pile ; aux pile r\n",
    "  in aux pile_vide u ;;\n",
    "\n",
    "\n",
    "(* séparer les parties par type car conflit *)\n",
    "(* utiliser une pile comme liste *)\n",
    "\n",
    "let lire_prefixe_izi u =\n",
    "  let rec reverse a = match a with\n",
    "    | Feuille f -> Feuille f\n",
    "    |Interne (x,g,d) -> Interne (x, reverse d, reverse g)\n",
    "    in reverse (lire_postfixe u) ;;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[25]\", line 1, characters 9-14:\n1 | prefixe (Noeud (1,Noeud (2,Feuille 3 ,Feuille 4),Noeud (5,Feuille 6,Feuille 7)) )\n             ^^^^^\nError: This variant expression is expected to have type ('a, 'b) arbre\n       The constructor Noeud does not belong to type arbre\n"
     ]
    }
   ],
   "source": [
    "prefixe (Noeud (1,Noeud (2,Feuille 3 ,Feuille 4),Noeud (5,Feuille 6,Feuille 7)) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.08.1+flambda",
   "language": "OCaml",
   "name": "ocaml-jupyter"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "OCaml",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "4.08.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}