une classe d arbre binaire ... tout est dans le code, c est commenté a mort, mais si vous avez une question, n hesitez pas a la poser ...
l arbre n est pas equilibré, faut que je travaille ca ...
c est juste un truc de base, on peut pas faire grand chose avec (bien que l utilisation des templates le rend un peu plus utile).
Source / Exemple :
#include <iostream.h>
/*
On va creer ici un arbre binaire
Mais keskeussay un arbre binaire ?
ben c est un arbre qui a 2 noeuds, un sur la gauche, qui contient
les valeurs inferieurs au noeud en cours, et une suer la droite, qui
contient les valeurs supérieures ...
Allez go, au code.
/*
Noeud de l arbre
template <class T>
class Noeud
{
public:
Noeud* gauche;
Noeud* droite;
T valeur;
inline T& val(){
return valeur;
};
};
/*
L arbre lui meme
Les templates servent a gérer tous les types, pour peux qu' ils possedent
un operateur < surchargé
template<class T>
class Arbre
{
public:
/*
Constructeur
Arbre (){
m_pTree = NULL;
}
/*
Methodes utiles
void Ajouter (T val);
Noeud<T>* Rechercher (T val);
void Supprimer(Noeud<T>* pNode);
/*
Accesseurs
Noeud<T>* root(){
// renvoie un pointeur sur le pNode de base
return m_pTree;
}
private:
// fonction privée car non nécessaire
void Placer (Noeud<T> *pNode);
Noeud<T>* m_pTree;
};
/*
Place un pNode dans l arbre;
template <class T>
void Arbre<T> :: Placer ( Noeud<T>* pNode )
{
// si le pNode est vide, on sort
if ( !pNode )
return;
// si l arbre est vide, on lui copie cette branche
if ( m_pTree == NULL )
{
m_pTree = pNode;
return;
}
Noeud<T>* courant = m_pTree;
Noeud<T>* precedent = NULL;
// on se fraie un chemin a travers l arbre
while ( courant )
{
precedent = courant;
if ( pNode->valeur < courant->valeur )
courant = courant->gauche;
else
courant = courant->droite;
}
// maintenant on demande aux branches precedentes de pointeur sur ce pNode
if( pNode->valeur < precedent->valeur )
precedent->gauche = pNode;
else
precedent->droite = pNode;
}
/*
Ajoute une element a l arbre
template <class T>
void Arbre<T> :: Ajouter ( T val )
{
// Alloue de la memoire pour un nouveau pNode
Noeud<T>* tmp = new Noeud<T>;
// on ne sait pas encore sur quoi le pNode va pointer
tmp->gauche = NULL;
tmp->droite = NULL;
// on lui copie la valeur
tmp->valeur = val;
// et l ajoute a l arbre
Placer (tmp);
}
/*
Renvoie un pointeur sur un element de l arbre qui est == a val
template <class T>
Noeud<T>* Arbre <T> :: Rechercher ( T val )
{
Noeud<T>* curr = m_pTree;
// on traverse l arbre
while (curr)
{
// si ce pNode a la bonne valeur, on a trouvé
if(curr->valeur == val)
return curr;
// sinon, on sait si le pNode qu on cherche est plutot vers la gauche ou vers la droite
// car lorsqu on a construit l arbre, on l a organisé de maniere a ce que les valeurs
// plus petites soient vers la gauche et les plus garndes vers la droite
if (val < curr->valeur)
curr = curr->gauche;
else
curr = curr->droite;
}
// rien trouvé
return NULL;
}
/*
Supprime une pNode de l arbre
On peut obtenir un pointeur sur un pNode via la methode Rechercher(...);
template<class T>
void Arbre<T> :: Supprimer( Noeud<T>* pNode )
{
// si le noeud est vide, on sort
if ( !pNode )
return;
// on sauvegarde des valeurs
Noeud<T>* droite = pNode->droite;
Noeud<T>* gauche = pNode->gauche;
Noeud<T>* courant = m_pTree;
// Cas délicat : si on supprime la racine?
if( pNode == m_pTree )
{
// la valeur superieur est toujours a droite
m_pTree = droite;
// mais il ne faut pas oublier celle de gauche
if( gauche )
Placer( gauche );
// on vire la racine et on sort
delete pNode;
return;
}
// on traverse tout l arbre
while( courant )
{
// si une des feuilles de ce noeud est celle qu on cherche, on sort
if( courant->droite == pNode || courant->gauche == pNode )
break;
// sinon, on traverse
if( pNode->valeur >= courant->valeur )
courant = courant->droite;
else
courant = courant->gauche;
}
if( courant->droite == pNode )
courant->droite = droite;
else
courant->gauche = droite;
// Et puis on replace l'autre fils du pNode disparu
if( gauche )
Placer( gauche );
// Enfin, on libère l'objet pNode de ses obligations
delete pNode;
}
/*
Fonction qui affiche l arbre
un operateur << est necessaire
mise en globale, et non pas en methode de classe car
elle n est pas necessaire a la gestion de l arbre et pas très utile
template <class T>
void Afficher ( Noeud<T> *pNode )
{
// on traverse vers la gauche (valeurs inferieures), si il existe
if ( pNode->gauche )
Afficher (pNode->gauche);
// on affiche le noeud en cours
if ( pNode )
cout << pNode->valeur << "\n";
// et traverse vers la droite (valeurs superieurs)
if ( pNode->droite )
Afficher (pNode->droite);
}
int main ()
{
// on cree un nouvel arbre, qui contiendra des entiers
Arbre <int> arbre;
// on le remplit de valeurs
arbre.Ajouter ( 10 );
arbre.Ajouter ( 4 );
arbre.Ajouter ( 15 );
arbre.Ajouter ( 2 );
arbre.Ajouter ( 16 );
arbre.Ajouter ( 1 );
arbre.Ajouter ( 9 );
arbre.Ajouter ( 14 );
// En affichant, on se rend compte que l arbre est trié
// Magique !
Afficher ( arbre.root ( ) );
// on vire quelques valeurs
arbre.Supprimer ( arbre.Rechercher( 14 ) );
arbre.Supprimer ( arbre.root ( ) );
// et magique, l arbre est toujours trié ;)
Afficher ( arbre.root( ) );
int a; cin>>a; // pour que le prog ne se ferme pas en une seconde
// des solutions plus elegantes existent mais c est pas le but du programme d en trouver une jolie
return 0;
}
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.