Soyez le premier à donner votre avis sur cette source.
Snippet vu 13 782 fois - Téléchargée 36 fois
#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); }
Le code est bien fait.
* 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.