Passage d'un arbre binaire ordonné à un tableau

Signaler
Messages postés
47
Date d'inscription
jeudi 20 avril 2006
Statut
Membre
Dernière intervention
3 mars 2015
-
Messages postés
1137
Date d'inscription
lundi 17 novembre 2003
Statut
Membre
Dernière intervention
23 janvier 2016
-
bonjour;
est ce que quelqu'un peut m'aider de me donner l'algorithme ou la fonction c du passage d'un arbre binaire ordoné vers un tableau triée comme l'exemple:

merci d'avance.

7 réponses

Messages postés
1329
Date d'inscription
vendredi 15 août 2003
Statut
Membre
Dernière intervention
16 juin 2010
2
Comme quel exemple ?

_______________________

Omnia vincit labor improbus
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
9
C:\Documents and Settings\thabet\Bureau\arbre.JPG        

Les images en local ca marche pas super :)

_____________________________________
Un éditeur de ressources gratuit pour Windows
Messages postés
1329
Date d'inscription
vendredi 15 août 2003
Statut
Membre
Dernière intervention
16 juin 2010
2
ptdrr xD

_______________________

Omnia vincit labor improbus
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
Les vacances scolaires, un pur moment de détente... Encore que, faudrait pas que ça dure trop longtemps.

ciao...
BruNews, MVP VC++
Messages postés
1329
Date d'inscription
vendredi 15 août 2003
Statut
Membre
Dernière intervention
16 juin 2010
2
Roh cha va, tout le monde n'a pas forcément 40 ans de PC derrière lui .. quoique celle çi était forte de café, j'avoue ^^

_______________________

Omnia vincit labor improbus
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
Messages postés
1137
Date d'inscription
lundi 17 novembre 2003
Statut
Membre
Dernière intervention
23 janvier 2016
24
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