From: Doni Pracner Date: Thu, 22 Dec 2016 11:33:39 +0000 (+0100) Subject: Stabla, dodat zadatak sa vezbi X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa2-materijali.git;a=commitdiff_plain;h=c96a71ed06b6978c439b8c18ef856a4e0a9a79b6 Stabla, dodat zadatak sa vezbi --- diff --git a/Stabla/konkretnoStablo/BinarnoStablo.java b/Stabla/konkretnoStablo/BinarnoStablo.java new file mode 100644 index 0000000..230bc74 --- /dev/null +++ b/Stabla/konkretnoStablo/BinarnoStablo.java @@ -0,0 +1,72 @@ +// Konkretno stablo koje sadrzi Osobe +class StabloO { + + // jedan cvor u stablu sa jednom osobom i pokazivacima + // na "decu" + private static class Cvor { + Osoba osoba; + Cvor levo; + Cvor desno; + } + + // koren celog stabla + private Cvor koren; + + // Vraca ukupan broj osoba u stablu + public int brojOsoba() { + return brojOsoba(koren); + } + + protected static int brojOsoba(Cvor cvor) { + if (cvor == null) { + return 0; + } + int broj = 1; + broj = broj + brojOsoba(cvor.levo); + broj = broj + brojOsoba(cvor.desno); + return broj; + } + + public int brojNivoa() { + // Spremimo argumente i pozovemo rekurzivni metod + return brojNivoa(koren); + } + + // Metod koji zapravo resava dati problem + protected static int brojNivoa(Cvor cvor) { + if (cvor == null) { + return 0; + } + int brojNivoaLevog = brojNivoa(cvor.levo); + int brojNivoaDesnog = brojNivoa(cvor.desno); + return Math.max(brojNivoaLevog, brojNivoaDesnog) + 1; + } + +} + +// Glavna klasa +public class BinarnoStablo { + + // Glavni program + public static void main(String[] args) { + + // Napravimo pomocni objekat za ucitavanje i ispisivanje + TreeIO io = new TreeIO<>(StabloO.class); + + // Procitamo stablo iz fajla + StabloO stablo = io.read(Svetovid.in("Osobe.txt")); + + // Ispisemo ucitano stablo + io.print(Svetovid.out, stablo); + + // ilustracije poziva metoda + + int brojElemenata = stablo.brojOsoba(); + Svetovid.out.println("Broj elemenata:", brojElemenata); + + int brojNivoa = stablo.brojNivoa(); + Svetovid.out.println("Broj nivoa:", brojNivoa); + + // dodati ovde pozive implementiranih metoda + } +} diff --git a/Stabla/konkretnoStablo/_zadatak-stabla1.txt b/Stabla/konkretnoStablo/_zadatak-stabla1.txt new file mode 100644 index 0000000..d1354e2 --- /dev/null +++ b/Stabla/konkretnoStablo/_zadatak-stabla1.txt @@ -0,0 +1,149 @@ +************************************************************ + Zadatak - binarna stabla +************************************************************ + +Data je klasa BinarnoStablo sa glavnim programom koji +ucitava jedno stablo i poziva neke od operacija nad njim. +U istom fajlu je i klasa `StabloO` koja predstavlja binarno +stablo osoba. Klasa `Osoba` je takodje data implmentirana. + +U okviru klase `StabloO` implementirati operacije navedene u +nastavku i ilustrovati njihov rad pozivanjem iz glavnog +programa u `BinarnoStablo`. Svaki metod je potrebno +implementirati kao javan metod klase `StabloO`, a cesto je +potrebno napravitit i pomocni zasticen staticki metod istog +imena. Pogledati primer implementacije metoda +brojElemenata() i brojNivoa(). + +Sve promene treba raditi u fajlu BinarnoStablo.java u kome +su pomenute klase. Ostali fajlovi su klasa `Osoba` koja +predstavlja element koji ubacujemo u konkretnom programu, +kao i pomocne klase koje sluze za ucitavanje stabla iz fajla +u urednom formatu. Ucitavanje stabla na ovaj nacin nije +neophodno uciti, a dato je tacno kako treba da se ucita. + + +Metodi +====== + +public boolean jePrazno() +------------------------- + +U klasi StabloO, implementirati metod koji +vraca true ako je stablo prazno, false ako nije. + +public boolean postojiElement(Osoba element) +---------------------------------------- + +U klasi StabloO, implementirati metod koji +vraca true ako se prosledjeni elemnt nalazi u +stablu, false inace. + +Prilikom pretrage stabla koristiti metod equals(). + + +public void stampajPreorder() +---------------------------- + +U klasi StabloO, implementirati metod koji +stampa sve elemente preorder nacinom obilaska. + +public void stampajInOrder() +---------------------------- + +U klasi StabloO, implementirati metod koji +stampa sve elemente inorder nacinom obilaska. + +public void stampajPostOrder() +---------------------------- + +U klasi StabloO, implementirati metod koji +stampa sve elemente postorder nacinom obilaska. + +public void stampajListove() +---------------------------- + +U klasi StabloO, implementirati metod koji +stampa sve elemente koji se nalaze u listovima. + +List je cvor koji nema ni levog ni desnog potomka. + +private Cvor pronadji(Osoba element) +------------------------------------ + +U klasi StabloO, implementirati metod koji +pronalazi dati element i vraca stablo sa korenom +u tom elementu. + +Ako element ne postoji u stablu, vratiti null. + +Ovaj metod koristiti kao pomocni za sledeci. + + +public void stampajSveIspod(Osoba element) +-------------------------------------- + +U klasi StabloO, implementirati metod koji +stampa sve elemnte koji su direktni ili indirektni +potomci datog. + + +public boolean ubaci(Osoba roditelj, Osoba potomak, boolean levo) +--------------------------------------------------------- + +U klasi StabloO, implementirati metod koji +pronalazi element dat u prvom argumentu (roditelj) +i kao njegovog poromka ubacuje element dat u drugom +argumentu (potomak). Ako je treci argument (levo) +true tada se element ubacuje kao levi potomak, a +ako je false, kao desni. + +Ako se na zeljenom mestu vec nalazi nesto, vratiti false +i ne ubacivati element, inace vratiti true pri uspesnom +ubacivanju. + + +public Osoba roditeljOd(Osoba potomak) +-------------------------------------- + +U klasi StabloO, implementirati metod koji +pronalazi i vraca roditelja datog elementa. Ako +je prosledjeni element koren celog stabla +vratiti null. + + +public Osoba min(Comparator komparator) +public Osoba max(Comparator komparator) +-------------------------------------- + +U klasi StabloO, implementirati metod koji +pronalazi i vraca najmanji, odnosno najveci, element +stabla. + +Prilikom pretrage koristiti prosledjeni komparator. + +Za testiranje je dat `KomparatorPoPlati`, napraviti +druge po potrebi. + + +public StabloO kopija() +------------------------- + +U klasi StabloO, implementirati metod koji +vraca kopiju stabla. + +Potrebno je iskopirati i sve cvorove kako izmene +jednog stabla ne bi uticale na drugo. + + +public StabloO obrnuto() +-------------------------- + +U klasi StabloO, implementirati metod koji +vraca novo stablo nastalo obrtanjem originalng. +Stablo se obrce tako sto se zamene mesta levih +i desnih podstabala koja se pre toga takogje +obrnu. + +Posle poziva metoda originalno stablo mora ostati +nepromenjeno.