Binarno stablo u c-u

[gavrilo]

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.

#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");
}

[Marko93]

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.

[gavrilo]

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

[Ivan452]

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.

[gavrilo]

Ivan452 kaže:

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

[Marko93]

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]

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);