begin process at 2008 07 19 16:42:05
1 212 905 membres
227 nouveaux aujourd'hui
14 165 membres club

Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum.
Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

PARCOURS ITÉRATIF D'UN ARBRE TERNAIRE


Information sur la source

Catégorie :Maths & Algorithmes Niveau : Débutant Date de création : 20/04/2002 Date de mise à jour : 20/04/2002 19:15:23 Vu : 5 915

Note :
9 / 10 - par 2 personnes
9,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10

Commentaire sur cette source (2)
Ajouter un commentaire et/ou une note

Description

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

  • #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);
  • }
#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);
	
}
 
  • signaler à un administrateur
    Commentaire de Peak le 20/04/2002 19:29:22

    * Bien optimisé.
    * Facilement updatable. (Arbre n-aire)

  • signaler à un administrateur
    Commentaire de GoldenEye le 22/04/2002 15:09:45

    Bravo. Le parcours d'un arbre  n-aire est évident en récursif mais pas en itératif.
    Le code est bien fait.

Ajouter un commentaire

Pub



Appels d'offres

Dessins techniques
Budget : 60€
Animation Flash - Doma...
Budget : 370€
Application flash medi...
Budget : 1 000€

CalendriCode

Juillet 2008
LMMJVSD
 123456
78910111213
14151617181920
21222324252627
28293031   

VS Express FR Gratuit !

VS Express en français et 100% gratuit !

Boutique

Boutique de goodies CodeS-SourceS