![]() |
![]() |
|
Programiranje Programski jezici, tehnike, alatke... |
![]() |
|
Alatke vezane za temu | Vrste prikaza |
![]() |
#1 |
Starosedelac
Član od: 5.12.2005.
Lokacija: Niš
Poruke: 1.259
Zahvalnice: 49
Zahvaljeno 154 puta na 115 poruka
|
![]()
Potreban mi je algoritam/pseudo-kod/C++ kod koji prolazi (jednom) kroz sve čvorove dinamičkog (tj, realizovanog uz pomoć lančanih lista) binarnog stabla. Hvala unapred.
![]() |
![]() |
![]() |
![]() |
#2 |
Član
Član od: 15.12.2010.
Lokacija: Beograd
Poruke: 120
Zahvalnice: 26
Zahvaljeno 39 puta na 32 poruka
|
![]()
Ne znam da li sam te dobro razumeo ali meni izgleda da ovde treba samo rekurzija.
pozoveš funkciju Prolazak() i predaš joj prvi čvor kao argument. Prolazak(čvor) { ako čvor ima levo dete pozovi Prolazak(levo_dete) ako čvor ima desno dete pozovi Prolazak(desno_dete) return} tako se prolazi kroz sve elemente binarnog stabla. |
![]() |
![]() |
![]() |
#3 |
Član
Član od: 30.10.2005.
Lokacija: Vancouver, BC
Poruke: 475
Zahvalnice: 48
Zahvaljeno 95 puta na 75 poruka
|
![]()
Samo treba obratiti paznju na slucaj kada je stablo prazno, posto ce u tom slucaju pri prvom pozivu dobiti null pointer exception.
|
![]() |
![]() |
![]() |
#4 |
Starosedelac
Član od: 5.12.2005.
Lokacija: Niš
Poruke: 1.259
Zahvalnice: 49
Zahvaljeno 154 puta na 115 poruka
|
![]()
Hm, nisam siguran da razumem ovo dobro. Koji je redosled prolaska kroz čvorove u ovom slučaju (može, recimo na primeru nekog stabla sa 3-4 nivoa)? Najbolje što sam ja uspeo je da obuhvatim možda nekih pola čvorova u jednom prolazu, tj, jednoj petlji. Imajte u vidu da je jedini način za prelazak na sledeći čvor kod dinamičkog vezivanja, nesto tipa node = node->left ili node = node->right.
|
![]() |
![]() |
![]() |
#5 |
Član
Član od: 15.12.2010.
Lokacija: Beograd
Poruke: 120
Zahvalnice: 26
Zahvaljeno 39 puta na 32 poruka
|
![]()
Šta ti ovde nije jasno (nisi precizirao), ali ajde da probam ponovo da ti objasnim.
Nemam predstavu kako izgleda tvoj kod ali da zamislimo jedan čvor kao strukturu Kod:
struct TreeNode { int data; // neki podatak TreeNode *left; // pokazivač na levi čvor TreeNode *right; // pokazivač na desni čvor } Ono root ti je prvi čvor a sama funkcija izgleda ovako: Kod:
void Prolazak( TreeNode *root ) { if (root->left)Prolazak(root->left); if (root->right)Prolazak(root->right); // ovde možeš da uradiš nešto sa čvorom return; } Ako i dalje ne razumeš onda jedino da staviš ovde svoj kod pa da probamo na njemu ili da ti objasni neko ko je bolji u objašnjavanju. Ja bolje ne umem ![]() |
![]() |
![]() |
![]() |
#6 |
V.I.P. Programiranje
Član od: 29.8.2007.
Lokacija: Valjevo
Poruke: 1.349
Zahvalnice: 983
Zahvaljeno 371 puta na 280 poruka
|
![]()
Treba da proverava samo root pokazivac da li je null:
Kod:
void rekurzija(Tree* root) { if(0 != root) { // ovde radis na trenutnom pokazivacu rekurzija(root->lef); rekurzija(root->right); } } |
![]() |
![]() |
![]() |
#7 | |
Član
Član od: 15.12.2010.
Lokacija: Beograd
Poruke: 120
Zahvalnice: 26
Zahvaljeno 39 puta na 32 poruka
|
![]() Citat:
Kako god, sad ima dva primera pa će valjda lakše da shvati. |
|
![]() |
![]() |
![]() |
#8 |
V.I.P. Programiranje
Član od: 29.8.2007.
Lokacija: Valjevo
Poruke: 1.349
Zahvalnice: 983
Zahvaljeno 371 puta na 280 poruka
|
![]()
Treba jer ostali rekurzivni pozivi funkcije proveravaju left i right koji su u stvari root na tom "nivou", ako me razumes posto ne umem ni ja bas da objasnjavam.
|
![]() |
![]() |
![]() |
#9 | |
Član
Član od: 15.12.2010.
Lokacija: Beograd
Poruke: 120
Zahvalnice: 26
Zahvaljeno 39 puta na 32 poruka
|
![]() Citat:
@GrimReaper tebi je sve jedno šta ćeš od ovoga koristiti. Nadam se da ti je pomogao bilo koji primer. Ovaj drugi primer možda čak i deluje optimizovanije jer ima samo jednu proveru u petlji. Sa druge strane on će za svaki krajnji čvor pozvati rekurziju još dva puta u prazno. |
|
![]() |
![]() |
![]() |
#10 |
Starosedelac
Član od: 5.12.2005.
Lokacija: Niš
Poruke: 1.259
Zahvalnice: 49
Zahvaljeno 154 puta na 115 poruka
|
![]()
Ok, hvala na pomoći, uspeo sam da uradim ono što sam hteo. U suštini, moj zadatak je bio da prebrojim listove stabla, a mislio sam da to uradim na ovaj način. No, na internetu sam našao elegantnije rešenje.
Kod:
int countLeaves(BTnode<T> *p) { if (p == NULL) return 0; else if (p->left == NULL && p->right == NULL) return 1; else return countLeaves(p->left) + countLeaves(p->right); } Kod:
void traverse(BTnode<T> *p) { l = p->left; r = p->right; while (p != NULL) { traverse(l); traverse(r); } } |
![]() |
![]() |
![]() |
Bookmarks sajtovi |
|
|
![]() |
||||
tema | temu započeo | forum | Odgovora | Poslednja poruka |
Binarno Stablo | -Vertex- | Programiranje | 8 | 22.6.2007 12:31 |