|
Programiranje Programski jezici, tehnike, alatke... |
|
Alatke vezane za temu | Vrste prikaza |
23.6.2011, 1:12 | #1 |
Starosedelac
Član od: 5.12.2005.
Lokacija: Niš
Poruke: 1.259
Zahvalnice: 49
Zahvaljeno 154 puta na 115 poruka
|
Binarno stablo
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.
|
23.6.2011, 4:25 | #2 |
Član
Član od: 15.12.2010.
Lokacija: Beograd
Poruke: 120
Zahvalnice: 26
Zahvaljeno 39 puta na 32 poruka
|
Re: Binarno stablo
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. |
23.6.2011, 11:13 | #3 |
Član
Član od: 30.10.2005.
Lokacija: Vancouver, BC
Poruke: 475
Zahvalnice: 48
Zahvaljeno 95 puta na 75 poruka
|
Re: Binarno stablo
Samo treba obratiti paznju na slucaj kada je stablo prazno, posto ce u tom slucaju pri prvom pozivu dobiti null pointer exception.
|
23.6.2011, 12:48 | #4 |
Starosedelac
Član od: 5.12.2005.
Lokacija: Niš
Poruke: 1.259
Zahvalnice: 49
Zahvaljeno 154 puta na 115 poruka
|
Re: Binarno stablo
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.
|
23.6.2011, 18:25 | #5 |
Član
Član od: 15.12.2010.
Lokacija: Beograd
Poruke: 120
Zahvalnice: 26
Zahvaljeno 39 puta na 32 poruka
|
Re: Binarno stablo
Š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 |
23.6.2011, 18:39 | #6 |
V.I.P. Programiranje
Član od: 29.8.2007.
Lokacija: Valjevo
Poruke: 1.349
Zahvalnice: 983
Zahvaljeno 371 puta na 280 poruka
|
Re: Binarno stablo
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); } } |
23.6.2011, 18:46 | #7 | |
Član
Član od: 15.12.2010.
Lokacija: Beograd
Poruke: 120
Zahvalnice: 26
Zahvaljeno 39 puta na 32 poruka
|
Re: Binarno stablo
Citat:
Kako god, sad ima dva primera pa će valjda lakše da shvati. |
|
23.6.2011, 19:00 | #8 |
V.I.P. Programiranje
Član od: 29.8.2007.
Lokacija: Valjevo
Poruke: 1.349
Zahvalnice: 983
Zahvaljeno 371 puta na 280 poruka
|
Re: Binarno stablo
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.
|
23.6.2011, 20:37 | #9 | |
Član
Član od: 15.12.2010.
Lokacija: Beograd
Poruke: 120
Zahvalnice: 26
Zahvaljeno 39 puta na 32 poruka
|
Re: Binarno stablo
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. |
|
24.6.2011, 13:01 | #10 |
Starosedelac
Član od: 5.12.2005.
Lokacija: Niš
Poruke: 1.259
Zahvalnice: 49
Zahvaljeno 154 puta na 115 poruka
|
Re: Binarno stablo
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 |
|
|
Slične teme | ||||
tema | temu započeo | forum | Odgovora | Poslednja poruka |
Binarno Stablo | -Vertex- | Programiranje | 8 | 22.6.2007 12:31 |