|
Programiranje Programski jezici, tehnike, alatke... |
|
Alatke vezane za temu | Vrste prikaza |
31.3.2014, 23:06 | #1 |
Veteran
|
Binarno stablo u c-u
Treba da napravim binarno stablo, tako da svaki cvor sadrzi ceo broj. I onda funkciju koja vraca broj cvorova koji sadrze broj veci od svih svojih potomaka.
I sad ne mogu nikako da nadjem nacin da uporedim svaki cvor sa svim njegovim potomcima. Stavicu dole funkcije za rekurzivno dodavanje cvora i prolazak kroz stablo, a ako neko zna neka napise kako da napravim gore pomenutu funkciju. Kod:
#include<stdio.h> #include<stdlib.h> typedef struct cvor { int broj; struct cvor *levo; struct cvor *desno; }Cvor; typedef Cvor *Stablo; Stablo dodaj_u (Stablo koren, int b) { /* Dodavanje u uredjeno stablo. */ if (! koren) { koren =(Cvor *) malloc (sizeof(Cvor)); koren->broj = b; koren->levo = koren->desno = NULL; } else if (koren->broj > b) koren->levo = dodaj_u (koren->levo, b); else if (koren->broj < b) koren->desno = dodaj_u (koren->desno, b); else if (rand() / (RAND_MAX+1.) < 0.5) koren->levo = dodaj_u (koren->levo, b); else koren->desno = dodaj_u (koren->desno, b); return koren; } void svi_cvorovi (Stablo koren) { if (koren) { svi_cvorovi (koren->levo); svi_cvorovi (koren->desno); } } void main(){ Cvor *koren=NULL; koren=dodaj_u(koren,19); koren=dodaj_u(koren,6); koren=dodaj_u(koren,85); koren=dodaj_u(koren,2); system("pause"); } |
31.3.2014, 23:51 | #2 |
Deo inventara foruma
Član od: 7.12.2005.
Lokacija: Beograd
Poruke: 3.097
Zahvalnice: 513
Zahvaljeno 679 puta na 573 poruka
|
Re: Binarno stablo u c-u
Mislis funkciju koja vraca broj cvorova koji sadrze broj veci od zbira sve svoje dece?
Ako je tako, podeli to u dva problema. Napravi jednu funkciju koja ce za zadati koren stabla sabrati jednostavno sve cvorove tog nekog drveta. Zatim, napravi obicnu funkciju koja prolazi kroz stablo, i za svaki pojedinacni cvor poziva ovu prethodnu funkciju, tj za svaki cvor sabira vrednosti sve njegove dece. I onda jednostavno imas neku INT promenljivu koja belezi broj. Svaki put kada naidjes na cvor koji je veci od zbira svih potomaka stavis INT++. i to je to. EDIT: Takodje uzmi u obzir da je ovo mozda trik pitanje, i u stvari jako lako. Po definiciji binarnog stabla, vrednosti se unose tako da se vrednosti vece od cvora X stavljaju kao njegovo desno dete, a vrednosti manje od X cvora kao njegovo levo dete. Ako pratimo to pravilo, jedini cvorovi koji su veci od sve svoje dece su oni koji nemaju desno dete. Ako postujemo tu definiciju, tvoj zadatak je ultra-lak. Samo treba da prolazis kroz stablo i brojis cvorove koji nemaju desno dete, u najgorem slucaju da proveravas da nije u pitanju list, ako ti se to ne vazi. Poslednja ispravka: Marko93 (1.4.2014 u 0:05) |
Sledeći korisnik se zahvaljuje korisniku Marko93 na korisnoj poruci: | ||
gavrilo (1.4.2014) |
1.4.2014, 17:28 | #3 |
Veteran
|
Re: Binarno stablo u c-u
Ne bas, mislim funkcija koja ispituje da li neki cvor sadrzi broj koji je veci od broja svih svojih potomaka.
Dakle ako neki cvor sadrzi broj 15 i ima dva potomka koji sadrze brojeve 10 i 9 onda imamo cvor koji ima veci broj od svojih potomaka. Ali sve jedno, na isto se svodi, poenta izgleda i jeste bila u pravilu da levo idu manji a desno veci, i jedini uslov je da cvor sadrzi levu granu, a desnu ne , ne znam kako se nisam setio, hvala |
1.4.2014, 23:19 | #4 |
Veteran
|
Re: Binarno stablo u c-u
Za resenje tvog problema postoji tezi i laksi nacin.
Najlaksi nacin je da prilikom ubacivanja cvorova u stablo ti kreiras Binary Search Tree (sto jeste tip binarnog stabla). Njegova karakteristika je ta sto svako levo dete cvora je manje od njega, i svako desno je vece. Da bi prebrojao cvorove koje imaju veci broj od svojih potomaka samo trebas da prebrojis cvorove koji imaju levog potomka. Tezi nacin je...nista mi pametno ovde ne pada napamet iskreno. Samo suva sila. Resenje ta taj nacin je brutalno za implementaciju (ili barem ja sada ne znam ni jedno pametno). Znaci preporuka, radi binary search tree. |
2.4.2014, 12:32 | #5 | |
Veteran
|
Re: Binarno stablo u c-u
Citat:
Ko sto rece Marko dole. Ali nikako ne mogu tu ideju da implementiram, uvek ispadne neka za*ebancija Poslednja ispravka: gavrilo (2.4.2014 u 12:41) |
|
2.4.2014, 12:48 | #6 |
Deo inventara foruma
Član od: 7.12.2005.
Lokacija: Beograd
Poruke: 3.097
Zahvalnice: 513
Zahvaljeno 679 puta na 573 poruka
|
Re: Binarno stablo u c-u
Pa podeli taj problem na vise jednostavnijih problema koje ces lako da resis. Evo ovako:
1. Napravis funkciju kojoj posaljes koren drveta, i ona prolazi kroz to drvo, pocevsi od tog korena, i samo proverava da li je koren najveci broj u drvetu. I vraca true ili false kao rezultat. Zatim. Ovo vec mozes opusteno u mainu da pises. 2. Prolazis kroz drvo, DFS ili BFS, nevazno, i jednostavno za svaki cvor pokreces tu funkciju, i za svaki cvor za koji ti se vrati "true", neku promenljivu povecavas za jedan, koja ti broji broj takvih cvorova.. I to je to.. samo pazi naravno da isti cvor ne posetis dva puta tokom ovog prolaza.. |
2.4.2014, 21:07 | #7 |
Veteran
|
Re: Binarno stablo u c-u
Razumem na sta mislis, ali evo u cemu je tu problem.
Predpostavljam da si na ovakvu nekakvu funkciju mislio : Kod:
bool provera(Stablo koren){ Cvor *tmp=koren; if(koren){ if(tmp->broj < koren->broj) return false; provera(koren->levo); provera(koren->desno); } return true; } I kada treba da predjem na sledeci cvor, i pozove se ova linija : Kod:
provera(koren->levo) Poslednja ispravka: gavrilo (2.4.2014 u 21:25) |
3.4.2014, 1:58 | #8 |
Deo inventara foruma
Član od: 7.12.2005.
Lokacija: Beograd
Poruke: 3.097
Zahvalnice: 513
Zahvaljeno 679 puta na 573 poruka
|
Re: Binarno stablo u c-u
Napravi funkciju tako da prima 2 vrednosti. Prva vrednost ce biti koren->levo i koren->desno, a u drugu vrednost ces uvek slati vrednost "onog prvog korena". Znaci ta druga vrednost se nece menjati kako rekurzija ide dublje i dublje.
I onda ce ti provera glasiti if(tmp->broj < "ta druga vrednost") return false; A iz maina ces tu funkciju pozivati ovako: Bool=provera(koren,koren->broj); |
Sledeći korisnik se zahvaljuje korisniku Marko93 na korisnoj poruci: | ||
gavrilo (3.4.2014) |
Bookmarks sajtovi |
|
|
Slične teme | ||||
tema | temu započeo | forum | Odgovora | Poslednja poruka |
Binarno stablo | GrimReaper | Programiranje | 9 | 24.6.2011 13:01 |
Binarno Stablo | -Vertex- | Programiranje | 8 | 22.6.2007 12:31 |