Parcurgere arbore

Rezolvarea problemelor de matematica prin realizarea unor programe.
ElenaIulia
utilizator
utilizator
Mesaje: 77
Membru din: 25 Oct 2010, 20:52

Parcurgere arbore

Mesaj de ElenaIulia » 10 Apr 2011, 21:00

Am o problema daca ma poate ajuta cineva: o alocare dinamica a unui arbore (care nu este binar) si o parcurgere a acestuia in latime in C++.... Am incercat eu cumva, dar la clasa mi s-a spus ca rezolvarea e cam slabuta si ca se poate face mult mai frumos... culmea e ca rezolvarea era luata din manualul de informatica... in fine nu orice ne e dat ca sa il luam de bun...
Daca ma poate ajuta cineva ar fi perfect ca nu ma prea descurc... Multumesc!

morpheus
utilizator
utilizator
Mesaje: 25
Membru din: 09 Feb 2011, 19:44
Contact:

Re: Parcurgere arbore

Mesaj de morpheus » 11 Apr 2011, 00:54

Faptul ca in manuale, uneori, se intampla sa nu avem implementari corecte de cod C++, nu ma mira deloc.
Arata ce ai facut ... posteaza codul pe care l-ai prezentat (sau explica cum ai avut de gand sa faci, daca nu ai cod), ca sa discutam.
Sunt sigur ca vom ajunge la o implementare decenta in C++.

ElenaIulia
utilizator
utilizator
Mesaje: 77
Membru din: 25 Oct 2010, 20:52

Mesaj de ElenaIulia » 11 Apr 2011, 10:35

Rezolvarea pe care am gasit-o in manual e asta, dar mi s-a spus ca nu e prea eficienta, ca arborele ar trebui alocat dinamic.
#include < iostream.h>
int t[20], n, c[20], prim, ultim;
void citire( ){
cout<<"Dati numarul de noduri ale arborelui de parcurs: ";
cin >>n;
for( int i=1;i<=n;i++ ){
cout<<"Dati nodul tata al nodului "<< i<<" : ";
cin>>t;
}
}
int rad ( ){
for( int i=1; i<=n; i++)
if( t==0 ) return i;
return 0;
}// se determina nodul radacina r al arborelui
void init( int k ){
prim=ultim=1;
c[ultim]=k;
}//intializeaza coada de asteptare cu radacina
int este_vida ( ){
return ultim< prim;
}//testeaza coada de asteptare daca este vida
void adauga ( int i ){
ultim++;
c[ultim]=i;
}//adauga un nod la coada de astepare
void elimina ( ){
prim++;
}
void prelucrare ( ){
int r=c[prim];
for ( int i=1; i<=n;i++ )
if ( t==r ) adauga (i);
elimina( );
}//prelucreaza primul nod din coada: adauga la coada de asteptare toti fiii acestui nod si apoi il elimina din coada de asteptare
void afisare( ){
cout<<"Arborele parcurs in latime este: ";
for ( int i=1; i<=n; i++ )
cout<< c<<" ";
}
int main ( ){
int r;
citire ( );
r=rad ( );
init (r);
while (!este_vida ( ))
prelucrare ( );
afisare ( );

}

morpheus
utilizator
utilizator
Mesaje: 25
Membru din: 09 Feb 2011, 19:44
Contact:

Mesaj de morpheus » 11 Apr 2011, 16:03

Ca sa implementezi un arbore in C++, in mod normal ar trebui sa faci o clasa template pentru arbore si un iterator care parcurge arborele.
Ai aici o implementare de arbore: http://tree.phi-sci.com/download.html
Acolo e o implementare completa, tie, in principiu nu iti trebuie tot ... doar uitat-te in fisierul tree.hh la:
- felul in care e declarata clasa tree_node_
- felul in care e declarata clasa tree, felul in care sunt implementati constructorii, destructorul si felul in care sunt supraincarcati operatorii
- ai nevoie si de iterator_base si breadth_first_queued_iterator
- clasa breadth_first_queued_iterator e de interes maxim. E iteratorul folosit pentru a parcurge containerul in latime, fii atenta cum e implementat, asta e ceea ce iti trebuie.

Daca ai probleme cu implementarea pe baza modelului propus, posteaza.

ElenaIulia
utilizator
utilizator
Mesaje: 77
Membru din: 25 Oct 2010, 20:52

Mesaj de ElenaIulia » 11 Apr 2011, 18:33

Ok.... multumesc mult pentru timpul alocat pentru a ma ajuta. Voi studia cele indicate si sper sa ma descurc... Multumesc inca o data!

Scrie răspuns