Strcuture d'arbre n-aire

Télécharger le projet
Commenter

Description

Ce source permet de créer un arbre n-aire.

Source / Exemple : 


/*


     
  • 		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();
}

Conclusion :


Une version générique de la classe Noeud est à l'étude...
Je planche également sur une structure de graphe ce qui permettrait de faire des arbres et d'autres objets mathématiques inétressants.
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (jeanlandercy)