Arbre binaire

Soyez le premier à donner votre avis sur cette source.

Snippet vu 15 901 fois - Téléchargée 31 fois

Contenu du snippet

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; }

A voir également

Ajouter un commentaire Commentaires
Messages postés
4
Date d'inscription
lundi 6 avril 2009
Statut
Membre
Dernière intervention
6 avril 2009

g pas trop aimer mais tu as essayer com mem
Messages postés
6
Date d'inscription
mercredi 29 janvier 2003
Statut
Membre
Dernière intervention
31 mars 2005

euh un arbre binaire ca veut pas dire que le pointeur de gauche il contien une valeur inferieure sauf si tu travailles avec un ABOH (;

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.