Forum Sveta kompjutera  

Nazad   Forum Sveta kompjutera > Test Run > Programiranje

Programiranje Programski jezici, tehnike, alatke...

Odgovor
 
Alatke vezane za temu Vrste prikaza
Stara 31.3.2014, 23:06   #1
gavrilo
Veteran
 
Član od: 25.11.2008.
Lokacija: :D
Poruke: 581
Zahvalnice: 127
Zahvaljeno 39 puta na 39 poruka
Slanje poruke preko MSN-a korisniku gavrilo
Određen forumom 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");
}
gavrilo je offline   Odgovor sa citatom ove poruke
Stara 31.3.2014, 23:51   #2
Marko93
Deo inventara foruma
 
Član od: 7.12.2005.
Lokacija: Beograd
Poruke: 3.099
Zahvalnice: 513
Zahvaljeno 679 puta na 573 poruka
Određen forumom 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)
Marko93 je offline   Odgovor sa citatom ove poruke
Sledeći korisnik se zahvaljuje korisniku Marko93 na korisnoj poruci:
gavrilo (1.4.2014)
Stara 1.4.2014, 17:28   #3
gavrilo
Veteran
 
Član od: 25.11.2008.
Lokacija: :D
Poruke: 581
Zahvalnice: 127
Zahvaljeno 39 puta na 39 poruka
Slanje poruke preko MSN-a korisniku gavrilo
Određen forumom 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
gavrilo je offline   Odgovor sa citatom ove poruke
Stara 1.4.2014, 23:19   #4
Ivan452
Veteran
 
Član od: 25.7.2008.
Lokacija: Beograd
Poruke: 772
Zahvalnice: 33
Zahvaljeno 189 puta na 152 poruka
Slanje poruke preko MSN-a korisniku Ivan452
Određen forumom 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.
Ivan452 je offline   Odgovor sa citatom ove poruke
Stara 2.4.2014, 12:32   #5
gavrilo
Veteran
 
Član od: 25.11.2008.
Lokacija: :D
Poruke: 581
Zahvalnice: 127
Zahvaljeno 39 puta na 39 poruka
Slanje poruke preko MSN-a korisniku gavrilo
Određen forumom Re: Binarno stablo u c-u

Citat:
Ivan452 kaže: Pregled poruke
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.
Da, tako sam i uradio, a ako nije u pitanju uredjeno stablo, odnosno ako se ne primenjuje pravilo levo manji desno veci, na prvi pogled mi je izgledalo mnogo prosto - da jednostavno rekurzivno obidjem celo stablo, i prilikom svake posete nekom cvoru, taj cvor se uzme kao koren nekog njegovog podstabla i uporedje se broj tog trenutnog korena sa svim ostalim brojevima koje sadrze cvorovi tog podstabla.
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)
gavrilo je offline   Odgovor sa citatom ove poruke
Stara 2.4.2014, 12:48   #6
Marko93
Deo inventara foruma
 
Član od: 7.12.2005.
Lokacija: Beograd
Poruke: 3.099
Zahvalnice: 513
Zahvaljeno 679 puta na 573 poruka
Određen forumom 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..
Marko93 je offline   Odgovor sa citatom ove poruke
Stara 2.4.2014, 21:07   #7
gavrilo
Veteran
 
Član od: 25.11.2008.
Lokacija: :D
Poruke: 581
Zahvalnice: 127
Zahvaljeno 39 puta na 39 poruka
Slanje poruke preko MSN-a korisniku gavrilo
Određen forumom 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;
}
E ovde je problem u tome sto ne mogu da napravim promenljivu tmp koja ce da ima vrednost korena u trenutku kada se prvi put pozove, iz razloga sto se radi o rekurziji.

I kada treba da predjem na sledeci cvor, i pozove se ova linija :
Kod:
provera(koren->levo)
Funkcija opet krece od pocetka i onda promenljiva tmp uzima vrednost od koren->levo.

Poslednja ispravka: gavrilo (2.4.2014 u 21:25)
gavrilo je offline   Odgovor sa citatom ove poruke
Stara 3.4.2014, 1:58   #8
Marko93
Deo inventara foruma
 
Član od: 7.12.2005.
Lokacija: Beograd
Poruke: 3.099
Zahvalnice: 513
Zahvaljeno 679 puta na 573 poruka
Određen forumom 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);
Marko93 je offline   Odgovor sa citatom ove poruke
Sledeći korisnik se zahvaljuje korisniku Marko93 na korisnoj poruci:
gavrilo (3.4.2014)
Odgovor

Bookmarks sajtovi

Alatke vezane za temu
Vrste prikaza

Vaš status
Ne možete postavljati teme
Ne možete odgovarati na poruke
Ne možete slati priloge uz poruke
Ne možete prepravljati svoje poruke

BB kod: uključeno
Smajliji: uključeno
[IMG] kod: uključeno
HTML kod: isključeno


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


Sva vremena su po Griniču +2 h. Sada je 6:08.


Powered by vBulletin® verzija 3.8.7
Copyright ©2000–2019, vBulletin Solutions, Inc.
Hosted by Beograd.com