PROGRAMME DE MANIPULATION DES ARBRES

---

Commentaire sur cette source (1)
Ajouter un commentaire et/ou une note

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

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

Pas de bugs en ce moment,mais j'ai eu quelques erreurs de segmentation dûes au fait que je gerais mal mes pointeurs!

• PETIT ALGO DE TRI...
• TRIS DE TABLEAUX PAR LES METHODES LES PLUS USUELLES...
• MANIPULATION DE MATRICES CARRÉES POUR DEBUTANTS!

• GESTION DES ENTREES/ SORTIES AVEC CODEBARRE
• QT4 ET MYSQL
• [WXWIDGETS] WXSQLITE+ 0.1 ALPHA - EXPLORATEUR DE FICHIER DE BASE DE DONNÉES SQLITE
• BASES DE DONNÉES ET LES PHOTOS
• GESTION DES PERSONNEL D'UNE ENTRPRISE EN UTILISANT LES LISTES CHAINEES ET LES FICHIERS