From: Doni Pracner Date: Sun, 18 Dec 2016 21:08:07 +0000 (+0100) Subject: uklonjeno StabloOpstegTipa koje se ne radi vise X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa2-materijali.git;a=commitdiff_plain;h=0df7082afb219400a49ed38fdd1b3dce086a64e2 uklonjeno StabloOpstegTipa koje se ne radi vise --- diff --git a/Stabla/StabloOpstegTipa/Konverter.java b/Stabla/StabloOpstegTipa/Konverter.java deleted file mode 100644 index 421c1ce..0000000 --- a/Stabla/StabloOpstegTipa/Konverter.java +++ /dev/null @@ -1,33 +0,0 @@ -// Instance ove klase konvertuju string u neki konkretan tip podataka i obratno -// Takodje je dato par gotovih implementacija konvertera -public interface Konverter { - - public String toString(T element); - public T fromString(String string); - - public static Konverter INTEGER = new Konverter() { - @Override public String toString(Integer element) { return element == null ? null : element.toString(); } - @Override public Integer fromString(String string) { return string == null ? null : Integer.parseInt(string); } - }; - - public static Konverter LONG = new Konverter() { - @Override public String toString(Long element) { return element == null ? null : element.toString(); } - @Override public Long fromString(String string) { return string == null ? null : Long.parseLong(string); } - }; - - public static Konverter DOUBLE = new Konverter() { - @Override public String toString(Double element) { return element == null ? null : element.toString(); } - @Override public Double fromString(String string) { return string == null ? null : Double.parseDouble(string); } - }; - - public static Konverter STRING = new Konverter() { - @Override public String toString(String element) { return element; } - @Override public String fromString(String string) { return string; } - }; - - public static Konverter OSOBA = new Konverter() { - @Override public String toString(Osoba element) { return element == null ? null : element.getIme() + " " + element.getPrezime() + " " + element.getGodinaRodjenja(); } - @Override public Osoba fromString(String string) { if (string == null) return null; else { String[] delovi = string.split(" "); return new Osoba(delovi[0], delovi[1], Integer.parseInt(delovi[2]));} } - }; - -} diff --git a/Stabla/StabloOpstegTipa/Osoba.java b/Stabla/StabloOpstegTipa/Osoba.java deleted file mode 100644 index 6971b1c..0000000 --- a/Stabla/StabloOpstegTipa/Osoba.java +++ /dev/null @@ -1,72 +0,0 @@ -import java.util.Objects; - -// Tip podataka koji predstavlja jednu osobu -public class Osoba { - - private final String ime; - private final String prezime; - private final int godinaRodjenja; - - public Osoba(String ime, String prezime, int godinaRodjenja) { - if (ime == null) { - throw new IllegalArgumentException("ime"); - } - this.ime = ime; - if (prezime == null) { - throw new IllegalArgumentException("prezime"); - } - this.prezime = prezime; - this.godinaRodjenja = godinaRodjenja; - } - - public String getIme() { - return ime; - } - - public String getPrezime() { - return prezime; - } - - public int getGodinaRodjenja() { - return godinaRodjenja; - } - - @Override - public int hashCode() { - final int prostBroj = 31; - int rezultat = 1; - rezultat = prostBroj * rezultat + godinaRodjenja; - rezultat = prostBroj * rezultat + ime.hashCode(); - rezultat = prostBroj * rezultat + prezime.hashCode(); - return rezultat; - } - - @Override - public boolean equals(Object obj) { - if (this == obj) { - return true; - } - if (obj == null) { - return false; - } - if (getClass() != obj.getClass()) { - return false; - } - Osoba that = (Osoba) obj; - if (this.godinaRodjenja != that.godinaRodjenja) { - return false; - } - if (!Objects.equals(this.ime, that.ime)) { - return false; - } - if (!Objects.equals(this.prezime, that.prezime)) { - return false; - } - return true; - } - - @Override - public String toString() { - return ime + " " + prezime + " " + godinaRodjenja; - } -} diff --git a/Stabla/StabloOpstegTipa/Osobe.txt b/Stabla/StabloOpstegTipa/Osobe.txt deleted file mode 100644 index 04cf8d0..0000000 --- a/Stabla/StabloOpstegTipa/Osobe.txt +++ /dev/null @@ -1,99 +0,0 @@ - /-----(o) Pera Peric 1953 - | - /-----(o) Paja Pajic 1962 - | | - | | /-----(o) Mitar Mitrovic 1958 - | | | | - | | | \-----(o) Dara Darinkov 1968 - | | | - | | /-----(o) Mile Milic 1962 - | | | | - | | | | /-----(o) Stefan Stefan-Stefan 1948 - | | | | | - | | | \-----(o) Nemanja Nemanjic 1979 - | | | - | \-----(o) Svetozar Svetozarevic 1954 - | | - | \-----(o) Zlaja Zlajic 1981 - | - /-----(o) Vuk Wolfeschlegelsteinhausenberger 1966 - | | - | | /-----(o) Nina Ninkov 1971 - | | | - | \-----(o) Raja Rajkovic 1985 - | | - | | /-----(o) Djoka Djokic 1979 - | | | - | \-----(o) Srbislava Srbislavac 1969 - | | - | \-----(o) Nikolina Nikolic 1944 - | | - | \-----(o) Zvonko Zvonkov 1983 - | --(o) Petar Petrovic 1945 - | - | /-----(o) Marko Markovic 1923 - | | | - | | | /-----(o) Jakov Karajakov 1966 - | | | | | - | | | | | /-----(o) Janko Jankovic 1959 - | | | | | | - | | | | \-----(o) Tuta Tutevski 1974 - | | | | | - | | | | \-----(o) Zorana Zoranovic-Zoranovski 1955 - | | | | - | | \-----(o) Zdravko Dren 1823 - | | | - | | \-----(o) Filip Filipovic 1957 - | | - \-----(o) Maja Majic 1972 - | - | /-----(o) Mislav Mislavski 1960 - | | - | /-----(o) Ljubisava Ljubisavljevic 1959 - | | | - | | | /-----(o) Pera Peric 1973 - | | | | - | | | /-----(o) Joksim Joksimovic 1959 - | | | | | - | | | | \-----(o) Mika Mikic 1970 - | | | | | - | | | | \-----(o) Baja Bajic 1967 - | | | | - | | \-----(o) Zrinko Zrinkovic 1965 - | | | - | | \-----(o) Hadzija Hadzi-Hadzic 1963 - | | | - | | \-----(o) Jova Jovic 1943 - | | | - | | \-----(o) Tatjana Tatjanic 1972 - | | | - | | \-----(o) Leposava Leposavljevic 1981 - | | | - | | | /-----(o) Zora Zoric 1969 - | | | | - | | \-----(o) Milos Milosevic 1953 - | | | - | | \-----(o) Jovan Jovanovic 1975 - | | - | /-----(o) Ivana Ivanovic 1977 - | | - \-----(o) Marinko Marinkovic 1965 - | - \-----(o) Marina Marinovic 1984 - | - \-----(o) Gojko Gojkovic 1967 - | - | /-----(o) Milan McMilan 1966 - | | | - | | | /-----(o) Milena Mileski 1977 - | | | | - | | | /-----(o) Miladinka Miladinovic 1964 - | | | | - | | \-----(o) Nikola Nikolic-Nikolic 1981 - | | | - | | \-----(o) Danijela Danijelac 1979 - | | - | /-----(o) Strahinja Strahimirovic 1976 - | | - \-----(o) Lazar Lazarevic 1976 diff --git a/Stabla/StabloOpstegTipa/ResenoStabloProgram.java b/Stabla/StabloOpstegTipa/ResenoStabloProgram.java deleted file mode 100644 index e0f310d..0000000 --- a/Stabla/StabloOpstegTipa/ResenoStabloProgram.java +++ /dev/null @@ -1,502 +0,0 @@ -import java.util.Comparator; -import java.util.NoSuchElementException; -import java.util.Objects; - -// Tip podataka koji sadrzi binarno stablo -class BinarnoStablo { - - // Tip podataka koji opisuje jedan cvor stabla - private static class Cvor { - - T element; - Cvor levo; - Cvor desno; - - Cvor(T element, Cvor levo, Cvor desno) { - this.element = element; - this.levo = levo; - this.desno = desno; - } - } - - // Cvor koji je koren stabla - // Ako je stablo prazno, koren je null - protected Cvor koren; - - // Kreiramo prazno stablo - public BinarnoStablo() { - koren = null; - } - - // Kreiramo stablo sa datim elementom u korenu - // bez levog i desnog podstabla - public BinarnoStablo(T element) { - koren = new Cvor<>(element, null, null); - } - - // Kreiramo novo stablo sa datim elementom u korenu - // i datim levim i desnim podstablom - public BinarnoStablo(T element, BinarnoStablo levo, BinarnoStablo desno) { - koren = new Cvor(element, levo.koren, desno.koren); - } - - // Zasticeni konstruktor za kreiranje novog stabla - // sa korenom u datom cvoru ovog stabla - protected BinarnoStablo(Cvor koren) { - this.koren = koren; - } - - public T getElement() { - if (koren == null) { // Stablo je prazno - throw new NoSuchElementException(); - } - return koren.element; - } - - public void setElement(T element) { - if (koren == null) { // Stablo je prazno - throw new NoSuchElementException(); - } - koren.element = element; - } - - public BinarnoStablo getLevoPodstablo() { - if (koren == null) { // Stablo je prazno - throw new NoSuchElementException(); - } - if (koren.levo == null) { // Nema levog podstabla - return null; - } - return new BinarnoStablo(koren.levo); - } - - public void setLevoPodstablo(BinarnoStablo levo) { - if (koren == null) { // Stablo je prazno - throw new NoSuchElementException(); - } - if (levo == null) { - koren.levo = null; - } else { - koren.levo = levo.koren; - } - } - - public BinarnoStablo getDesnoPodstablo() { - if (koren == null) { // Stablo je prazno - throw new NoSuchElementException(); - } - if (koren.desno == null) { - return null; - } - return new BinarnoStablo(koren.desno); - } - - public void setDesnoPodstablo(BinarnoStablo desno) { - if (koren == null) { // Stablo je prazno - throw new NoSuchElementException(); - } - if (desno == null) { - koren.desno = null; - } else { - koren.desno = desno.koren; - } - } - - //DatoNaVezbama - public int brojElemenata() { - // Spremimo argumente i pozovemo rekurzivni metod - return brojElemenata(koren); - } - - // Metod koji zapravo resava dati problem - //DatoNaVezbama - protected static int brojElemenata(Cvor cvor) { - if (cvor == null) { - return 0; - } - int broj = 1; - broj = broj + brojElemenata(cvor.levo); - broj = broj + brojElemenata(cvor.desno); - return broj; - } - - //DatoNaVezbama - public int brojNivoa() { - // Spremimo argumente i pozovemo rekurzivni metod - return brojNivoa(koren); - } - - // Metod koji zapravo resava dati problem - //DatoNaVezbama - 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; - } - - public boolean jePrazno() { - return koren == null; - } - - public boolean postojiElement(T element) { - return postojiElement(koren, element); - } - - protected static boolean postojiElement(Cvor cvor, T element) { - if (cvor == null) { - return false; - } - if (Objects.equals(cvor.element, element)) { - return true; - } - if (postojiElement(cvor.levo, element)) { - return true; - } - if (postojiElement(cvor.desno, element)) { - return true; - } - return false; - } - - public T min(Comparator komparator) { - return min(koren, komparator); - } - - protected static T min(Cvor cvor, Comparator komparator) { - if (cvor == null) { - return null; - } - T min = cvor.element; - T levoMin = min(cvor.levo, komparator); - if (komparator.compare(min, levoMin) > 0) { - min = levoMin; - } - T desnoMin = min(cvor.desno, komparator); - if (komparator.compare(min, desnoMin) > 0) { - min = desnoMin; - } - return min; - } - - public T max(Comparator komparator) { - return max(koren, komparator); - } - - protected static T max(Cvor cvor, Comparator komparator) { - if (cvor == null) { - return null; - } - T max = cvor.element; - T levoMax = max(cvor.levo, komparator); - if (komparator.compare(max, levoMax) > 0) { - max = levoMax; - } - T desnoMax = max(cvor.desno, komparator); - if (komparator.compare(max, desnoMax) > 0) { - max = desnoMax; - } - return max; - } - - public BinarnoStablo pronadji(T element) { - Cvor cvor = pronadji(koren, element); - if (cvor == null) { - return null; - } - return new BinarnoStablo<>(cvor); - } - - protected static Cvor pronadji(Cvor cvor, T element) { - if (cvor == null) { - return null; - } - if (Objects.equals(cvor.element, element)) { - return cvor; - } - Cvor nadjenLevo = pronadji(cvor.levo, element); - if (nadjenLevo != null) { - return nadjenLevo; - } - Cvor nadjenDesno = pronadji(cvor.desno, element); - if (nadjenDesno != null) { - return nadjenDesno; - } - return null; - } - - public boolean ubaci(T roditelj, T potomak, boolean levo) { - return ubaci(koren, roditelj, potomak, levo); - } - - protected static boolean ubaci(Cvor cvor, T roditelj, T potomak, boolean levo) { - cvor = pronadji(cvor, roditelj); - if (cvor == null) { - return false; - } - if (levo) { - if (cvor.levo != null) { - return false; - } - cvor.levo = new Cvor(potomak, null, null); - } else { - if (cvor.desno != null) { - return false; - } - cvor.desno = new Cvor(potomak, null, null); - } - return true; - } - - public BinarnoStablo roditeljOd(T potomak) { - Cvor cvor = roditeljOd(koren, null, potomak); - if (cvor == null) { - return null; - } - return new BinarnoStablo<>(cvor); - } - - protected static Cvor roditeljOd(Cvor cvor, Cvor roditelj, T potomak) { - if (cvor == null) { - return null; - } - if (Objects.equals(cvor.element, potomak)) { - return roditelj; - } - Cvor roditeljLevo = roditeljOd(cvor.levo, cvor, potomak); - if (roditeljLevo != null) { - return roditeljLevo; - } - Cvor roditeljDesno = roditeljOd(cvor.desno, cvor, potomak); - if (roditeljDesno != null) { - return roditeljDesno; - } - return null; - } - - public BinarnoStablo kopija() { - return new BinarnoStablo(kopija(koren)); - } - - protected static Cvor kopija(Cvor cvor) { - if (cvor == null) { - return null; - } - return new Cvor(cvor.element, kopija(cvor.levo), kopija(cvor.desno)); - } - - public BinarnoStablo obrnuto() { - return new BinarnoStablo(obrnuto(koren)); - } - - protected static Cvor obrnuto(Cvor cvor) { - if (cvor == null) { - return null; - } - return new Cvor(cvor.element, obrnuto(cvor.desno), obrnuto(cvor.levo)); - } - - public void stampajPreorder() { - stampajPreorder(koren); - } - protected static void stampajPreorder(Cvor cvor) { - if (cvor == null) { - return; - } - Svetovid.out.println(cvor.element); - stampajPreorder(cvor.levo); - stampajPreorder(cvor.desno); - } - - public void stampajInorder() { - stampajInorder(koren); - } - - protected static void stampajInorder(Cvor cvor) { - if (cvor == null) { - return; - } - stampajInorder(cvor.levo); - Svetovid.out.println(cvor.element); - stampajInorder(cvor.desno); - } - - public void stampajPostorder() { - stampajPostorder(koren); - } - - protected static void stampajPostorder(Cvor cvor) { - if (cvor == null) { - return; - } - stampajPostorder(cvor.levo); - stampajPostorder(cvor.desno); - Svetovid.out.println(cvor.element); - } - - public void stampajListove() { - stampajListove(koren); - } - - protected static void stampajListove(Cvor cvor) { - if (cvor == null) { - return; - } - if ((cvor.levo == null) && (cvor.desno == null)) { - Svetovid.out.println(cvor.element); - } - stampajListove(cvor.levo); - stampajListove(cvor.desno); - } - - public void stampajSveIspod(T element) { - stampajSveIspod(koren, element); - } - - protected static void stampajSveIspod(Cvor cvor, T element) { - Cvor nadjen = pronadji(cvor, element); - if (nadjen != null) { - stampajInorder(nadjen.levo); - stampajInorder(nadjen.desno); - } - } -} - - //definisemo neke komparatore za konkretnu klasu koju cemo - // ubacivati u nase stablo - - class KomparatorPoStarosti implements Comparator { - public int compare(Osoba o1, Osoba o2) { - if (o1 == null && o2 == null) { - return 0; - } - if (o1 == null) { - return 1; - } - if (o2 == null) { - return -1; - } - return o2.getGodinaRodjenja() - o1.getGodinaRodjenja(); - } - } - - class KomparatorPoDuziniPrezimena implements Comparator { - public int compare(Osoba o1, Osoba o2) { - if (o1 == null && o2 == null) { - return 0; - } - if (o1 == null) { - return 1; - } - if (o2 == null) { - return -1; - } - return o2.getPrezime().length() - o1.getPrezime().length(); - } - } - -// Glavna klasa -public class ResenoStabloProgram { - - // Glavni program - public static void main(String[] args) { - - // Kreiramo objekat koji koristimo za ucitavanje i ispisivanje stabla - StabloIOPretty io = new StabloIOPretty<>(Konverter.OSOBA); - - // Ucitamo stablo - BinarnoStablo stablo = io.readStablo(Svetovid.in("Osobe.txt")); - - // Ispisemo ucitano stablo na ekran - Svetovid.out.println("Ucitano stablo:"); - io.printStablo(Svetovid.out, stablo); - Svetovid.out.println(); - - // Ilustrujemo pozive metoda - - int brojElemenata = stablo.brojElemenata(); - Svetovid.out.println(); - Svetovid.out.println("Broj elemenata je ", brojElemenata); - - int brojNivoa = stablo.brojNivoa(); - Svetovid.out.println("Broj nivoa je ", brojNivoa); - - if (stablo.jePrazno()) { - Svetovid.out.println("Stablo je prazno"); - } else { - Svetovid.out.println("Stablo nije prazno"); - } - - Osoba o1 = new Osoba("Lazar", "Lazarevic", 1976); - if (stablo.postojiElement(o1)) { - Svetovid.out.println(o1 + " se nalazi u stablu"); - } else { - Svetovid.out.println(o1 + " se ne nalazi u stablu"); - } - - Osoba najmladji = stablo.min(new KomparatorPoStarosti()); - Svetovid.out.println("Najmladja osoba je " + najmladji); - - Osoba najduzePrezime = stablo.max(new KomparatorPoDuziniPrezimena()); - Svetovid.out.println("Osoba sa najduzim prezimenom je " + najduzePrezime); - - BinarnoStablo podstablo = stablo.pronadji(o1); - if (podstablo != null) { - Svetovid.out.println("Podstablo sa korenom u " + o1 + ":"); - io.printStablo(Svetovid.out, podstablo); - } else { - Svetovid.out.println("Podstablo sa korenom u " + o1 + " je prazno"); - } - - Osoba o2 = new Osoba("Krsta", "Krstic", 1988); - boolean ubacili = stablo.ubaci(o1, o2, true); - if (ubacili) { - Svetovid.out.println("Uspesno smo ubacili " + o2 + ":"); - } else { - Svetovid.out.println("Nismo uspeli da ubacimo novu osobu"); - } - - BinarnoStablo roditelj = stablo.roditeljOd(o1); - if (roditelj != null) { - Svetovid.out.println(o1 + " za roditelja ima " + roditelj); - } else { - Svetovid.out.println(o1 + " nema roditelja"); - } - - BinarnoStablo kopija = stablo.kopija(); - kopija.setLevoPodstablo(null); - BinarnoStablo obrnuto = stablo.obrnuto(); - Svetovid.out.println(); - Svetovid.out.println("Kopija stabla (sa odstranjenim levim podstablom):"); - io.printStablo(Svetovid.out, kopija); - Svetovid.out.println(); - Svetovid.out.println("Obrnuto stablo:"); - io.printStablo(Svetovid.out, obrnuto); - Svetovid.out.println(); - Svetovid.out.println("Originalno stablo:"); - io.printStablo(Svetovid.out, stablo); - - Svetovid.out.println(); - Svetovid.out.println("Preorder:"); - stablo.stampajPreorder(); - - Svetovid.out.println(); - Svetovid.out.println("Inorder:"); - stablo.stampajInorder(); - - Svetovid.out.println(); - Svetovid.out.println("Postorder:"); - stablo.stampajPostorder(); - - Svetovid.out.println(); - Svetovid.out.println("Listovi:"); - stablo.stampajListove(); - - Svetovid.out.println(); - Svetovid.out.println("Svi ispod " + o1 + ":"); - stablo.stampajSveIspod(o1); - - } -} diff --git a/Stabla/StabloOpstegTipa/StabloIOPretty.java b/Stabla/StabloOpstegTipa/StabloIOPretty.java deleted file mode 100644 index 8e286da..0000000 --- a/Stabla/StabloOpstegTipa/StabloIOPretty.java +++ /dev/null @@ -1,223 +0,0 @@ -import java.util.ArrayList; -import java.util.List; -import java.util.regex.Matcher; -import java.util.regex.Pattern; - -import org.svetovid.io.SvetovidReader; -import org.svetovid.io.SvetovidWriter; - -@interface DatoNaVezbama {} - -// Ako bude potrebna, ova klasa ce biti data na testu -@DatoNaVezbama -public class StabloIOPretty { - - protected static final String EMPTY_SYMBOL = " "; - protected static final String RIGHT_SYMBOL = "/"; - protected static final String VERTICAL_SYMBOL = "|"; - protected static final String LEFT_SYMBOL = "\\"; - protected static final String HORIZONTAL_SYMBOL = "-"; - - protected Konverter konverter; - protected String nullSymbol; - protected int separation; - protected int length; - - public StabloIOPretty(Konverter konverter) { - this(konverter, null, 1, 7); - } - - public StabloIOPretty(Konverter konverter, String nullSymbol, int separation, int length) { - this.konverter = konverter; - this.nullSymbol = nullSymbol; - this.separation = separation; - this.length = length; - } - - public Konverter getKonverter() { - return konverter; - } - - public void setKonverter(Konverter konverter) { - this.konverter = konverter; - } - - public String getNullSymbol() { - return nullSymbol; - } - - public void setNullSymbol(String nullSymbol) { - this.nullSymbol = nullSymbol; - } - - public int getSeparation() { - return separation; - } - - public void setSeparation(int separation) { - this.separation = separation; - } - - public int getLength() { - return length; - } - - public void setLength(int length) { - if (length < 3) { - throw new IllegalArgumentException("length"); - } - this.length = length; - } - - public BinarnoStablo readStablo(SvetovidReader in) { - return parseStablo(in, konverter, nullSymbol, length); - } - - protected BinarnoStablo parseStablo(SvetovidReader in, Konverter konverter, String nullSymbol, int length) { - List> elements = new ArrayList<>(); - List levels = new ArrayList<>(); - Pattern levelPattern = Pattern.compile("[\\Q" + LEFT_SYMBOL + HORIZONTAL_SYMBOL + RIGHT_SYMBOL + "\\E]"); - String line = in.readLine(); - while ((line != null) && !line.isEmpty()) { - Matcher matcher = levelPattern.matcher(line); - int level = -1; - if (matcher.find()) { - level = matcher.start(); - } - if (level != -1 && (nullSymbol == null || !line.endsWith(nullSymbol))) { - BinarnoStablo stablo = parseStablo(konverter, line); - elements.add(stablo); - levels.add(level); - } - line = in.readLine(); - } - BinarnoStablo stablo = formStablo(0, elements.size(), levels, elements); - return stablo; - } - - private BinarnoStablo parseStablo(Konverter konverter, String line) { - String vrednost; - int beginIndex = line.indexOf('('); - int endIndex = line.indexOf(')'); - if ((beginIndex != -1) && (endIndex != -1) && (beginIndex < endIndex)) { - vrednost = line.substring(endIndex + 2); - } else { - throw new NumberFormatException(line); - } - T element = konverter.fromString(vrednost); - BinarnoStablo stablo = new BinarnoStablo<>(element); - return stablo; - } - - private BinarnoStablo formStablo(int beginIndex, int endIndex, List levels, List> elements) { - if (beginIndex >= endIndex) { - return null; - } - int minIndex = beginIndex; - int minLevel = levels.get(minIndex); - for (int i = beginIndex + 1; i < endIndex; i++) { - int level = levels.get(i); - if (level < minLevel) { - minLevel = level; - minIndex = i; - } - } - BinarnoStablo stablo = elements.get(minIndex); - BinarnoStablo levo = formStablo(minIndex + 1, endIndex, levels, elements); - BinarnoStablo desno = formStablo(beginIndex, minIndex, levels, elements); - stablo.setLevoPodstablo(levo); - stablo.setDesnoPodstablo(desno); - return stablo; - } - - public void printStablo(SvetovidWriter out, BinarnoStablo stablo) { - StringBuilder builder = new StringBuilder(); - appendTree(builder, stablo, konverter, nullSymbol, separation, length); - out.print(builder.toString()); - } - - protected void appendTree(StringBuilder builder, BinarnoStablo stablo, Konverter konverter, String nullSymbol, int separation, int length) { - String[] buildingBlocks = generateBuildingBlocks(length); - appendRight(builder, stablo, konverter, nullSymbol, separation, buildingBlocks, true, buildingBlocks[5]); - appendNode(builder, stablo, konverter, nullSymbol != null ? nullSymbol : "|", buildingBlocks[4]); - appendLeft(builder, stablo, konverter, nullSymbol, separation, buildingBlocks, false, buildingBlocks[5]); - } - - protected void appendNode(StringBuilder builder, BinarnoStablo stablo, Konverter konverter, String nullSymbol, String prefix) { - builder.append(prefix); - if (stablo == null) { - builder.append(nullSymbol); - } else { - builder.append("(o) "); - String vrednost = konverter.toString(stablo.getElement()); - builder.append(vrednost); - } - builder.append("\n"); - } - - protected void appendRight(StringBuilder builder, BinarnoStablo stablo, Konverter konverter, String nullSymbol, int separation, String[] buildingBlocks, boolean isRight, String prefix) { - if (stablo == null) { - return; - } - if ((nullSymbol != null) || (stablo.getDesnoPodstablo() != null)) { - appendSubtree(builder, stablo.getDesnoPodstablo(), konverter, nullSymbol, separation, buildingBlocks, true, prefix); - for (int i = 0; i < separation; i++) { - appendEmpty(builder, buildingBlocks, prefix); - } - } - } - - protected void appendLeft(StringBuilder builder, BinarnoStablo stablo, Konverter konverter, String nullSymbol, int separation, String[] buildingBlocks, boolean isRight, String prefix) { - if (stablo == null) { - return; - } - if ((nullSymbol != null) || (stablo.getLevoPodstablo() != null)) { - for (int i = 0; i < separation; i++) { - appendEmpty(builder, buildingBlocks, prefix); - } - appendSubtree(builder, stablo.getLevoPodstablo(), konverter, nullSymbol, separation, buildingBlocks, false, prefix); - } - } - - protected void appendEmpty(StringBuilder builder, String[] buildingBlocks, String prefix) { - builder.append(prefix); - builder.append(buildingBlocks[2]); - builder.append("\n"); - } - - protected void appendSubtree(StringBuilder builder, BinarnoStablo stablo, Konverter konverter, String nullSymbol, int separation, String[] buildingBlocks, boolean isRight, String prefix) { - String mojPrefix = prefix; - if (isRight == true) { - mojPrefix = mojPrefix + buildingBlocks[1]; - } - if (isRight == false) { - mojPrefix = mojPrefix + buildingBlocks[3]; - } - String noviPrefix = prefix + (!isRight ? buildingBlocks[2] : buildingBlocks[0]); - appendRight(builder, stablo, konverter, nullSymbol, separation, buildingBlocks, isRight, noviPrefix); - appendNode(builder, stablo, konverter, nullSymbol, mojPrefix); - noviPrefix = prefix + (isRight ? buildingBlocks[2] : buildingBlocks[0]); - appendLeft(builder, stablo, konverter, nullSymbol, separation, buildingBlocks, isRight, noviPrefix); - } - - private String[] generateBuildingBlocks(int length) { - String[] blocks = new String[6]; - blocks[0] = generateBlock(EMPTY_SYMBOL, EMPTY_SYMBOL, EMPTY_SYMBOL, length - 2); - blocks[1] = generateBlock(EMPTY_SYMBOL, RIGHT_SYMBOL, HORIZONTAL_SYMBOL, length - 2); - blocks[2] = generateBlock(EMPTY_SYMBOL, VERTICAL_SYMBOL, EMPTY_SYMBOL, length - 2); - blocks[3] = generateBlock(EMPTY_SYMBOL, LEFT_SYMBOL, HORIZONTAL_SYMBOL, length - 2); - blocks[4] = HORIZONTAL_SYMBOL; - blocks[5] = EMPTY_SYMBOL; - return blocks; - } - - protected String generateBlock(String emptySymbol, String startSymbol, String repeatSymbol, int repeatCount) { - StringBuilder builder = new StringBuilder(); - builder.append(emptySymbol); - builder.append(startSymbol); - for (int i = 0; i < repeatCount; i++) { - builder.append(repeatSymbol); - } - return builder.toString(); - } -} diff --git a/Stabla/StabloOpstegTipa/StabloProgram.java b/Stabla/StabloOpstegTipa/StabloProgram.java deleted file mode 100644 index 2594334..0000000 --- a/Stabla/StabloOpstegTipa/StabloProgram.java +++ /dev/null @@ -1,167 +0,0 @@ -import java.util.NoSuchElementException; -//@interface DatoNaVezbama {} - -// Tip podataka koji sadrzi binarno stablo -class BinarnoStablo { - - // Tip podataka koji opisuje jedan cvor stabla - private static class Cvor { - - T element; - Cvor levo; - Cvor desno; - - Cvor(T element, Cvor levo, Cvor desno) { - this.element = element; - this.levo = levo; - this.desno = desno; - } - } - - // Cvor koji je koren stabla - // Ako je stablo prazno, koren je null - protected Cvor koren; - - // Kreiramo prazno stablo - public BinarnoStablo() { - koren = null; - } - - // Kreiramo stablo sa datim elementom u korenu - // bez levog i desnog podstabla - public BinarnoStablo(T element) { - koren = new Cvor<>(element, null, null); - } - - // Kreiramo novo stablo sa datim elementom u korenu - // i datim levim i desnim podstablom - public BinarnoStablo(T element, BinarnoStablo levo, BinarnoStablo desno) { - koren = new Cvor(element, levo.koren, desno.koren); - } - - // Zasticeni konstruktor za kreiranje novog stabla - // sa korenom u datom cvoru ovog stabla - protected BinarnoStablo(Cvor koren) { - this.koren = koren; - } - - public T getElement() { - if (koren == null) { // Stablo je prazno - throw new NoSuchElementException(); - } - return koren.element; - } - - public void setElement(T element) { - if (koren == null) { // Stablo je prazno - throw new NoSuchElementException(); - } - koren.element = element; - } - - public BinarnoStablo getLevoPodstablo() { - if (koren == null) { // Stablo je prazno - throw new NoSuchElementException(); - } - if (koren.levo == null) { // Nema levog podstabla - return null; - } - return new BinarnoStablo(koren.levo); - } - - public void setLevoPodstablo(BinarnoStablo levo) { - if (koren == null) { // Stablo je prazno - throw new NoSuchElementException(); - } - if (levo == null) { - koren.levo = null; - } else { - koren.levo = levo.koren; - } - } - - public BinarnoStablo getDesnoPodstablo() { - if (koren == null) { // Stablo je prazno - throw new NoSuchElementException(); - } - if (koren.desno == null) { - return null; - } - return new BinarnoStablo(koren.desno); - } - - public void setDesnoPodstablo(BinarnoStablo desno) { - if (koren == null) { // Stablo je prazno - throw new NoSuchElementException(); - } - if (desno == null) { - koren.desno = null; - } else { - koren.desno = desno.koren; - } - } - -// @DatoNaVezbama - public int brojElemenata() { - // Spremimo argumente i pozovemo rekurzivni metod - return brojElemenata(koren); - } - - // @DatoNaVezbama - // Metod koji zapravo resava dati problem - protected static int brojElemenata(Cvor cvor) { - if (cvor == null) { - return 0; - } - int broj = 1; - broj = broj + brojElemenata(cvor.levo); - broj = broj + brojElemenata(cvor.desno); - return broj; - } - - // @DatoNaVezbama - public int brojNivoa() { - // Spremimo argumente i pozovemo rekurzivni metod - return brojNivoa(koren); - } - - @DatoNaVezbama - // 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 StabloProgram { - - // Glavni program - public static void main(String[] args) { - - // Kreiramo objekat koji koristimo za ucitavanje i ispisivanje stabla - StabloIOPretty io = new StabloIOPretty<>(Konverter.OSOBA); - - // Ucitamo stablo - BinarnoStablo stablo = io.readStablo(Svetovid.in("Osobe.txt")); - - // Ispisemo ucitano stablo na ekran - io.printStablo(Svetovid.out, stablo); - Svetovid.out.println(); - - // Ilustrujemo poziv metoda - - int brojElemenata = stablo.brojElemenata(); - Svetovid.out.println("Broj elemenata:", brojElemenata); - - int brojNivoa = stablo.brojNivoa(); - Svetovid.out.println("Broj nivoa:", brojNivoa); - - // TODO Dodati pozive ostalih metoda - - } -} diff --git a/Stabla/StabloOpstegTipa/_zadatak-stabla.txt b/Stabla/StabloOpstegTipa/_zadatak-stabla.txt deleted file mode 100644 index b271547..0000000 --- a/Stabla/StabloOpstegTipa/_zadatak-stabla.txt +++ /dev/null @@ -1,142 +0,0 @@ -************************************************************ - Zadatak - binarna stabla -************************************************************ - -Data je klasa BinarnoStablo koja implementira opste binarno -stablo. Takodje je dat i glavni program koji ucitava jedno -stablo i poziva neke od operacija nad njim. - -Implementirati operacije navedene u nastavku i ilustrovati -njihov rad pozivanjem iz glavnog programa. Svaki metod je -potrebno implementirati kao javan metod klase BinarnoStablo, -uz pomocni zasticen staticki metod istog imena. Pogledati -primer implementacije metoda brojElemenata() i brojNivoa(). - -Sve promene treba raditi u fajlu StabloProgram.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. - - -Metodi -====== - -public boolean jePrazno() -------------------------- - -U klasi BinarnoStablo, implementirati metod koji -vraca true ako je stablo prazno, false ako nije. - -public boolean postojiElement(T element) ----------------------------------------- - -U klasi BinarnoStablo, 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 BinarnoStablo, implementirati metod koji -stampa sve elemente preorder nacinom obilaska. - -public void stampajInOrder() ----------------------------- - -U klasi BinarnoStablo, implementirati metod koji -stampa sve elemente inorder nacinom obilaska. - -public void stampajPostOrder() ----------------------------- - -U klasi BinarnoStablo, implementirati metod koji -stampa sve elemente postorder nacinom obilaska. - -public void stampajListove() ----------------------------- - -U klasi BinarnoStablo, implementirati metod koji -stampa sve elemente koji se nalaze u listovima. - -List je cvor koji nema ni levog ni desnog potomka. - -private Cvor pronadji(T element) ------------------------------------- - -U klasi BinarnoStablo, 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(T element) --------------------------------------- - -U klasi BinarnoStablo, implementirati metod koji -stampa sve elemnte koji su direktni ili indirektni -potomci datog. - - -public boolean ubaci(T roditelj, T potomak, boolean levo) ---------------------------------------------------------- - -U klasi BinarnoStablo, 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 T roditeljOd(T potomak) --------------------------------------- - -U klasi BinarnoStablo, implementirati metod koji -pronalazi i vraca roditelja datog elementa. Ako -je prosledjeni element koren celog stabla -vratiti null. - -public T min(Comparator komparator) -public T max(Comparator komparator) --------------------------------------- - -U klasi BinarnoStablo, implementirati metod koji -pronalazi i vraca najmanji, odnosno najveci, element -stabla. - -Prilikom pretrage koristiti prosledjeni komparator. - - -public BinarnoStablo kopija() -------------------------- - -U klasi BinarnoStablo, implementirati metod koji -vraca kopiju stabla. - -Potrebno je iskopirati i sve cvorove kako izmene -jednog stabla ne bi uticale na drugo. - - -public BinarnoStablo obrnuto() --------------------------- - -U klasi BinarnoStablo, 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.