Construire un arbre binaire équilibré à partir d'une table en récursif

Construire un arbre binaire équilibré à partir d'une table en récursif - Algo - Programmation

Marsh Posté le 25-11-2009 à 17:26:47    

Bonjour,
Je suis à la recherche d'un algorithme de remplissage d'un arbre binaire équilibré à partir d'une table d'élément ordonnés.
 
C'est une procédure ou fonction récursive qui avec Ada s'écrit en partie, me semble t'il de mémoire :

Code :
  1. procedure Tree_Loader(Table : in out T_Table;
  2.                             B_Inf, B_Sup : in out Positive) is
  3.          midle : positive := (b_sup - b_inf) / 2;
  4.       begin
  5.          ---
  6.          ajout_dans_l_arbre();
  7.          ---
  8.          ajout_dans_l_arbre();
  9.       end Tree_Loader;


 
Il me semble que les deux appel à ajout sont dans un if et son else, mais pas certain.
 
Ca dit quelque chose à quelqu'un ?
Merci.

Reply

Marsh Posté le 25-11-2009 à 17:26:47   

Reply

Marsh Posté le 26-11-2009 à 01:21:24    

Yep!
 
Je cherche.... J'y suis presque....
Voilà çe à quoi ça ressemble... Mais ça n'a pas l'air d'être ça encore...
 

Code :
  1. procedure Tree_Loader(Table : in table_access;
  2.                             B_Inf, B_Sup : in out Natural) is
  3.  
  4.          Coded_Word : T_Coded_Word;
  5.          Midle : Natural := B_Inf + ((B_Sup - B_Inf)/ 2);
  6.          New_B_Inf : Natural;
  7.          New_B_Sup : Natural;
  8.  
  9.       begin
  10.          if Midle+1 < B_sup then
  11.             New_B_inf := Midle+1;
  12.             Tree_Loader(Table => Table,
  13.                         B_Inf => New_B_Inf,
  14.                         B_Sup => B_sup);
  15.          end if;
  16.          Coded_Word := Table(Midle);
  17.          Put_Line(To_String(Coded_Word.Word));
  18.          Code_To_Word.Add(Coded_Word, Univers(Number_Of_Dictionary).To_Word);
  19.          Word_To_Code.Add(Coded_Word, Univers(Number_Of_Dictionary).To_Code);
  20.          if B_inf < Midle-1 then
  21.             New_B_sup := Midle-1;
  22.             Tree_Loader(Table => Table,
  23.                         B_Inf => B_inf,
  24.                         B_Sup => New_B_sup);
  25.          end if;
  26.       end Tree_Loader;


J'ai deux Add, parce que je remplie deux arbre en fait.

Reply

Marsh Posté le 26-11-2009 à 01:59:09    

Ca, ça n'a pas l'air mal non plus... Peut-être que je le tiens.
 

Code :
  1. procedure Tree_Loader(Table : in table_access;
  2.                             B_Inf, B_Sup : in out Natural) is
  3.  
  4.          Coded_Word : T_Coded_Word;
  5.          Midle : Natural := B_Inf + ((B_Sup - B_Inf)/ 2);
  6.          New_B_Inf : Natural := b_inf+1;
  7.          New_B_Sup : Natural := b_sup-1;
  8.  
  9.       begin
  10.          
  11.          if Midle < new_B_sup then
  12.             
  13.             Tree_Loader(Table => Table,
  14.                         B_Inf => midle,
  15.                         B_Sup => new_B_sup);
  16.          end if;
  17.          
  18.          Coded_Word := Table(Midle);
  19.          Put_Line(To_String(Coded_Word.Word));
  20.          Code_To_Word.Add(Coded_Word, Univers(Number_Of_Dictionary).To_Word);
  21.          Word_To_Code.Add(Coded_Word, Univers(Number_Of_Dictionary).To_Code);
  22.          if new_B_inf < Midle then
  23.             
  24.             Tree_Loader(Table => Table,
  25.                         B_Inf => new_B_inf,
  26.                         B_Sup => midle);
  27.          end if;
  28.          
  29.       end Tree_Loader;

Reply

Marsh Posté le 26-11-2009 à 16:21:11    

Voila la soluce que je cherchais...
 

Code :
  1. procedure Tree_Loader(Table : in table_access;
  2.                             B_Inf, B_Sup : in Natural) is
  3.          Coded_Word : T_Coded_Word;
  4.          Middle : Natural := b_inf + (b_sup-b_inf) / 2;
  5.          New_B_Inf : Natural;
  6.          New_B_Sup : Natural;
  7.       begin
  8.          Coded_Word := Table(Middle);
  9.          Code_To_Word.Add(Coded_Word, Univers(Number_Of_Dictionary).To_Word);
  10.          Word_To_Code.Add(Coded_Word, Univers(Number_Of_Dictionary).To_Code);
  11.          if Middle-1 >= B_Inf then
  12.             new_b_sup := middle-1;
  13.             Tree_Loader(Table => Table,
  14.                         B_Inf => b_inf,
  15.                         B_Sup => new_b_sup);
  16.          end if;
  17.          if  middle+1 <= B_sup then
  18.             new_b_inf := middle+1;
  19.             Tree_Loader(Table => Table,
  20.                         B_Inf => new_b_inf,
  21.                         B_Sup => b_sup);
  22.          end if;      
  23.       
  24.       end Tree_Loader;


 
Merci bien

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed