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