Voici une implémentation en c++ de ce problème.
Pas compilable, c'est juste l'idée.
// un objet générique
class objet;
// une info est tout objet qui produit les méthodes donneVal et
// estVide plus les operateurs = < > <= >= ect...
typedef objet info;
// un tableau d'info commençant à l'indice 1
class Tableau;
// un abr
class Abr
{
info valeur;
Abr* fg;
Abr* fd;
public:
Abr() { fg = fd = 0; }
void ajout(const info&);
void explore(Tableau&, int&) const;
};
void Abr::ajout(const info& uneInfo)
{
if( valeur.estVide() )
{
valeur = info(uneInfo);
return;
}
if( uneInfo.donneVal() < valeur.donneVal() )
{
if( !fg ) fg = new Abr;
fg->ajout(uneInfo);
}
else
{
if( !fd ) fd = new Abr;
fd->ajout(uneInfo);
}
}
void Abr::explore(Tableau& unTab, int& ind) const
{
if( fg ) fg->explore(unTab, ind);
unTab[ind++] = valeur;
if( fd ) fd->explore(unTab, ind);
}
// ceci explore l'arbre en remplissant le tableau en ordre croissant
// par récursivité
///////////////////////////////////////////////
// pourrait s'utiliser comme cela
Tableau unTab(1000);
Abr monAbr;
int indice = 1;
// remplissage non trié
remplirTableau(unTab);
// ajout dans l'abr
for(int i=1; i<unTab.nbrElements(); i++)
monAbr.ajout(unTab[i]);
// ici on rerempli le tableau en le triant
monAbr.explore(unTab, indice);
// seul inconvénient, la duplication des données dans le tab et l'abr