Parcours itératif d'un arbre ternaire
Soyez le premier à donner votre avis sur cette source.
Snippet vu 14 175 fois - Téléchargée 38 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.
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
- Itérativement
- Algorithme ternaire - Meilleures réponses
- Parcours itératif arbre binaire - Meilleures réponses
- Fibonacci python iterative - Guide
- Tri fusion itératif - Forum - C / C++ / C++.NET
- Utiliser les itérateurs en php5 - Conseils pratiques - PHP
- C / C++ / C++.NET : Fonction itérative(très rapide) pour trouver le pgcd et le ppcm - Guide
- Java : Programme hannoi itératif. - CodeS SourceS - Guide
- Messages postés
-
527
- Date d'inscription
- vendredi 14 septembre 2001
- Statut
- Membre
- Dernière intervention
- 6 octobre 2008
422 avril 2002 à 15:09
Le code est bien fait.
20 avril 2002 à 19:29
* Facilement updatable. (Arbre n-aire)
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.