Parcours itératif d'un arbre ternaire

Soyez le premier à donner votre avis sur cette source.

Snippet vu 13 315 fois - Téléchargée 36 fois

Contenu du snippet

Ben c un parcours d'un arbre ,itérativement.C'est tout a fait inutile Mais ca peut aider
pour bien comprendre le fonctionnement de ce type de structure.

Source / Exemple :


#include <iostream.h>
#include <stdlib.h>
template <class Elem>
class Arbre2 {//Classe Arbre 2 Modifiée

	class Noeud {
		friend class Arbre2<Elem>;
		Elem info;
		Noeud *pere,*fg,*fd,*fm;//Nouveau pointeur fm (fils median) 
		Noeud (const Elem& E,Noeud *P=NULL,Noeud* G=NULL,Noeud *D=NULL,Noeud *M=NULL):
		info(E),pere(P),fg(G),fd(D),fm(M) {}
		//également initialiser a NULL
	};
	public:
		typedef Noeud *Place;
	private:
		Place rac;
		inline static Place Copy (Place ,Place = NULL);
		inline static void Cancel (Place&);
	public:
		bool Existe (Place p) const				{return p;}
		Place Rac () const						{return rac;}
		Place Pere (Place p) const				{return p->pere;} 
		Place FilsG (Place p) const				{return p->fg;}
		Place FilsM (Place p) const				{return p->fm;}
		// Fct FilsM 
		
		Place FilsD (Place p) const				{return p->fd;}
		Elem & operator[] (Place p)				{return p->info;}
		void InsG (const Elem &E, Place p)		{Cancel (p->fg); p->fg = new Noeud(E,p);}
		void InsM (const Elem &E, Place p)		{Cancel (p->fm); p->fm = new Noeud(E,p);}
		//Fct InsM
		void InsD (const Elem &E, Place p)		{Cancel (p->fd); p->fd = new Noeud(E,p);}
		void InsG (const Arbre2& A,Place p)     {Cancel (p->fg); p->fg = Copy(A.rac,p);}
		void InsM (const Arbre2& A,Place p)     {Cancel (p->fm); p->fm = Copy(A.rac,p);}
			//Fct InsM
		void InsD (const Arbre2& A,Place p)     {Cancel (p->fd); p->fd = Copy(A.rac,p);}
		void SupG (Place p)						{Cancel (p->fg);}
		void SupM (Place p)						{Cancel (p->fm);}
		void SupD (Place p)						{Cancel (p->fd);}
		//Constructeurs
		Arbre2 (const Elem& E): rac(new Noeud(E)) {}
		Arbre2 (): rac(NULL) {}
		Arbre2 (const Arbre2&,Place p): rac(Copy(p)) {}
		Arbre2 (const Arbre2& A): rac(Copy(A.rac)) {}
		const Arbre2& operator = (const Arbre2 &A ) {
			if (this != |A) {Cancel (rac);rac = Copy(A.rac);}
			return *this;

		}
		~Arbre2 () { Cancel (rac);}
};

	template <class Elem>
	 Arbre2<Elem>::Place Arbre2<Elem>::Copy(Place s,Place p) {

	Place f = NULL;
	if (s) {
		f = new Noeud (s->info,p);
		f->fg = Copy(s->fg, f);
		f->fm = Copy(s->fm, f);
		//modif
		f->fd = Copy(s->fd, f);
	}return f;
	}
	template<class Elem>
	void Arbre2<Elem>::Cancel (Place &p) {
	if (p) {
		Cancel(p->fg);
		Cancel(p->fm);
		//modif
		Cancel(p->fd);
		delete p; p = NULL;
		}
	}
void Traiter (Arbre2<int> & A,Arbre2<int>::Place p)
{
		cout<< A[p] <<"->";
}

//parcour ternaire preordre
void ParcourPRE(Arbre2<int> Arbre)
{
	bool Fin=false,bool1;
	Arbre2<int>:: Place tmp=Arbre.Rac();
	do
	{
		Traiter(Arbre,tmp);//on traite l'elem en cours
			//a commencer par la racine.
		while( Arbre.FilsG(tmp) || Arbre.FilsM(tmp)|| Arbre.FilsD(tmp))
		{
			while(Arbre.FilsG(tmp))
			{
				//tant que y as des FilsG on descend ds l'arbre.
				tmp=Arbre.FilsG(tmp);
				//et on traite chaque Elem 
				Traiter(Arbre, tmp);
			}
			if(Arbre.FilsM(tmp))
			{
				//si on trouve un FilsM en descendant dans l'arbre
				tmp=Arbre.FilsM(tmp);
				//on le tarite
				Traiter(Arbre, tmp);
			}
			if(Arbre.FilsD(tmp))
			{
				//si on trouve un FilsD en descendant dans l'arbre
				tmp=Arbre.FilsD(tmp);
				Traiter(Arbre, tmp);
			}
		}
		bool1=false;
		while( Arbre.Pere(tmp) && !bool1 )
		{
			if(Arbre.FilsG(Arbre.Pere(tmp))==tmp)
			{
				if(Arbre.FilsM(Arbre.Pere(tmp)))
				{ 
					//Avant de remonter :
					//si y as un FilsM on pointe dessus
					//Et on sort de ce while pour recommencer
					//une iteration du while(!Fin) si on doit.
					tmp=Arbre.FilsM(Arbre.Pere(tmp)); 
					bool1=true;
					
				}
				else if(Arbre.FilsD(Arbre.Pere(tmp)))
				{ 
					//Avant de remonter :
					//si y as un FilsD on pointe dessus
					//Et on sort de ce while pour recommencer
					//une iteration du while(!Fin) si on doit
					tmp=Arbre.FilsD(Arbre.Pere(tmp)); 
					bool1=true; 
				}else 
				{
					//sinon on remonte seulement
					tmp=Arbre.Pere(tmp);
				}
			}	
			else if(Arbre.FilsM(Arbre.Pere(tmp))==tmp)
			{
				if(Arbre.FilsD(Arbre.Pere(tmp)))
				{ 
					//Avant de remonter :
					//si y as un FilsD on pointe dessus
					//Et on sort de ce while pour recommencer
					//une iteration du while(!Fin) si on doit
					tmp=Arbre.FilsD(Arbre.Pere(tmp)); 
					bool1=true; 
				}
				else 
				{
					//sinon on remonte seulement
					tmp=Arbre.Pere(tmp);
				}
			}
			else 
			{
				tmp=Arbre.Pere(tmp);
			}
		}
		if(!Arbre.Pere(tmp))
		{
			cout<<"*";
			Fin=true;
		}
	}
	while(!Fin);
}

//parcour ternaire postordre
void ParcourPOST(Arbre2<int> Arbre)
{
	bool Fin=false,bool1 = true;
	Arbre2<int>:: Place tmp=Arbre.Rac();
	do
	{
		
		if( Arbre.FilsG(tmp) || Arbre.FilsM(tmp) || Arbre.FilsD(tmp) )
		{
			while(Arbre.FilsG(tmp))//tant(ou si) qu'il existe un Fils Gauche
			{//on parcours la premiere branche gauche
				//raison du while
				tmp=Arbre.FilsG(tmp);
			}
			if(Arbre.FilsM(tmp))//Si il existe un filsM
			{//on passe a ce filsM
				tmp=Arbre.FilsM(tmp);
			}
			if(Arbre.FilsD(tmp))//Si il existe un filsM
			{
				tmp=Arbre.FilsD(tmp);//on passe a ce filsM
			}
		}
		// ici on est forcément dans un cas ou il n'y pas de fils
		Traiter(Arbre, tmp);//donc on traite l'elem en cours.
		bool1 = false;
		while( Arbre.Pere(tmp) && !bool1)
		{
			if(Arbre.FilsG(Arbre.Pere(tmp))==tmp)
			{
				if(Arbre.FilsM(Arbre.Pere(tmp)))
				{ 
					//si un filsM existe : on y va
					tmp=Arbre.FilsM(Arbre.Pere(tmp)); 
					bool1=true;
					
				}
				else if(Arbre.FilsD(Arbre.Pere(tmp)))
				{ 
					//si un filsD existe : on y va
					tmp=Arbre.FilsD(Arbre.Pere(tmp)); 
					bool1=true; 
				}
				else 
				{	
					tmp=Arbre.Pere(tmp);
					//si on remonte on doit traiter l'elem en cours
					Traiter(Arbre,tmp);
				}
			
			}	
			else if(Arbre.FilsM(Arbre.Pere(tmp))==tmp)
			{
				if(Arbre.FilsD(Arbre.Pere(tmp)))	
				{ 
					//si un filsD existe : on y va
					tmp=Arbre.FilsD(Arbre.Pere(tmp)); bool1=true; 
				}
				else 
				{
					tmp=Arbre.Pere(tmp);
					//si on remonte on doit traiter l'elem en cours
					Traiter(Arbre,tmp);
				}
			}
			else if(Arbre.FilsD(Arbre.Pere(tmp))==tmp)
			{ 
				tmp=Arbre.Pere(tmp);
				//si on remonte on doit traiter l'elem en cours
				Traiter(Arbre,tmp);
			}
		}
		if(!Arbre.Pere(tmp)) 
		{
			cout<<"*";
			Fin=true;
		}
	}
	while(!Fin);
}

void main()
{
	bool fin = false,deux = false;int a=0;
	//Declaration
	Arbre2<int> A(13);

	//remplissage de l'arbre
	A.InsG(4, A.Rac());
	A.InsM(8, A.Rac());
	A.InsD(12, A.Rac());
	A.InsG(1, A.FilsG(A.Rac()));
	A.InsM(2, A.FilsG(A.Rac()));
	A.InsD(3, A.FilsG(A.Rac()));
	A.InsG(5, A.FilsM(A.Rac()));
	A.InsM(6, A.FilsM(A.Rac()));
	A.InsD(7, A.FilsM(A.Rac()));
	A.InsG(9, A.FilsD(A.Rac()));
	A.InsM(10, A.FilsD(A.Rac()));
	A.InsD(11, A.FilsD(A.Rac()));
	ParcourPRE(A);
	cout<<endl;
	ParcourPOST(A);
	
}

A voir également

Ajouter un commentaire

Commentaires

cs_Peak
Messages postés
7
Date d'inscription
samedi 20 avril 2002
Statut
Membre
Dernière intervention
27 octobre 2003
-
* Bien optimisé.
* Facilement updatable. (Arbre n-aire)
cs_GoldenEye
Messages postés
527
Date d'inscription
vendredi 14 septembre 2001
Statut
Membre
Dernière intervention
6 octobre 2008
2 -
Bravo. Le parcours d'un arbre n-aire est évident en récursif mais pas en itératif.
Le code est bien fait.

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.