Programme de manipulation des arbres
Contenu du snippet
Ce petit bout de programme est dstiné au debutant en c++ qui travaillent sur des arbres,il est du moins assez detaillé. Les affichages sont sous forme linéaire...
Si quelqu'un sait comment afficher des arbres en arborescence,je serai ravi d'en apprendre plus dessus! Soyez pas trop dûr,je débute...
Ceci n'est qu'une base,vous pouvez optimiser ce programme et je reste ouvert à tous conseils ou suggestion...Merci
Pas de bugs en ce moment,mais j'ai eu quelques erreurs de segmentation dûes au fait que je gerais mal mes pointeurs!
Si quelqu'un sait comment afficher des arbres en arborescence,je serai ravi d'en apprendre plus dessus! Soyez pas trop dûr,je débute...
Ceci n'est qu'une base,vous pouvez optimiser ce programme et je reste ouvert à tous conseils ou suggestion...Merci
Source / Exemple :
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <cstddef> // pr le NULL
using namespace std; //necessaire sous VC++6 pas sous linux
struct Noeud
{
int Val;
Noeud * SAG; // fils gauche
Noeud * SAD; // fils droit
Noeud * PERE;
};
class Bin_Tree // Binary Tree
{
public:
Noeud * Root; //declarée globale pr un acces plus facile...
Bin_Tree( );
Noeud * RechercheNoeud(int data,Noeud* courant);
Noeud * InsererNoeud(int data,Noeud* courant);
void CreerNoeud( );
void Afficher_Ordre(Noeud* courant);
void Afficher_Pre_Ordre(Noeud* courant);
void Afficher_Post_Ordre(Noeud* courant);
void SupprimerNoeud(int data,Noeud* courant);
int Taille_Arbre(Noeud* courant);
int Hauteur_Arbre(Noeud* courant);
int Max(int a,int b);
int Menu();
};
Bin_Tree::Bin_Tree( )
{
Root = NULL;
}
/********** INSERER NOEUD DANS ARBRE ***********/
Noeud * Bin_Tree::InsererNoeud(int data,Noeud * courant)
{
if(!courant)
{
courant=new(Noeud);
courant->Val=data;
courant->SAG=NULL;
courant->SAD=NULL;
courant->PERE=NULL;
}
else
{
if(courant->Val > data)
{
courant->SAG = InsererNoeud(data,courant->SAG);
courant->SAG ->PERE = courant;
}
else
{
courant->SAD = InsererNoeud(data,courant->SAD);
courant->SAD->PERE = courant;
}
}
return courant;
}
/************ CREER LA RACINE DE L'ARBRE **********/
void Bin_Tree::CreerNoeud( )
{
char rep;
int data;
do
{
cout<<endl<<"entrer une valeur(entier) pour la racine : "; cin>>data;
Root=InsererNoeud(data,Root);
cout<<"Un autre noeud? O/N : "; cin>>rep;
}
while((rep=='o') || (rep=='O'));
}
/************AFFICHE EN PRE-ORDRE ************/
void Bin_Tree::Afficher_Pre_Ordre(Noeud* courant)
{
if(courant != NULL)
{
cout<<" -> "<<courant->Val;
Afficher_Pre_Ordre(courant->SAG);
Afficher_Pre_Ordre(courant->SAD);
}
}
/************ AFFICHER ARBRE EN ORDRE ( INFIXE ) ********/
void Bin_Tree::Afficher_Ordre(Noeud* courant)
{
if (courant != NULL)
{
Afficher_Ordre(courant->SAG);
cout<<" -> "<<courant->Val;
Afficher_Ordre(courant->SAD);
}
}
/************ AFFICHER EN POST-ORDRE ********/
void Bin_Tree::Afficher_Post_Ordre(Noeud * courant)
{
if(courant != NULL)
{
Afficher_Post_Ordre(courant->SAG);
Afficher_Post_Ordre(courant->SAD);
cout<<" -> "<< courant->Val;
}
}
/************ RECHERCHE D'UN NOEUD **********/
Noeud * Bin_Tree::RechercheNoeud(int data,Noeud * courant)
{
if (courant != NULL)
{
if (courant->Val > data)
{
RechercheNoeud(data,courant->SAG); /* Va chercher à gauche du Noeud courant */
}
else
{
if (courant->Val < data)
{
RechercheNoeud(data,courant->SAD); /* Va chercher à droite du Noeud courant */
}
else // ici,on a trouvé le noeud...
{
cout<<" Le Noeud existe son adresse est: "<<endl;
return courant;
}
}
}
else
{
cout<<"Noeud inexistant,adresse Nulle: ";
return NULL; cout<<endl;
}
}
/************** TAILLE DE L'ARBRE **********/
int Bin_Tree::Taille_Arbre(Noeud * courant)
{
if(courant==NULL)
{
return 0;
}
else
{
return 1+ Taille_Arbre(courant->SAG) + Taille_Arbre(courant->SAD);
}
}
/* definition d'une petite fonction pr avoir le max de 2 éléments */
int Bin_Tree:: Max(int a,int b)
{
return a < b ? a : b;
}
int Bin_Tree::Hauteur_Arbre(Noeud * courant)
{
if(courant==NULL)
{
return 0;
}
else
{
return 1 + Max(Hauteur_Arbre(courant->SAD),Hauteur_Arbre(courant->SAG));
}
}
/********SUPPRIMER UN NOEUD *****/
void Bin_Tree::SupprimerNoeud(int data,Noeud * courant)
{
courant=RechercheNoeud(data,courant);
if (data == courant->Val) // Le Noeud à supprimer est trouvé
{
delete courant;
courant=NULL;
cout<<"Le noeud a ete supprime avec succes"<<endl<<endl;
}
else
{
cout<<"Le noeud est inexistant";
}
}
if(courant->Val < data)
{
SupprimerNoeud(data,courant->SAD);
}
else
{
if(courant->Val > data)
{
SupprimerNoeud(data,courant->SAG);
}
else
{
cout<<"Aucun Noeud ne correspond a votre recherche !!! "; cout<<endl;
}
}
}
}
/* PETIT MENU POUR CHOISIR LA FONCTION A TESTER DANS LE main() */
int Bin_Tree::Menu()
{
int Choix;
do
{
system("cls");
cout<<" ----------------------------- "<<endl;
cout<<" | M E N U P R I N C I P A L | " << endl;
cout<<" ----------------------------- "<<endl<<endl;
cout<<" 1- AFFICHAGE EN PREORDRE : " <<endl;
cout<<" 2- AFFICHAGE EN ORDRE : " <<endl;
cout<<" 3- AFFICHAGE EN POSTORDRE : " <<endl;
cout<<" 4- RECHERCHER UN NOEUD : " <<endl;
cout<<" 5- TAILLE ARBRE BINAIRE : " <<endl;
cout<<" 6- HAUTEUR ARBRE BINAIRE : " <<endl;
cout<<" 7- SUPPRIMER UN NOEUD : " <<endl<<endl;
cout<<" Choix : " ;
cin>>Choix ; cout<<endl;
}
while((Choix < 1) || (Choix > 8));
return Choix;
}
/************PROGRAMME PRINCIPAL**************/
int main(int argc,char **argv)
{
Bin_Tree Ar;
int Choix;
int valeur=0;
Ar.CreerNoeud( );
Choix = Ar.Menu();
while((Choix < 1)||(Choix > 8)) // si mauvais choix,retourne au menu;
{
return Ar.Menu();
}
switch (Choix)
{
case 1 :
if(Ar.Root == NULL)
{
cout <<"Rien a afficher car arbre vide!!!"<<endl<<endl;
}
else
{
cout<<"AFFICHAGE EN PREORDRE:" <<endl<<endl;
Ar.Afficher_Pre_Ordre(Ar.Root);cout<<endl;;
}
break;
case 2 : if(Ar.Root == NULL)
{
cout <<"Rien a afficher car arbre vide!!!"<<endl<<endl;
}
else
{
cout<<"AFFICHAGE EN ORDRE : "<< endl;
Ar.Afficher_Ordre(Ar.Root);cout<<endl;
}
break;
case 3 :
if(Ar.Root == NULL)
{
cout <<"Rien a afficher car arbre vide!!!"<<endl<<endl;
}
else
{
cout<<"Affichage en POSTORDRE : " <<endl;
Ar.Afficher_Post_Ordre(Ar.Root);cout<<endl;
}
break;
case 4 :if(Ar.Root==NULL) cout<<"Recherche impossible car arbre vide";
else
{
cout<<"Entrer la valeur contenue dans le noeud a rechercher : ";
cin>>valeur; cout<< endl;
cout<<Ar.RechercheNoeud(valeur,Ar.Root)<<endl<<endl;
}
break;
case 5 :cout<<"TAILLE = "<<Ar.Taille_Arbre(Ar.Root)<<endl<<endl;
break;
case 6 :cout<<"HAUTEUR = "<<Ar.Hauteur_Arbre(Ar.Root)<<endl<<endl;
break;
case 7 :
if(Ar.Root == NULL)
{
cout <<"Rien a supprimer car arbre vide!!!"<<endl;
}
else
{
cout<<"Valeur dans le noeud a supprimer: ";cin>>valeur;
Ar.SupprimerNoeud(valeur,Ar.Root);
}
break;
}
return (0);
}
Conclusion :
Pas de bugs en ce moment,mais j'ai eu quelques erreurs de segmentation dûes au fait que je gerais mal mes pointeurs!
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.