PARCOURS ITÉRATIF D'UN ARBRE TERNAIRE , Source N°9652

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

Auteur : Nico5779

Site perso

Ecrire un message privé

Note :

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

Sources de la même categorie

Toutes les sources de la catégorie Maths & Algorithmes

Commentaires

Commentaire de Peak le 20/04/2002 19:29:22

* Bien optimisé.
* Facilement updatable. (Arbre n-aire)
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.