UTILISATION D'UN ARBRE BINAIRE ET DES CLASSES EN C++ (ALGORITHME)

/*******************************************************************
* Fichier string_nikko_defs.cpp
*
* Contient les définitions de la classe String
*
*******************************************************************/

#include "string_nikko.h"

//--------- OPERATOR = pour la classe Strg ------
Strg & Strg::operator=( const Strg & op2 )
{

	delete [] string;	//Libérer la mém. allouée par l'opérande gauche.
						//La taille initiale n'est pas bonne.

	if ( string = new char[ op2.len + 1 ] )
	{
		strcpy( string, op2.string );		//Copie de la chaîne
		len = op2.len;						//On "devient" comme l'autre. Même longueur.
	}
	else
		exit(1);

	return (*this);		//Retourne réf. de  l'opérande gauche.
}






//---------- OPERATOR + pour la classe Strg  -----
Strg  Strg::operator +( const Strg & op2)
{
	Strg resultat;
	
	if ( resultat.string = new char[ strlen(string) + strlen(op2.string)+ 1 ] )
	{
		strcpy( resultat.string, string );			//On prend le premier bout...
		strcat( resultat.string, op2.string );		//...et le deuxième.
		resultat.len = strlen(string) + strlen(op2.string);	
	}
	else
		exit(1);

	return resultat;				//Retourne la classe contenant le résultat.
									//Si c'était *this, cela signifirait que l'opérande
									//gauche est modifié !

}




//---------- OPERATOR == pour test d'égalité ---------
int Strg::operator ==( const Strg & op2 )
{
	int res = 0;				//Contiendra le résultat du test. (tjrs en INT )

	if ( strcmp( string, op2.string ) == 0 )
		res = 1;

	return res;
}



//-------- OPERATOR <= pour test ------------
int Strg::operator <=( const Strg & op2 )
{
	static int res;					//Contiendra le résultat du test. (tjrs en INT )

	if ( strcmp( string, op2.string ) == 0 )
		res = 1;
	
	if ( strcmp( string, op2.string ) < 0 )
		res = 1;

	return res;
}




//-------- OPERATOR >= pour test ------------
int Strg::operator >=( const Strg & op2 )
{
	static int res;					//Contiendra le résultat du test. (tjrs en INT )

	if ( strcmp( string, op2.string ) == 0 )
		res = 1;
	
	if ( strcmp( string, op2.string ) > 0 )
		res = 1;

	return res;
}




//---------- OPERATOR > pour test d'égalité ---------
int Strg::operator >( const Strg & op2 )
{
	static int res = 0;				//Contiendra le résultat du test. (tjrs en INT )

	if ( strcmp( string, op2.string ) > 0 )
		res = 1;

	return res;
}



//---------- OPERATOR < pour test d'égalité ---------
int Strg::operator <( const Strg & op2 )
{
	static int res = 0;				//Contiendra le résultat du test. (tjrs en INT )

	if ( strcmp( string, op2.string ) < 0 )
		res = 1;

	return res;
}



//-------- OPERATOR [] POUR INDEXATION -------------
char & Strg::operator []( const int & index )
{
	char * p = 0;
	if (( index > len ) || ( index < 0 ))
	{
		cerr << "ERREUR [] :" << endl << "Indice en dehors de la plage admise.";
		return *p;
	}

	return string[index];
}







//Surcharge de << pour cout:
ostream & operator <<( ostream & out, const Strg & op )
{
	out << op.string;

	return out;
}


//Surcharge de >> pour cin:
istream & operator >>( istream & in, Strg & op )
{
	char ph[256];

	in >> ph;
	delete [] op.string;

	if ((op.string = new char[ strlen( ph ) + 1 ]) != 0) 
	{
		strcpy( op.string, ph );
		op.len = strlen( op.string );
	}
	else
		exit (1);

	return in;
}



//-------------------------------------------
//         +=
//-------------------------------------------
void Strg::operator += ( const Strg op )
{
	Strg resultat;
	
	if ( resultat.string = new char[ strlen(string) + strlen(op.string)+ 1 ] )
	{
		strcpy( resultat.string, string );			//On prend le premier bout...
		strcat( resultat.string, op.string );		//...et le deuxième.
		resultat.len = strlen(string) + strlen(op.string);	
	}
	else
		exit(1);

	*this = resultat;
}



/*************************************************************************
* Fichier string_nikko.h
* 
***********************************************************************/

#ifndef STRING_NIKKO_H_
#define STRING_NIKKO_H_

#include <iostream.h>
#include <string.h>
#include <process.h>

// =======================================================================
class Strg
{
private:

	//------------------------------------------------------------
	//Données accessibles seulement par les fonctions ci-dessous
	//-------------------------------------------------------------
	char * string;
	int len;

public:

	//Ajout pour l'exo de l'arbre:
	int occurences;

	//---------------------------
	// Constructeur avec un char
	//---------------------------
	Strg( const char car )
	{
		if ( string = new char[ 2 ] )
		{
			string[ 0 ] = car;
			string[ 1 ] = '\0';
			occurences = 1;
		}
		else
			exit (1);
	}



	//-----------------------
	//Fonction Constructeur:
	//-----------------------

	Strg( const char * s = "" )
	{
		len = strlen( s );

		if ( string = new char[ len + 1 ] )			//Allocation mémoire pour un espace..
		{
			strcpy( string, s );
			occurences = 1;			
		}
		else
			exit (1);
	}

	//---------------------
	//Fonction Destructeur
	//---------------------

	~Strg()								//Destructeur: la mémoire doit être
	{									//libérée car prise avec NEW

		if ( string == 0 )
			cout << "WARNING: Tentative de destruction d'1 pointeur nul !" << endl;
		else
		{
			delete [] string;
			string = 0;			//Pour ne pas le réutiliser.
		}
	}									

	//--------------------------
	//Accès à la chaîne de car. 
	//--------------------------
	
	char * show()
	{
		return string;
	}
	
	//---------------------------------------
	//Accès en écriture de la chaîne de car.
	//---------------------------------------

	void set( const char * ch )
	{
		delete [] string;			//La chaîne sera sûrement de taille != 

		len = strlen( ch );
		if ( string = new char[ len + 1 ] )		//Ré-allocation.
			strcpy( string, ch );
		else
			exit(1);
	}

	//-----------------------------------
	//Surcharge d'opérateur pour copie
	//-----------------------------------
	Strg & operator =( const Strg & op2 );

	//----------------------------------------
	//Surchrage d'opérateur pour concaténation
	//----------------------------------------
	Strg  operator +( const Strg & op2 );

	//--------------------------------------------
	//Surcharge d'opérateur pour test d'égalité ==
	//---------------------------------------------
	int operator ==( const Strg & op2 );

	//------------------------------
	//Surcharge d'opérateur pour <=
	//-------------------------------
	int operator <=( const Strg & op2 );

	//--------------------------------
	//Surcharge d'opérateur pour >=*
	//--------------------------------
	int operator >=( const Strg & op2 );

	//-----------------------------
	//Surchrage d'opérateur pour >
	//-----------------------------
	int operator >( const Strg & op2 );

	//-----------------------------
	//Surchrage d'opérateur pour <
	//-----------------------------
	int operator <( const Strg & op2 );

	//----------------------------------------------
	//Surcharge des crochets [] pour accès à un car.
	//----------------------------------------------
	char & operator []( const int & index );

	//---------------------------------
	// +=
	//---------------------------------
	void operator += ( const Strg op );

	//--------------------------------------------------------------
	friend ostream & operator <<( ostream & out, const Strg & op );

	friend istream & operator >>( istream & in, Strg & op );
	//--------------------------------------------------------------

	//----------------------
	//Constructeur de copie
	//----------------------
	Strg( const Strg & src )		//Appelé lorsque : - passage par valeur;
	{												// - Strg s4(s1).
		
		if ((string = new char[ strlen( src.string) + 1 ]) != 0 )
		{
			strcpy( string, src.string );
			len = strlen( src.string);
			occurences = 1;
		}
		else
			exit (1);
	}

	//---------------------------------------------
	//Constructeur de conversion de STRG en CHAR *
	//---------------------------------------------
	operator char * () const			//Ne modifie rien !
	{
		return string;					//Pas de type de retour, comme constructeur,
	}									//Mais renvoi quan même (!) de qqchose.

};




#endif



/************************************************************************\
 * FICHIER: arbre_nikko_main.cpp
 * N.P. 18/04/02 (12:46:42)
 * OBJET:
 * 	Exemple d'utilisation d'un arbre binaire
 * NOTES:
 *  
 *		Un fichier est demandé pour une analyse lexicale.
 *		A la fin l'arbre est lu et affiché sous forme de nombre
 *		d'occurences ( répétitions ).
 *
 *		L'arbre binaire est un moyen efficace et rapide pour traiter
 *		un grand nombre de données. Son point le plus fort réside dans 
 *		le fait que les données sont pré-triées étant donné la façon
 *		de ranger les données dedans !
 *
 *
 *		Point intérressant: les données contenues dans les feuilles de
 *		l'arbre binaire sont des objets de la classe Strg ( String ).
 *		A méditer ! ;-)
 *
\************************************************************************/


#include <ctype.h>
#include <stdlib.h>
#include <fstream.h>			//Pour accès E/S aux fichiers
#include <iostream.h>

#include "string_nikko.h"
#include "arbre_nikko.h"




void main()
{
	Strg filename;
	cout << "Utilisation d'un arbre binaire pour analyse lexicale." << "\n\n";
	system( "dir/w" );
	cout << endl << "Choisissez un fichier à analyser: ";
	cin >> filename;


	//Lecture du fichier afin de trouver les mots:
	Arbre sapin;
	Strg mot;
	char car = 0;

	//ouverture du fichier:
	fstream f1;
	f1.open( filename.show(), ios::in );

	while ( !f1.eof() )
	{
		f1.read( &car, sizeof( char ) );
		
		if ((( car == ' ' ) || ( car == '\n' )) && ( mot[ 0 ] != '\0' ))
		{
			//Insertion du mot trouvé dans un arbre
			cout << mot << "|| ";
			sapin.AddNode( mot );
			mot.set( "" );		//On repart pour un nouveau mot.
		}
		else if ( isalpha( car ) )
			mot += Strg( car );
	}

	//Fermeture du fichier:
	f1.close();

	//Affichage de l'arbre:
	cout << "Fichier parcouru.Apercu de l'arbre:\n\n";
	sapin.Afficher( sapin.ptr_r );

}	



/**********************************************************************
*
* Fichier arbre_nikko_defs.cpp
*
* Contient les définitions de la classe Arbre
*
**********************************************************************/
 
//----------------------------------------------------
// Définitions des fonctions membres des deux classes:
//----------------------------------------------------

#include "arbre_nikko.h"
#include "string_nikko.h"

#include <iostream.h>
#include <string.h>


//-------------------
// Ajouter un noeud
//-------------------
bool Arbre::AddNode( Strg & donnee )
{
	if ( ptr_r == 0 )
	{
		//Si arbre sans branches...
		ptr_r = new Noeud;	//...en voici une !
		ptr_r->data_in = donnee;
	}
	else
	{
		Noeud * tmp = ptr_r;
		Noeud * n_parent;
		
		do		//Recherche d'une feuille.
		{
			n_parent = tmp;
			
			if ( donnee == tmp->data_in )
			{
				//On a trouvé la donnée dans l'arbre:
				tmp->data_in.occurences++;
				return true;				
			}
			else if ( donnee < tmp->data_in )
				tmp = tmp->n_g;		//On chope l'adr du noeud futur papa
			else
				tmp = tmp->n_d;		//On chope l'adr du noeud futur papa
			
		}
		while ( tmp );
		
		//Maintenant, il faut créer ce nouveau noeud:
		if ( donnee < n_parent->data_in )
		{
			n_parent->n_g = new Noeud;
			n_parent->n_g->data_in = donnee;
		}
		else
		{
			n_parent->n_d = new Noeud;
			n_parent->n_d->data_in = donnee;
		}
		
	}
	
	return true;
}


//------------------
// Gicler un noeud
//------------------
bool Arbre::RemoveNode( Strg & donnee )
{
	if ( ptr_r == 0)
		return false;	//On ne coupe pas l'arbre !
	
	Noeud * tmp = ptr_r;
	Noeud * n_parent = ptr_r;
	
	//Parcours de l'arbre à la recherche de la valeur à trouver:
	while ( tmp && ( donnee != tmp->data_in ) )
	{
		n_parent = tmp;
		if ( donnee <= tmp->data_in )
			tmp = tmp->n_g;
		else
			tmp = tmp->n_d;
		
		if ( tmp == 0 )
			return false;	//La valeur n'y était pas !
	}
	//Cas facile: il était célibataire:
	if (!tmp->n_g && !tmp->n_d )
	{
		//IL est d*le noeud g ou d de son père ?
		if ( n_parent->n_g == tmp )
		{
			//..le noeud gauche va mourrir.
			delete n_parent->n_g;
			n_parent->n_g = 0;
		}
		else
		{
			//...le noeud droit va mourrir.
			delete n_parent->n_d;
			n_parent->n_d = 0;
		}
	}
	//Cas difficile: deux gosses à charge:	
	else if ( tmp->n_g && tmp->n_d )
	{
		Noeud * tampon = tmp;
		
		//On regarde du côté du fils droit du 'zombie'.
		tmp = tmp->n_d;
		
		//Recherche jusqu'au bout de ce côté:
		while ( tmp->n_g )
		{
			n_parent = tmp;
			tmp = tmp->n_g;
		}
		
		//Le fils droit n'a pas de noeaud à sa gauche?
		if ( tampon->n_d == tmp )
		{
			tampon->data_in = tmp->data_in;
			tampon->n_d = tmp->n_d;
			delete tmp;
		}
		else
		{
			//Le fils gauche n'a pas de descendance?
			tampon->data_in = tmp->data_in;
			n_parent->n_g = tmp->n_d;
			delete tmp;
		}
		
	}
	//Cas medium: un noeud fils: d ou g ?
	else if ( tmp->n_g )
		n_parent = tmp->n_g;
	else
		n_parent = tmp->n_d;
	
	tmp->data_in = n_parent->data_in;
	tmp->n_d = n_parent->n_d;
	tmp->n_g = n_parent->n_g;
	
	
	//TODO
	return true;
}





//---------------------------------------
// Parcours de l'arbre à la recherche de
// la donnée à trouver:
//---------------------------------------
Noeud * Arbre::Wanted( Strg donnee )
{
	Noeud * tmp;
	
	//Parcours de l'arbre:
	while ( tmp && ( donnee != tmp->data_in ) )
	{
		if ( donnee < tmp->data_in )
			tmp = tmp->n_g;
		else
			tmp = tmp->n_d;
		
		if ( tmp == 0 )
			return 0;	//La valeur n'y était pas !
	}

	return tmp;
}



//---------------------------------------------------
// Affichage de l'arbre: départ au fond à gauche,
// puis on remonte à la recine et on fait pareil à d.
//---------------------------------------------------
void Arbre::Afficher( Noeud * org )
{
	if ( org == 0 )
		return;
	
	Afficher( org->n_g );
	cout << "Mot: " << org->data_in << "\tOccurences : " << org->data_in.occurences << endl;
	Afficher( org->n_d );
}


/*********************************************************************
*
* Fichier arbre_nikko.h
*
*********************************************************************/

//------------------------------------------
// Fichier d'en-tête contenant les classes
//------------------------------------------


#include "string_nikko.h"


#ifndef ARBRE_NIKKO_H
#define ARBRE_H


const short LG_MOT_MAX = 50;			//Pour les mots

//----------------------
// Classe de base Noeud
//----------------------
class Noeud
{
	//Pour lire tout les noeuds avec la classe Arbre.
	friend class Arbre;

public:

	Noeud( Noeud * ng = 0, Noeud * nd = 0, Strg done = "" )
	{
		//Constructeur:
		n_g = ng;
		n_d = nd;
		data_in = done;		//Le constructeur Strg met une chaîne vide par défaut.
	}



protected:

	Noeud * n_g;
	Noeud * n_d;
	Strg data_in;

};



//----------------------
// Classe dérivée Arbre
//----------------------
// Elle hérite de deux pointeurs de noeud: n_g et n_d
class Arbre : private Noeud
{
public:
	
	Arbre( Noeud * r = 0, Noeud * g = 0, Noeud * d = 0 )
	{
		ptr_r = r;
		n_g = g;
		n_d = d;
	}

	void Arbre::Afficher( Noeud * org );
	bool AddNode( Strg & );
	bool RemoveNode( Strg & );
	Noeud * Wanted( Strg donnee );
	Noeud * ptr_r;
};



#endif