C / C++ / C++.NET : Parcours itératif d'un arbre ternaire

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