STRCUTURE D'ARBRE N-AIRE

/*
 *		Sujet:		Structure d'arbre n-aire
 *		Version:		1.0
 *		Màj:			21.02.2004
 *		Auteur:		LANDERCY Jean
 *		e-mail:		dr.degree@caramail.com
 *		Site Web:	http://endorphin.imb.free.fr/
 */

class Noeud;

typedef Noeud * pNoeud;
typedef pNoeud * ppNoeud;

const pNoeud pN_NULL=0;
const ppNoeud ppN_NULL=0;

// Classe Noeud:
class Noeud {

	private:

		// Informations du noeud:
		int Niveau;					// Niveau du noeud
		int nbSuccesseurs;		// Nombre de noeuds enfants

		// Méthodes privées:
		
		void Calculer_Niveau();	// Mutateur descendant

		// Gestion dynamique des adresses des noeuds enfants:
		void Initialiser_Successeurs(int _nbSuccesseurs);
		void Supprimer_Successeurs();

	public:
		
		// Liens:		
		pNoeud Predecesseur;		// Pointe le noeud parent
		ppNoeud Successeurs;		// Pointe vers le tableau des noeuds enfants

		// Constructeur:		
		Noeud() {
			Niveau=0;
			nbSuccesseurs=0;
			Predecesseur=pN_NULL;
			Successeurs=ppN_NULL;
		}
		
		// Destructeur:
		~Noeud() {
			Supprimer_Noeuds_Successeurs(); // Appel récurssif de la méthode!
		}
		
		// Méthodes associées:

		// Mutateurs:
		void Definir_Niveau(int _Niveau);
		void Definir_nbSuccesseurs(int _nbSuccesseurs);
		
		// Accesseurs:
		int Lire_Niveau() const;
		int Lire_nbSuccesseurs() const;

		// Affichage:
		void Afficher_Noeud();
		void Afficher_Arbre();

		// Gestion des noeuds enfants:
		void Creer_Noeuds_Successeurs(int _nbSuccesseurs);
		void Supprimer_Noeuds_Successeurs();
		
};

// Méthodes déportées de la classe Noeud:

// Définit le niveau du noeud:
void Noeud::Definir_Niveau(int _Niveau) {
	Niveau=_Niveau;
}

// Retourne le niveau du noeud:
int Noeud::Lire_Niveau() const {
	return Niveau;
}

// Calcule le niveau d'un noeud dans l'arbre: (méthode descendante)
void Noeud::Calculer_Niveau() {
	if(Predecesseur!=pN_NULL) {
		Niveau=Predecesseur->Niveau+1;
	} else {
		Niveau=0;
	}
}

// Définit le nombre de noeuds enfants:
void Noeud::Definir_nbSuccesseurs(int _nbSuccesseurs) {
	nbSuccesseurs=_nbSuccesseurs;
}

// Retourne le nombre de noeuds enfants:
int Noeud::Lire_nbSuccesseurs() const {
	return nbSuccesseurs;
}


// Affiche nbCar fois le caractère Car:
void Barre(char Car, int nbCar) {
	for(int i=0; i<nbCar; i++) {
		cout << Car;
	}
}

// Affiche le noeud:
void Noeud::Afficher_Noeud() {
	Barre(' ',2*Niveau);
	cout << "+ Noeud (" << this << ") :" << endl;
/*	Barre(' ',2*Niveau);
	cout << "  - Niveau = " << Niveau << endl;
	Barre(' ',2*Niveau);
	cout << "  - nbSuccesseurs = " << nbSuccesseurs << endl;
	Barre(' ',2*Niveau);
	cout << "  - Predecesseur = " << Predecesseur << endl;
	Barre(' ',2*Niveau);
	cout << "  - Successeurs[" << nbSuccesseurs  << "] = { ";
	for(int i=0; i<nbSuccesseurs; i++) {
		if(i>0) {
			cout << ", ";
		}
		cout << Successeurs[i];
	}
	cout << " }" << endl;
	cout << endl;*/
}

// Affiche le noeud et le sous-arbre découlant du noeud: (méthode récursive!)
void Noeud::Afficher_Arbre() {
	Afficher_Noeud();
	for(int i=0; i<nbSuccesseurs; i++) {
		Successeurs[i]->Afficher_Arbre();
	}
}

// Initialise le tableau des successeurs pour  n noeuds enfants: (supprime les noeuds enfants existants)
void Noeud::Initialiser_Successeurs(int _nbSuccesseurs) {
	if(Successeurs!=ppN_NULL) {
		Supprimer_Noeuds_Successeurs();
	}
	nbSuccesseurs=_nbSuccesseurs;
	Successeurs = new pNoeud[nbSuccesseurs];
}

// Supprime le tableau des successeurs: (ne supprime pas les noeuds enfants)
void Noeud::Supprimer_Successeurs() {
	if(Successeurs!=ppN_NULL) {
		delete [] Successeurs;
	}
	nbSuccesseurs=0;
	Successeurs=ppN_NULL;
}

// Crée n noeuds enfants au noeud courant:
void Noeud::Creer_Noeuds_Successeurs(int _nbSuccesseurs) {
	Initialiser_Successeurs(_nbSuccesseurs);
	for(int i=0; i<_nbSuccesseurs; i++) {
		Successeurs[i] = new Noeud;
		Successeurs[i]->Predecesseur=this;
		Successeurs[i]->Calculer_Niveau();
	}
}

// Supprime les noeuds enfants du noeud courant: (méthode récursive! cf.: déstructeur de la classe Noeud)
// Cette méthode supprime le sous-arbre de noeuds découlant du noeud courant
void Noeud::Supprimer_Noeuds_Successeurs() {
	for(int i=0; i<nbSuccesseurs; i++) {
		delete Successeurs[i];	// Lors de la destruction d'un noeud, cette fonction est appellée par le déstructeur du noeud
	}
	Supprimer_Successeurs();
}