|
Trouver une ressource
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !
GESTION D'UN ARBRE BINAIRE PAR LES CLASSES
Information sur la source
Description
Ceci compléte la recherche des alogorithmes de base, dans la même série que la Pile,File voici : "la gestion élémentaire d'un arbre binaire en utilisant une classe dynamique". Qu'est ce qu'un arbre binaire : On peu concevoir un arbre binaire comme un noeud racine composé de deux branches (une gauche et une droite)chaque brance est composé d'un noeud, lui-même composé de deux branches. voir le NET pour plus d'info... Celui-ci est utilisé comme cet exemple pour faire des tris. L'exemple de test utilise un tri de char. Ce code à été compilé avec Borland C++ 5.5 (sans Bug apparent)
Source
- #include <stdio.h>
- #include <iostream>
- using namespace std;
-
- //On va creer ici un arbre binaire
- //un arbre qui a 1 noeuds constitué de deux branches, un sur la gauche, qui contient
- //les valeurs inferieurs au noeud en cours, et une sur la droite, qui
- //contient les valeurs supérieures ...
-
- template <class T> class Cl_Arbre;
-
- //--------------------------------------------------------
- // DEBUT CLASSE Cl_Noeud
- //--------------------------------------------------------
- template <class T>
- class Cl_Noeud{
- private:
- static int NbrNoeuds;
-
- public:
- Cl_Noeud *gauche;
- Cl_Noeud *droite;
- T valeur;
- inline T & val()const{return valeur;};
- Cl_Noeud(){NbrNoeuds++;};
- ~Cl_Noeud(){delete gauche;delete droite;};
- friend class Cl_Arbre <T> ;
- };//end class
- //--------------------------------------------------------
- // FIN CLASSE Cl_Noeud
- //--------------------------------------------------------
- template<class T>
- int Cl_Noeud<T>::NbrNoeuds = 0;
- //--------------------------------------------------------
- // DEBUT CLASSE Cl_Arbre
- //--------------------------------------------------------
- template<class T>
- class Cl_Arbre{
- private:
- Cl_Noeud <T> *racine;
- void Inserer (Cl_Noeud <T> *);
- void Balayage(Cl_Noeud <T> *);
- Cl_Noeud <T> *DonnepRacine()const{return racine;};// renvoie un pointeur sur le pNoeud racine
- Cl_Noeud <T> *Rechercher (const T)const;
-
- public:
- Cl_Arbre (){racine = NULL;} //constructeur
- ~Cl_Arbre (){delete racine;} //constructeur
- void Creer (const T);
- void Supprimer(const T);
- void Affichage(void);
- void NbrNoeuds(void){cout << Cl_Noeud<T>::NbrNoeuds;};
- };//end class
- //--------------------------------------------------------
- // FIN CLASSE Cl_Arbre
- //--------------------------------------------------------
- //------------------------------------------------------------------------------
- // FONCTION : Affichage
- // DESCRIPTION : Affiche l'arbre à l'écran
- //-------------------------------------------------------------------------------
- template <class T>
- void Cl_Arbre<T>::Affichage(){
- //Si racine différent de NULL alors il affiche l'arbre
- if(racine!=NULL)
- //Affectation du pointeur racine à pNoeud
- Balayage(racine);
- else
- cout << "Arbre vide!" << endl;
- //end if
- }//end process
-
- //------------------------------------------------------------------------------
- // FONCTION : Balaye
- // DESCRIPTION : fonction recursive de balayage dans l'arbre
- //-------------------------------------------------------------------------------
- template <class T>
- void Cl_Arbre<T>::Balayage(Cl_Noeud<T> *pNoeud){
-
- //On traverse vers la gauche (valeurs inferieures), si il existe
- if (pNoeud->gauche) Balayage(pNoeud->gauche);
-
- //On affiche le noeud en cours
- if (pNoeud) cout << pNoeud->valeur << "\n";
-
- //Et traverse vers la droite (valeurs superieurs)
- if (pNoeud->droite) Balayage(pNoeud->droite);
-
- }//end process
-
- //------------------------------------------------------------------------------
- // FONCTION : Creer
- // DESCRIPTION : Création d'un Noeud
- //-------------------------------------------------------------------------------
- template <class T>
- void Cl_Arbre <T>::Creer(const T val){
- //Allocation memoire pour un nouveau pNoeud
- Cl_Noeud <T> * pNoeudTmp = new Cl_Noeud <T>;
- //Initialisation des pointeur pNoeud à NULL
- pNoeudTmp->gauche = NULL;
- pNoeudTmp->droite = NULL;
- //Transfert de la valeur
- pNoeudTmp->valeur = val;
- //Insérer dans l'arborescence de l'arbre
- Inserer (pNoeudTmp);
- }//end process
-
- //------------------------------------------------------------------------------
- // FONCTION : Inserer
- // DESCRIPTION : Insertion d'un pNoeud dans l'arbre;
- //-------------------------------------------------------------------------------
- template <class T>
- void Cl_Arbre<T>::Inserer(Cl_Noeud <T> *pNoeud){
- //Si le pNoeud est vide, on sort
- if (!pNoeud) return;
-
- //Si l'arbre est vide, on lui accroche le Noeud et on sort
- if (racine == NULL){
- racine = pNoeud;
- return;
- }//end if
-
- //Création de deux pointeurs de déplacement dans l'arbre et initilisation
- Cl_Noeud<T> * courant = racine;
- Cl_Noeud<T> * precedent = NULL;
-
- //On se déplace à travers l'arbre jusqu'a ce que courant atteint la valeur NULL
- //precedent memorise l'adresse du dernier Noeud
- while (courant){
- precedent = courant;
- if (pNoeud->valeur < courant->valeur)
- courant = courant->gauche;
- else
- courant = courant->droite;
- }//end while
-
- //Maintenant on place le nouveau noeud dans la bonne branche
- if(pNoeud->valeur < precedent->valeur)
- precedent->gauche = pNoeud;
- else
- precedent->droite = pNoeud;
- }//end process
-
- //------------------------------------------------------------------------------
- // FONCTION : Supprimer
- // DESCRIPTION : Supprime une pNoeud de l arbre
- // On peut obtenir un pointeur sur un pNoeud via la methode Rechercher(...);
- //-------------------------------------------------------------------------------
- template<class T>
- void Cl_Arbre<T>::Supprimer(const T val){
-
- Cl_Noeud<T> *pNoeud = Rechercher(val);
-
- //Si le noeud est = NULL , on sort la valeur n'existe pas.
- if (!pNoeud){
- cout << "Recherche infructueuse! impossible de trouver cette valeur." << endl;
- return;
- }//end if
-
- //Créations 3 pointeurs pour mémoriser
- //les paramétres de pointeurs du Noeuds à supprimer et la racine
- Cl_Noeud<T> *droite = pNoeud->droite;
- Cl_Noeud<T> *gauche = pNoeud->gauche;
- Cl_Noeud<T> *courant = racine;
-
- //CAS 1 : La valeur à supprimer est dans le noeud racine
- if(pNoeud == racine){
- //On transfer le pointeur droite supérieur dans racine
- racine = droite;
-
- //Si le pointeur gauche du noeud supprimé n'est pas NULL,
- //Il faut réinsérer le noeud qui à été coupé par la suppression
- //pour reconstruire notre arbre
- if(gauche) Inserer(gauche);
-
- //On libere la mémoire du noeud contenant la valeur supprimée
- delete pNoeud;
- return;
- }//end if
-
- //CAS 2 : tous les autres cas
- // on fait un balayage à travers l'arborescence
- while(courant){
- //Si une des branches de ce noeud est celle que l'on recherche,
- //on sort de la boucle while
- if(courant->droite == pNoeud || courant->gauche == pNoeud) break;
-
- //Sinon, on continue
- if(pNoeud->valeur >= courant->valeur)
- courant = courant->droite;
- else
- courant = courant->gauche;
- }//end while
-
- if(courant->droite == pNoeud)
- courant->droite = droite;
- else
- courant->gauche = droite;
- //end if
-
- //Accrochage du fils du Noeud disparu
- if(gauche) Inserer(gauche);
-
- //Enfin, on libère l'objet pNoeud de la mémoire
- delete pNoeud;
- cout << "Noeud effacé!" << endl;
- }//end process
-
- //------------------------------------------------------------------------------
- // FONCTION : Rechercher
- // DESCRIPTION : Renvoie un pointeur sur un element
- // de l'arbre qui est == a val
- //-------------------------------------------------------------------------------
- template <class T>
- Cl_Noeud<T> *Cl_Arbre<T>::Rechercher(const T val)const{
-
- //Création d'un pointeur de mémorisation d'adresse de racine
- Cl_Noeud<T> *courant = racine;
-
- //Si la valeur du pointeur n'est pas NULL on continue
- while(courant){
- //Si le Noeud a la bonne valeur,
- //on renvoie l'adresse du pointeur courant sinon on continue
- if(courant->valeur == val) return courant;
-
- //Si la valeur est inférieure, on control le noeud de droite
- //Si elle est supérieure, on contrôl le noeud de gauche
- if (val < courant->valeur)
- courant = courant->gauche;
- else
- courant = courant->droite;
- }//end while
-
- //Si rien trouvé on retourne la valeur NULL
- return NULL;
- }//end process
-
-
-
- void main(void){
- //On cree un nouvel arbre, qui contiendra des entiers
- Cl_Arbre <char> arbre;
-
- //On le remplit de valeurs
- arbre.Creer('C');
- arbre.Creer('A');
- arbre.Creer('X');
- arbre.Creer('Z');
- arbre.Creer('T');
- arbre.Creer('I');
- arbre.Creer('H');
- arbre.Creer('M');
-
- //En affichant, on se rend compte que l arbre est trié
- //Magique !
- arbre.Affichage();
- cout << "\nFIN PROGRAM 1" << endl;
- arbre.Supprimer('Z');
- arbre.Affichage();
- cout << "\nFIN PROGRAM 2" << endl;
- arbre.NbrNoeuds();
- }
#include <stdio.h>
#include <iostream>
using namespace std;
//On va creer ici un arbre binaire
//un arbre qui a 1 noeuds constitué de deux branches, un sur la gauche, qui contient
//les valeurs inferieurs au noeud en cours, et une sur la droite, qui
//contient les valeurs supérieures ...
template <class T> class Cl_Arbre;
//--------------------------------------------------------
// DEBUT CLASSE Cl_Noeud
//--------------------------------------------------------
template <class T>
class Cl_Noeud{
private:
static int NbrNoeuds;
public:
Cl_Noeud *gauche;
Cl_Noeud *droite;
T valeur;
inline T & val()const{return valeur;};
Cl_Noeud(){NbrNoeuds++;};
~Cl_Noeud(){delete gauche;delete droite;};
friend class Cl_Arbre <T> ;
};//end class
//--------------------------------------------------------
// FIN CLASSE Cl_Noeud
//--------------------------------------------------------
template<class T>
int Cl_Noeud<T>::NbrNoeuds = 0;
//--------------------------------------------------------
// DEBUT CLASSE Cl_Arbre
//--------------------------------------------------------
template<class T>
class Cl_Arbre{
private:
Cl_Noeud <T> *racine;
void Inserer (Cl_Noeud <T> *);
void Balayage(Cl_Noeud <T> *);
Cl_Noeud <T> *DonnepRacine()const{return racine;};// renvoie un pointeur sur le pNoeud racine
Cl_Noeud <T> *Rechercher (const T)const;
public:
Cl_Arbre (){racine = NULL;} //constructeur
~Cl_Arbre (){delete racine;} //constructeur
void Creer (const T);
void Supprimer(const T);
void Affichage(void);
void NbrNoeuds(void){cout << Cl_Noeud<T>::NbrNoeuds;};
};//end class
//--------------------------------------------------------
// FIN CLASSE Cl_Arbre
//--------------------------------------------------------
//------------------------------------------------------------------------------
// FONCTION : Affichage
// DESCRIPTION : Affiche l'arbre à l'écran
//-------------------------------------------------------------------------------
template <class T>
void Cl_Arbre<T>::Affichage(){
//Si racine différent de NULL alors il affiche l'arbre
if(racine!=NULL)
//Affectation du pointeur racine à pNoeud
Balayage(racine);
else
cout << "Arbre vide!" << endl;
//end if
}//end process
//------------------------------------------------------------------------------
// FONCTION : Balaye
// DESCRIPTION : fonction recursive de balayage dans l'arbre
//-------------------------------------------------------------------------------
template <class T>
void Cl_Arbre<T>::Balayage(Cl_Noeud<T> *pNoeud){
//On traverse vers la gauche (valeurs inferieures), si il existe
if (pNoeud->gauche) Balayage(pNoeud->gauche);
//On affiche le noeud en cours
if (pNoeud) cout << pNoeud->valeur << "\n";
//Et traverse vers la droite (valeurs superieurs)
if (pNoeud->droite) Balayage(pNoeud->droite);
}//end process
//------------------------------------------------------------------------------
// FONCTION : Creer
// DESCRIPTION : Création d'un Noeud
//-------------------------------------------------------------------------------
template <class T>
void Cl_Arbre <T>::Creer(const T val){
//Allocation memoire pour un nouveau pNoeud
Cl_Noeud <T> * pNoeudTmp = new Cl_Noeud <T>;
//Initialisation des pointeur pNoeud à NULL
pNoeudTmp->gauche = NULL;
pNoeudTmp->droite = NULL;
//Transfert de la valeur
pNoeudTmp->valeur = val;
//Insérer dans l'arborescence de l'arbre
Inserer (pNoeudTmp);
}//end process
//------------------------------------------------------------------------------
// FONCTION : Inserer
// DESCRIPTION : Insertion d'un pNoeud dans l'arbre;
//-------------------------------------------------------------------------------
template <class T>
void Cl_Arbre<T>::Inserer(Cl_Noeud <T> *pNoeud){
//Si le pNoeud est vide, on sort
if (!pNoeud) return;
//Si l'arbre est vide, on lui accroche le Noeud et on sort
if (racine == NULL){
racine = pNoeud;
return;
}//end if
//Création de deux pointeurs de déplacement dans l'arbre et initilisation
Cl_Noeud<T> * courant = racine;
Cl_Noeud<T> * precedent = NULL;
//On se déplace à travers l'arbre jusqu'a ce que courant atteint la valeur NULL
//precedent memorise l'adresse du dernier Noeud
while (courant){
precedent = courant;
if (pNoeud->valeur < courant->valeur)
courant = courant->gauche;
else
courant = courant->droite;
}//end while
//Maintenant on place le nouveau noeud dans la bonne branche
if(pNoeud->valeur < precedent->valeur)
precedent->gauche = pNoeud;
else
precedent->droite = pNoeud;
}//end process
//------------------------------------------------------------------------------
// FONCTION : Supprimer
// DESCRIPTION : Supprime une pNoeud de l arbre
// On peut obtenir un pointeur sur un pNoeud via la methode Rechercher(...);
//-------------------------------------------------------------------------------
template<class T>
void Cl_Arbre<T>::Supprimer(const T val){
Cl_Noeud<T> *pNoeud = Rechercher(val);
//Si le noeud est = NULL , on sort la valeur n'existe pas.
if (!pNoeud){
cout << "Recherche infructueuse! impossible de trouver cette valeur." << endl;
return;
}//end if
//Créations 3 pointeurs pour mémoriser
//les paramétres de pointeurs du Noeuds à supprimer et la racine
Cl_Noeud<T> *droite = pNoeud->droite;
Cl_Noeud<T> *gauche = pNoeud->gauche;
Cl_Noeud<T> *courant = racine;
//CAS 1 : La valeur à supprimer est dans le noeud racine
if(pNoeud == racine){
//On transfer le pointeur droite supérieur dans racine
racine = droite;
//Si le pointeur gauche du noeud supprimé n'est pas NULL,
//Il faut réinsérer le noeud qui à été coupé par la suppression
//pour reconstruire notre arbre
if(gauche) Inserer(gauche);
//On libere la mémoire du noeud contenant la valeur supprimée
delete pNoeud;
return;
}//end if
//CAS 2 : tous les autres cas
// on fait un balayage à travers l'arborescence
while(courant){
//Si une des branches de ce noeud est celle que l'on recherche,
//on sort de la boucle while
if(courant->droite == pNoeud || courant->gauche == pNoeud) break;
//Sinon, on continue
if(pNoeud->valeur >= courant->valeur)
courant = courant->droite;
else
courant = courant->gauche;
}//end while
if(courant->droite == pNoeud)
courant->droite = droite;
else
courant->gauche = droite;
//end if
//Accrochage du fils du Noeud disparu
if(gauche) Inserer(gauche);
//Enfin, on libère l'objet pNoeud de la mémoire
delete pNoeud;
cout << "Noeud effacé!" << endl;
}//end process
//------------------------------------------------------------------------------
// FONCTION : Rechercher
// DESCRIPTION : Renvoie un pointeur sur un element
// de l'arbre qui est == a val
//-------------------------------------------------------------------------------
template <class T>
Cl_Noeud<T> *Cl_Arbre<T>::Rechercher(const T val)const{
//Création d'un pointeur de mémorisation d'adresse de racine
Cl_Noeud<T> *courant = racine;
//Si la valeur du pointeur n'est pas NULL on continue
while(courant){
//Si le Noeud a la bonne valeur,
//on renvoie l'adresse du pointeur courant sinon on continue
if(courant->valeur == val) return courant;
//Si la valeur est inférieure, on control le noeud de droite
//Si elle est supérieure, on contrôl le noeud de gauche
if (val < courant->valeur)
courant = courant->gauche;
else
courant = courant->droite;
}//end while
//Si rien trouvé on retourne la valeur NULL
return NULL;
}//end process
void main(void){
//On cree un nouvel arbre, qui contiendra des entiers
Cl_Arbre <char> arbre;
//On le remplit de valeurs
arbre.Creer('C');
arbre.Creer('A');
arbre.Creer('X');
arbre.Creer('Z');
arbre.Creer('T');
arbre.Creer('I');
arbre.Creer('H');
arbre.Creer('M');
//En affichant, on se rend compte que l arbre est trié
//Magique !
arbre.Affichage();
cout << "\nFIN PROGRAM 1" << endl;
arbre.Supprimer('Z');
arbre.Affichage();
cout << "\nFIN PROGRAM 2" << endl;
arbre.NbrNoeuds();
}
Conclusion
Ceci est un exemple de base (n'est peut-être pas la meilleur sollution mais cela fonctionne.
Historique
- 25 juillet 2006 18:21:44 :
- changement des includes
Sources du même auteur
Sources de la même categorie
Sources en rapport avec celle ci
Commentaires et avis
Discussions en rapport avec ce code source dans le forum
prob d'algorithme dans matrice [ par gregorian ]
Bonjour, Voila je dois écrire un prg en C qui joue avec des matrices booléennes.J'ai déjà fait la partie addition, multiplication,
algorithme de lemmatisation HELP [ par spamoutik ]
salut!je ne sais pas si je suis ds la bonne section pour ce poste mais bon,je cherchais un algorithme de la lemmatisation de mot et je suis tombé sur
Algorithme de visio conference [ par Timwaz ]
Bonjour, Je dois pour un projet présenter un algo de visioconference (système simple). Cela fait suite à un cours de programmation système sous linux
algo canny [ par salma2011 ]
Slt tt le monde,,Je veux detecter les contours d'une image avec l'algorithme de canny en utilisant le langage c++ ..je veux un simple code( en c++ )
contour actif [ par mar1985 ]
Bonjour,S'il vous plaît j'ai besoin de votre aide et c très urgent.j'implémente l'algorithme de contour actif.Comme vous le savez, il y a plusieurs im
Création de nombres en binaire [ par mrpsychopathe ]
Bonjour,J'essaye de faire un petit programme de compression de fichier et donc je cherche un algorithme qui permet de créer des nombres en binaire en
Transposée de matrice algo? [ par YOOP ]
Bonjour,Le contexte :-------------Je travaille sur un programme embarqué en C sur PIC (µC). (Compilateur MCC18 du constructeur)Je suis soucieux de la
A l'aide [ par alex64100 ]
bonjourétudiantt par correspondance, je bataille sur un algo je dois créer un prog en c, calculan les facteurs 1er d'un entier n a partir de l'algo s
|
Téléchargements
Logiciels à télécharger sur le même thème :
Comparez les prix Nouvelle version

HTC Touch HD
Entre 25€ et 605€
|