CodeS-SourceS est hébergé par Frontier.fr

Ce site au démarrage

begin process at 2012 02 12 13:04:27

Accueil Codes Tutoriels Forum Livres Emploi Services Connexion

Trouver un code source :

dans

[ Dernières recherches ]

Accueil >

Code

Maths & Algorithmes

> PARCOURS ITÉRATIF D'UN ARBRE TERNAIRE

PARCOURS ITÉRATIF D'UN ARBRE TERNAIRE

Information sur la source

Note :

9,00 / 10

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 :10 387

Auteur : Nico5779

Ecrire un message privé

Site perso

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

UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras

CHIFFREMENT DE VIGENERE par lajouad

ANALYSE SYNTAXIQUE par lajouad

STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel

DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel

Toutes les sources de la catégorie Maths & Algorithmes

Commentaires et avis

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.

Ajouter un commentaire

Nos sponsors

Derniers Blogs

SESSION SILVERLIGHT 5 3D : SLIDES ET DEMOS par Groc

[TECHDAYS 2012] SESSION WEBMATRIX 2 : LE COUTEAU SUISSE GRATUIT POUR VOS DéVELOPPEMENTS WEB - SLIDES par gpommier

[SHAREPOINT] LES SESSIONS TECHDAYS 2012. par Patrick Guimonet

TECHDAYS PARIS 2012 : SESSION PLEINIèRE JOUR 3 par ROMELARD Fabrice

MISHRA READER : UN LECTEUR RSS TRèS ZUNE STYLE EN OPEN SOURCE ! par Vko

Forum

RE : INVERSER UNE CHAîNE DE CARACTèRES LANGAGE C+ par Renfield

RE : EXCEPTIONS par rt15

RE : [QT]JEUX SIMILAIRE à ZELDA EN MULTIJOUEUR par Neckara

RE : çA COMPILE SUR DEV ET çA MARCHE PAS SUR CODEBLOCKS par rt15

RE : C DUP UTILISATION par rt15

Côté IT

Offres d'emploi

Formations Video

Appels d'offres

Passerelle Pericles sur site Joomla 17
Budget : 499€
Infogerance Serveur Debian Linux
Budget : 2 400€
Developpeur applications iphone - ipad - android
Budget : 800€

Logiciels

Tribler (2012)
TRIBLER (2012)

Tribler est un client pair à pair (P2P/Peer-to-Peer) open source avec la capacité de regarder des...

Cliquez pour télécharger Tribler
OneSwarm (2012)
ONESWARM (2012)

Le peer-to-peer qui protège votre vie privée, c'est OneSwarm. Ce logiciel de peer-to-peer crypté...

Cliquez pour télécharger OneSwarm
PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V8.4)
PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V8.4)

PONAMEDIA TV DEVIENS HELLLOOO FLASH LA TV SUR VOTRE ORDINATEUR. Toute une plateforme Multi...

Cliquez pour télécharger PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO
Academy System (17.2.1.0)
ACADEMY SYSTEM (17.2.1.0)

Logiciel de gestion des établissements. - élèves/étudiants (inscription, dossier, absence...) -...

Cliquez pour télécharger Academy System
Easy-Planning (1.0.0.1)
EASY-PLANNING (1.0.0.1)

Basé sur les mêmes principes que MyPlanning, Easy-Planning permet de créer des plannings sous la ...

Cliquez pour télécharger Easy-Planning