Dictionnaires

type dico=structure
            a:^sommet; /* l'arbre*/
            p:^sommet; :* le curseur */
          finstructure


fonction chercher_branche_droite(ref d : dico; ref c:car): booleen;
var v: car;
debut
  v=valeur(d.p)
  tant que filsDroit(d.p)<>NIL et v<c faire
    d.p=filsDroit(d.p)
    v= valeur(d.p)
  fin tant que
  si v==c alors /*d.p est positionné sur la lettre c*/
    retourner VRAI
  sinon
    si filsGauche(pere(d.p))!=d.p et filsDroit(d.p)<>NIL alors 
      d.p=pere(d.p)
    finsi
    /* dans le cas ou d.p est le premier de la branche droite le
       sommet contient une valeur >C */
    /* sinon d.p est surl'elt précédant la place possible pour un
       ajout à droite */ 
    retourner FAUX  
  finsi
fin

fonction prefixe(ref d: dico; ref M:Mot;ref i:entier) :booleen;
/*->VRAI M est dans le dico*/
/*->FAUX M[i] est la dernière lettre du prefixe dans le dico
debut
  cas où
    cas  M[i]=="\0" et valeur(d.p)=="\0" :
      /*le mot existe dans le dico*/
      retourner VRAI
    cas M[i]==valeur(d.p) 
      /* filsGauche(d.p)!=NIL nécéssairement*/
      d.p=filsGauche(d.p)
      i=i+1
      /* On continue à chercher le péréfixe /*
      retourner(prefixe(d,M,i))
    cas chercher_branche_droite(d,M[i]) alors
      /*d.p est sur le caractère correspondant à M[i] dans dico on repart de là*/
      /*prefixe se charge de descendre à gauche*/
     retourner(prefixe(d,M,i))
    autre cas :
      /*  on a le prefixe max au i-1eme caractère. d.p est sur l'elt précédant la place possible*/
      i=i-1
      retourner FAUX
  fincasou
fin

fonction supprimer(ref d : dico; ref M:mot) :vide
var tmp,pereTmp:sommet;
var i : entier;
debut
  i=1
  si prefixe(d,M,i) alors
    /*le mot est dans le dico d.p est sur \0 */
    /* on supprime le mot baguette */
    tant que  filsDroit(d.p)!=NIL et pere(d.p)!=NIL et filsGauche(pere(d.p))==d.p faire
      /*d.p n'a pas de fils droit et est le fils gauche de son père */    
      /*donc d.p fait partie de l'arbre baguette*/		   
      d.p=pere(d.p)					   	
      delete(filsGauche(d.p))					  		 
    fin tant que
    si d.p == d.a alors
      /* la première lettre est à la racine
       d.a=filsDroit(d.p)
      delete(d.p)
      d.p=d.a
    sinon
      /* soit d.p est un Fils gauche  soit c'est un fils droit du père */
      pereTmp=pere(d.p);
      tmp=d.p
      si filsDroit(pereTmp)==d.p alors
        pereTmp^.droit=d.p^.droit
        si filsDroit(d.p)!=NIL alors
          d.p^.droit^.pere=pereTmp
        finsi
      sinon 			
        pereTmp^.gauche=d.p^.droit			     
        /* d.p a toujours un fils droit */
        d.p^.droit^.pere=d.p^.pere		     
      finsi
    /* on deplace le curseur pour qu'il pointe sur une cellule active */
    d.p=pereTmp
    delete(tmp)
  finsi
fin

fonction creer_arbre_baguette(ref M:mot;val i:entier):sommet;
  var s,tmp,c:sommet
  var j:entier;
  debut
    s=creerArbreBinaire(M[i]);
    tmp=s;
    pour j=i+1 a longuer(M) faire
      ajouterFilsDroit(tmp,M[j]);
      tmp=filsDroit(tmp)
    finpour
    retourner(s)
  fin
    

fonction ajouter(ref d:dico,ref M:mot):vide
debut
  d.p=d.a
  i=1
  si !prefixe(d,m,i) alors
    s=creer_arbre_baguette(M, i+1)
    cas où :
     cas i=0 et pere(d.p)==NIL :
       /* cas de la racine*/
       s^.droit=d.a
       s^.pere=nil
       d.a^.pere=s
       d.a=s
    cas  M[i]>valeur(d.p) :
       /* insertion en milieu de branche droite */
       s^.droit=d.p^.droit
       s^.pere=d.p
       si filsDroit(d.p)!=NIL alors
         /* fin de branche droite */
         s^.droit^.pere=s
       finsi
       d.p^.droit=s
    autre cas
       s^.droit=d.p;
       s^.pere=d.p^.pere;
       d.p^.pere=s;
       s^.pere^.gauche==s
    fincasou
fin

fonction  nb_de_mots(ref d:dico):entier;
   retourner compterFeuille(d.a)


fonction compterFeuille(val s:sommet)
var g,d:entierdebut
debut
  si estFeuille(s) alors
    retourner 1
  sinon
    si filsGauche(s)!=NIL alors
      g= compterFeuille(filsGauche(s))
    finsi
    si filsDroit(s)!=NIL alors
      d= compterFeuille(filsDroit(s))
    finsi
    retourner(d+g)
  finsi
fin
    
fonction nb_mots_longueur_donnee(ref d:dico, val l:entier):entier;
var cpt:entier
debut
  cpt=0
  nb_mots_longueur_donnee_aux(d.a,l,cpt)
  retourner cpt
fin

fonction nb_mots_longueur_donnee_aux(ref s:sommet; val l: entier; ref cpt: entier):vide;
debut
  si estFeuille(s) et l==0 alors
    cpt=cpt+1
  sinon
var g,d:entierdebut
debut
  si estFeuille(s) alors
    retourner 1
  sinon
    si filsGauche(s)!=NIL alors
      g= nb_mots_longueur_donnee_aux(filsGauche(s),l-1,cpt)
    finsi
    si filsDroit(s)!=NIL alors
      d= nb_mots_longueur_donnee_aux(filsDroit(s),l-1,cpt)
    finsi
    retourner(d+g)
  finsi
fin