#include "skup.h" Skup *napravi_cvor(int broj) { /* dinamicki kreiramo cvor */ Skup *novi = (Skup *) malloc(sizeof(Skup)); /* u slucaju greske ... */ if (novi == NULL) { fprintf(stderr, "malloc() greska\n"); exit(1); } /* inicijalizacija */ novi->vrednost = broj; novi->levi = NULL; novi->desni = NULL; /* vracamo adresu novog cvora */ return novi; } Skup *dodaj_u_stablo(Skup * koren, int broj) { /* izlaz iz rekurzije: ako je stablo bilo prazno, novi koren je upravo novi cvor */ if (koren == NULL) return napravi_cvor(broj); /* Ako je stablo neprazno, i koren sadrzi manju vrednost od datog broja, broj se umece u desno podstablo, rekurzivnim pozivom */ if (koren->vrednost < broj) koren->desni = dodaj_u_stablo(koren->desni, broj); /* Ako je stablo neprazno, i koren sadrzi vecu vrednost od datog broja, broj se umece u levo podstablo, rekurzivnim pozivom */ else if (koren->vrednost > broj) koren->levi = dodaj_u_stablo(koren->levi, broj); /* U slucaju da je koren jednak datom broju, tada broj vec postoji u stablu, i ne radimo nista */ /* Vracamo koren stabla */ return koren; } Skup *pretrazi_stablo(Skup * koren, int broj) { /* Izlaz iz rekurzije: ako je stablo prazno, tada trazeni broj nije u stablu */ if (koren == NULL) return NULL; /* Ako je stablo neprazno, tada se pretrazivanje nastavlja u levom ili desnom podstablu, u zavisnosti od toga da li je trazeni broj respektivno manji ili veci od vrednosti korena. Ukoliko je pak trazeni broj jednak korenu, tada se vraca adresa korena. */ if (koren->vrednost < broj) return pretrazi_stablo(koren->desni, broj); else if (koren->vrednost > broj) return pretrazi_stablo(koren->levi, broj); else return koren; } Skup *pronadji_najmanji(Skup * koren) { /* Slucaj praznog stabla */ if (koren == NULL) return NULL; /* Izlaz iz rekurzije: ako koren nema levog sina, tada je upravo koren po vrednosti najmanji cvor. */ if (koren->levi == NULL) return koren; /* U suprotnom je najmanja vrednost u stablu upravo najmanja vrednost u levom podstablu, pa se pretraga nastavlja rekurzivno u levom podstablu. */ else return pronadji_najmanji(koren->levi); } Skup *obrisi_element(Skup * koren, int broj) { Skup *pomocni = NULL; /* Izlaz iz rekurzije: ako je stablo prazno, ono ostaje prazno i nakon brisanja */ if (koren == NULL) return NULL; /* Ako je vrednost broja veca od vrednosti korena, tada se broj eventualno nalazi u desnom podstablu, pa treba rekurzivno primeniti postupak na desno podstablo. Koren ovako modifikovanog stabla je nepromenjen, pa vracamo stari koren */ if (koren->vrednost < broj) { koren->desni = obrisi_element(koren->desni, broj); return koren; } /* Ako je vrednost broja manja od vrednosti korena, tada se broj eventualno nalazi u levom podstablu, pa treba rekurzivno primeniti postupak na levo podstablo. Koren ovako modifikovanog stabla je nepromenjen, pa vracamo stari koren */ if (koren->vrednost > broj) { koren->levi = obrisi_element(koren->levi, broj); return koren; } /* Slede podslucajevi vezani za slucaj kada je vrednost korena jednaka broju koji se brise (tj. slucaj kada treba obrisati koren) */ /* Ako koren nema sinova, tada se on prosto brise, i rezultat je prazno stablo (vracamo NULL) */ if (koren->levi == NULL && koren->desni == NULL) { free(koren); return NULL; } /* Ako koren ima samo levog sina, tada se brisanje vrsi tako sto obrisemo koren, a novi koren postaje levi sin */ if (koren->levi != NULL && koren->desni == NULL) { pomocni = koren->levi; free(koren); return pomocni; } /* Ako koren ima samo desnog sina, tada se brisanje vrsi tako sto obrisemo koren, a novi koren postaje desni sin */ if (koren->desni != NULL && koren->levi == NULL) { pomocni = koren->desni; free(koren); return pomocni; } /* Slucaj kada koren ima oba sina. U tom slucaju se brisanje vrsi na sledeci nacin: najpre se potrazi sledbenik korena (u smislu poretka) u stablu. To je upravo po vrednosti najmanji cvor u desnom podstablu. On se moze pronaci npr. funkcijom pronadji_najmanji(). Nakon toga se u koren smesti vrednost tog cvora, a u taj cvor se smesti vrednost korena (tj. broj koji se brise). Onda se prosto rekurzivno pozove funkcija za brisanje na desno podstablo. S obzirom da u njemu treba obrisati najmanji element, a on definitivno ima najvise jednog potomka, jasno je da ce to brisanje biti obavljeno na jedan od nacina koji je gore opisan. */ pomocni = pronadji_najmanji(koren->desni); koren->vrednost = pomocni->vrednost; pomocni->vrednost = broj; koren->desni = obrisi_element(koren->desni, broj); return koren; } void prikazi_stablo(Skup * koren) { /* izlaz iz rekurzije */ if (koren == NULL) return; prikazi_stablo(koren->levi); printf("%d, ", koren->vrednost); prikazi_stablo(koren->desni); } Skup *oslobodi_stablo(Skup * koren) { /* Izlaz iz rekurzije */ if (koren == NULL) return NULL; koren->levi = oslobodi_stablo(koren->levi); koren->desni = oslobodi_stablo(koren->desni); free(koren); return NULL; } Skup *kopiraj_stablo(Skup * koren) { Skup *duplikat = NULL; /* Izlaz iz rekurzije: ako je stablo prazno, vracamo NULL */ if (koren == NULL) return NULL; /* Dupliramo koren stabla i postavljamo ga da bude koren novog stabla */ duplikat = napravi_cvor(koren->vrednost); /* Rekurzivno dupliramo levo podstablo i njegovu adresu cuvamo u pokazivacu na levo podstablo korena duplikata. */ duplikat->levi = kopiraj_stablo(koren->levi); /* Rekurzivno dupliramo desno podstablo i njegovu adresu cuvamo u pokazivacu na desno podstablo korena duplikata. */ duplikat->desni = kopiraj_stablo(koren->desni); /* Vracamo adresu korena duplikata */ return duplikat; } Skup *kreiraj_uniju(Skup * koren_1, Skup * koren_2) { /* Ako je drugo stablo neprazno */ if (koren_2 != NULL) { /* dodajemo koren drugog stabla u prvo stablo */ koren_1 = dodaj_u_stablo(koren_1, koren_2->vrednost); /* rekurzivno racunamo uniju levog i desnog podstabla drugog stabla sa prvim stablom */ koren_1 = kreiraj_uniju(koren_1, koren_2->levi); koren_1 = kreiraj_uniju(koren_1, koren_2->desni); } /* vracamo pokazivac na modifikovano prvo stablo */ return koren_1; } Skup *kreiraj_presek(Skup * koren_1, Skup * koren_2) { /* Ako je prvo stablo prazno, tada je i rezultat prazno stablo */ if (koren_1 == NULL) return NULL; /* Kreiramo presek levog i desnog podstabla sa drugim stablom, tj. iz levog i desnog podstabla prvog stabla brisemo sve one elemente koji ne postoje u drugom stablu */ koren_1->levi = kreiraj_presek(koren_1->levi, koren_2); koren_1->desni = kreiraj_presek(koren_1->desni, koren_2); /* Ako se koren prvog stabla ne nalazi u drugom stablu tada ga uklanjamo iz prvog stabla */ if (pretrazi_stablo(koren_2, koren_1->vrednost) == NULL) koren_1 = obrisi_element(koren_1, koren_1->vrednost); /* Vracamo koren tako modifikovanog prvog stabla */ return koren_1; } Skup *kreiraj_razliku(Skup * koren_1, Skup * koren_2) { /* Ako je prvo stablo prazno, tada je i rezultat prazno stablo */ if (koren_1 == NULL) return NULL; /* Kreiramo razliku levog i desnog podstabla sa drugim stablom, tj. iz levog i desnog podstabla prvog stabla brisemo sve one elemente koji postoje i u drugom stablu */ koren_1->levi = kreiraj_razliku(koren_1->levi, koren_2); koren_1->desni = kreiraj_razliku(koren_1->desni, koren_2); /* Ako se koren prvog stabla nalazi i u drugom stablu tada ga uklanjamo iz prvog stabla */ if (pretrazi_stablo(koren_2, koren_1->vrednost) != NULL) koren_1 = obrisi_element(koren_1, koren_1->vrednost); /* Vracamo koren tako modifikovanog prvog stabla */ return koren_1; } int broj_elemenata(Skup * koren) { if (koren == NULL) return 0; return broj_elemenata(koren->levi) + broj_elemenata(koren->desni) + 1; } int podskup(Skup * s1, Skup * s2) { if (s1 == NULL) return 1; return pretrazi_stablo(s2, s1->vrednost) != NULL && podskup(s1->levi, s2) && podskup(s1->desni, s2); }