programme TD6; /* Un petit programme qui teste les fonctions de codage et décodage d'arbres binaire (de taille connue) */ type arbreptr: ^arbre; type arbre: enreg gauche: arbreptr; droite: arbreptr finenreg; type tab: tableau 0..20 de entier; fonction taille(ref racine:arbreptr): entier; debut si racine=nul alors retourne 0 finsi retourne 1+taille(racine^.gauche)+taille(racine^.droite) finfonction; var T:tab; procedure Calculprealable(ref T:tab) debut T[0]=1; pour i de 1 a 20 faire T[i]:=0; pour g de 0 a i-1 faire T[i]:=T[i]+T[g]*T[i-1-g] finprocedure fonction code (ref racine: arbreptr): entier; var i, taillegauche, tailledroite, tailletotale:entier; var somme:entier; debut /* code parmi ceux de la meme taille*/ si racine = nul alors retourne 0 finsi; taillegauche:=taille(racine^.gauche); tailledroite:=taille(racine^.droite); tailletotale:=1+taillegauche+tailledroite; /* compter ceux de la meme taille mais avec un sous-arbre gauche plus petit*/ somme:=0; pour i allant de 0 a taillegauche-1 par pas de 1 faire somme := somme+T[i]*T[tailletotale-1-i] finpour; /*et enfin ceux avec les memes tailles des deux sous-arbres mais qui preceden t * "racine" dans l'ordre*/ somme := somme+code(racine^.gauche)*T[tailledroite]; retourne somme+code(racine^.droite) fin finfonction; fonction decode(val n,c: entier): arbreptr; /* n la taille, c le code*/ var racine: arbreptr; var i: entier; debut i:=-1; si n=0 alors retourne nul finsi; allouer(racine); tantque c>=0 faire i:=i+1;c:=c-T[i]*T[n-1-i] fin tantque; c:=c+T[i]*T[n-1-i]; /*i est la taille du sous-arbre gauche*/ racine^.gauche:=decode(i,c/T[n-1-i]); racine^.droite=decode(n-1-i,c mod T[n-1-i]); retourne racine fin finfonction; var ARB: arbreptr; debut Calculprealable(T) pour i de 0 a 1000 faire ARB:=decode(15,i); printf("i et code sont %i et %i\n",i,code(ARB)) fin. \end{verbatim}