Création d'un arbre binaire

Un arbre binaire peut être créé en définissant un type correspondant à un n ud de l'arbre. Soit par exemple :

type arbre = ^noeud;
     noeud = record
                   valeur : integer;
                   gauche : arbre;
                   droit  : arbre;
             end;

Une telle structure peut être utilisée pour ordonner des éléments, en considérant que le sous-arbre gauche d'un n ud contient les éléments situés l'élément correspondant au n ud, tandis que le sous-arbre droit contient les éléments situés l'élément associé au n ud considéré (figure 6.7). Un exemple d'arbre binaire est donné par la figure 6.8

 
Figure:  

 
Figure 6.8:  Un exemple d'arbre binaire

Une telle structure est pratique pour effectuer des tris rapides. Le programme suivant permet de créer un arbre d'entiers, de le construire à partir d'une suite de nombres entrés par l'utilisateur, et ensuite de se servir de cet arbre pour afficher par ordre croissant les nombres entrés par l'utilisateur.

program arbresbinaires;

type 
    pointeur = ^noeud;
    noeud = record
               valeur : integer;
               gauche : pointeur;
               droit : pointeur;
            end;

var racine : pointeur;
    n : integer;

procedure construire(var arbre : pointeur; elt : integer);

   begin
      if (arbre=nil) then
         begin
            new(arbre);
            arbre^.valeur:=elt;
            arbre^.gauche:=nil;
            arbre^.droit:=nil;
         end
      else		    
           if elt<arbre^.valeur then
              construire(arbre^.gauche, elt)
           else if elt>arbre^.valeur then
              construire(arbre^.droit, elt);
end;

procedure afficher(arbre : pointeur);
   begin
     if not(arbre=nil) then
       begin
          afficher(arbre^.gauche);
          writeln(arbre^.valeur);
          afficher(arbre^.droit);
       end;
   end;    

begin     
      racine:=nil; (* Pascal n'initialise pas les pointeurs a nil *)
      write('entrez un nombre:');
      readln(n);
      while (n>=0) do
          begin
              construire(racine, n);
              write('entrez un nombre : '); 
              readln(n); 
          end;
      afficher(racine);
end.