gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
diff --git a/Stabla/StabloOpstegTipa/ResenoStabloProgram.java b/Stabla/StabloOpstegTipa/ResenoStabloProgram.java
--- /dev/null
@@ -0,0 +1,502 @@
+import java.util.Comparator;\r
+import java.util.NoSuchElementException;\r
+import java.util.Objects;\r
+\r
+// Tip podataka koji sadrzi binarno stablo\r
+class BinarnoStablo<T> {\r
+\r
+ // Tip podataka koji opisuje jedan cvor stabla\r
+ private static class Cvor<T> {\r
+ \r
+ T element;\r
+ Cvor<T> levo;\r
+ Cvor<T> desno;\r
+\r
+ Cvor(T element, Cvor<T> levo, Cvor<T> desno) {\r
+ this.element = element;\r
+ this.levo = levo;\r
+ this.desno = desno;\r
+ }\r
+ }\r
+\r
+ // Cvor koji je koren stabla\r
+ // Ako je stablo prazno, koren je null\r
+ protected Cvor<T> koren;\r
+\r
+ // Kreiramo prazno stablo\r
+ public BinarnoStablo() {\r
+ koren = null;\r
+ }\r
+\r
+ // Kreiramo stablo sa datim elementom u korenu\r
+ // bez levog i desnog podstabla\r
+ public BinarnoStablo(T element) {\r
+ koren = new Cvor<>(element, null, null);\r
+ }\r
+\r
+ // Kreiramo novo stablo sa datim elementom u korenu\r
+ // i datim levim i desnim podstablom\r
+ public BinarnoStablo(T element, BinarnoStablo<T> levo, BinarnoStablo<T> desno) {\r
+ koren = new Cvor<T>(element, levo.koren, desno.koren);\r
+ }\r
+\r
+ // Zasticeni konstruktor za kreiranje novog stabla\r
+ // sa korenom u datom cvoru ovog stabla\r
+ protected BinarnoStablo(Cvor<T> koren) {\r
+ this.koren = koren;\r
+ }\r
+\r
+ public T getElement() {\r
+ if (koren == null) { // Stablo je prazno\r
+ throw new NoSuchElementException();\r
+ }\r
+ return koren.element;\r
+ }\r
+\r
+ public void setElement(T element) {\r
+ if (koren == null) { // Stablo je prazno\r
+ throw new NoSuchElementException();\r
+ }\r
+ koren.element = element;\r
+ }\r
+\r
+ public BinarnoStablo<T> getLevoPodstablo() {\r
+ if (koren == null) { // Stablo je prazno\r
+ throw new NoSuchElementException();\r
+ }\r
+ if (koren.levo == null) { // Nema levog podstabla\r
+ return null;\r
+ }\r
+ return new BinarnoStablo<T>(koren.levo);\r
+ }\r
+\r
+ public void setLevoPodstablo(BinarnoStablo<T> levo) {\r
+ if (koren == null) { // Stablo je prazno\r
+ throw new NoSuchElementException();\r
+ }\r
+ if (levo == null) {\r
+ koren.levo = null;\r
+ } else {\r
+ koren.levo = levo.koren;\r
+ }\r
+ }\r
+\r
+ public BinarnoStablo<T> getDesnoPodstablo() {\r
+ if (koren == null) { // Stablo je prazno\r
+ throw new NoSuchElementException();\r
+ }\r
+ if (koren.desno == null) {\r
+ return null;\r
+ }\r
+ return new BinarnoStablo<T>(koren.desno);\r
+ }\r
+\r
+ public void setDesnoPodstablo(BinarnoStablo<T> desno) {\r
+ if (koren == null) { // Stablo je prazno\r
+ throw new NoSuchElementException();\r
+ }\r
+ if (desno == null) {\r
+ koren.desno = null;\r
+ } else {\r
+ koren.desno = desno.koren;\r
+ }\r
+ }\r
+\r
+ //DatoNaVezbama\r
+ public int brojElemenata() {\r
+ // Spremimo argumente i pozovemo rekurzivni metod\r
+ return brojElemenata(koren);\r
+ }\r
+\r
+ // Metod koji zapravo resava dati problem\r
+ //DatoNaVezbama\r
+ protected static <T> int brojElemenata(Cvor<T> cvor) {\r
+ if (cvor == null) {\r
+ return 0;\r
+ }\r
+ int broj = 1;\r
+ broj = broj + brojElemenata(cvor.levo);\r
+ broj = broj + brojElemenata(cvor.desno);\r
+ return broj;\r
+ }\r
+\r
+ //DatoNaVezbama\r
+ public int brojNivoa() {\r
+ // Spremimo argumente i pozovemo rekurzivni metod\r
+ return brojNivoa(koren);\r
+ }\r
+\r
+ // Metod koji zapravo resava dati problem\r
+ //DatoNaVezbama\r
+ protected static <T> int brojNivoa(Cvor<T> cvor) {\r
+ if (cvor == null) {\r
+ return 0;\r
+ }\r
+ int brojNivoaLevog = brojNivoa(cvor.levo);\r
+ int brojNivoaDesnog = brojNivoa(cvor.desno);\r
+ return Math.max(brojNivoaLevog, brojNivoaDesnog) + 1;\r
+ }\r
+\r
+ public boolean jePrazno() {\r
+ return koren == null;\r
+ }\r
+\r
+ public boolean postojiElement(T element) {\r
+ return postojiElement(koren, element);\r
+ }\r
+ \r
+ protected static <T> boolean postojiElement(Cvor<T> cvor, T element) {\r
+ if (cvor == null) {\r
+ return false;\r
+ }\r
+ if (Objects.equals(cvor.element, element)) {\r
+ return true;\r
+ }\r
+ if (postojiElement(cvor.levo, element)) {\r
+ return true;\r
+ }\r
+ if (postojiElement(cvor.desno, element)) {\r
+ return true;\r
+ }\r
+ return false;\r
+ }\r
+\r
+ public T min(Comparator<T> komparator) {\r
+ return min(koren, komparator);\r
+ }\r
+\r
+ protected static <T> T min(Cvor<T> cvor, Comparator<T> komparator) {\r
+ if (cvor == null) {\r
+ return null;\r
+ }\r
+ T min = cvor.element;\r
+ T levoMin = min(cvor.levo, komparator);\r
+ if (komparator.compare(min, levoMin) > 0) {\r
+ min = levoMin;\r
+ }\r
+ T desnoMin = min(cvor.desno, komparator);\r
+ if (komparator.compare(min, desnoMin) > 0) {\r
+ min = desnoMin;\r
+ }\r
+ return min;\r
+ }\r
+ \r
+ public T max(Comparator<T> komparator) {\r
+ return max(koren, komparator);\r
+ }\r
+\r
+ protected static <T> T max(Cvor<T> cvor, Comparator<T> komparator) {\r
+ if (cvor == null) {\r
+ return null;\r
+ }\r
+ T max = cvor.element;\r
+ T levoMax = max(cvor.levo, komparator);\r
+ if (komparator.compare(max, levoMax) > 0) {\r
+ max = levoMax;\r
+ }\r
+ T desnoMax = max(cvor.desno, komparator);\r
+ if (komparator.compare(max, desnoMax) > 0) {\r
+ max = desnoMax;\r
+ }\r
+ return max;\r
+ }\r
+\r
+ public BinarnoStablo<T> pronadji(T element) {\r
+ Cvor<T> cvor = pronadji(koren, element);\r
+ if (cvor == null) {\r
+ return null;\r
+ }\r
+ return new BinarnoStablo<>(cvor);\r
+ }\r
+\r
+ protected static <T> Cvor<T> pronadji(Cvor<T> cvor, T element) {\r
+ if (cvor == null) {\r
+ return null;\r
+ }\r
+ if (Objects.equals(cvor.element, element)) {\r
+ return cvor;\r
+ }\r
+ Cvor<T> nadjenLevo = pronadji(cvor.levo, element);\r
+ if (nadjenLevo != null) {\r
+ return nadjenLevo;\r
+ }\r
+ Cvor<T> nadjenDesno = pronadji(cvor.desno, element);\r
+ if (nadjenDesno != null) {\r
+ return nadjenDesno;\r
+ }\r
+ return null;\r
+ }\r
+\r
+ public boolean ubaci(T roditelj, T potomak, boolean levo) {\r
+ return ubaci(koren, roditelj, potomak, levo);\r
+ }\r
+\r
+ protected static <T> boolean ubaci(Cvor<T> cvor, T roditelj, T potomak, boolean levo) {\r
+ cvor = pronadji(cvor, roditelj);\r
+ if (cvor == null) {\r
+ return false;\r
+ }\r
+ if (levo) {\r
+ if (cvor.levo != null) {\r
+ return false;\r
+ }\r
+ cvor.levo = new Cvor<T>(potomak, null, null);\r
+ } else {\r
+ if (cvor.desno != null) {\r
+ return false;\r
+ }\r
+ cvor.desno = new Cvor<T>(potomak, null, null);\r
+ }\r
+ return true;\r
+ }\r
+\r
+ public BinarnoStablo<T> roditeljOd(T potomak) {\r
+ Cvor<T> cvor = roditeljOd(koren, null, potomak);\r
+ if (cvor == null) {\r
+ return null;\r
+ }\r
+ return new BinarnoStablo<>(cvor);\r
+ }\r
+ \r
+ protected static <T> Cvor<T> roditeljOd(Cvor<T> cvor, Cvor<T> roditelj, T potomak) {\r
+ if (cvor == null) {\r
+ return null;\r
+ }\r
+ if (Objects.equals(cvor.element, potomak)) {\r
+ return roditelj;\r
+ }\r
+ Cvor<T> roditeljLevo = roditeljOd(cvor.levo, cvor, potomak);\r
+ if (roditeljLevo != null) {\r
+ return roditeljLevo;\r
+ }\r
+ Cvor<T> roditeljDesno = roditeljOd(cvor.desno, cvor, potomak);\r
+ if (roditeljDesno != null) {\r
+ return roditeljDesno;\r
+ }\r
+ return null;\r
+ }\r
+\r
+ public BinarnoStablo<T> kopija() {\r
+ return new BinarnoStablo<T>(kopija(koren));\r
+ }\r
+\r
+ protected static <T> Cvor<T> kopija(Cvor<T> cvor) {\r
+ if (cvor == null) {\r
+ return null;\r
+ }\r
+ return new Cvor<T>(cvor.element, kopija(cvor.levo), kopija(cvor.desno));\r
+ }\r
+\r
+ public BinarnoStablo<T> obrnuto() {\r
+ return new BinarnoStablo<T>(obrnuto(koren));\r
+ }\r
+\r
+ protected static <T> Cvor<T> obrnuto(Cvor<T> cvor) {\r
+ if (cvor == null) {\r
+ return null;\r
+ }\r
+ return new Cvor<T>(cvor.element, obrnuto(cvor.desno), obrnuto(cvor.levo));\r
+ }\r
+\r
+ public void stampajPreorder() {\r
+ stampajPreorder(koren);\r
+ }\r
+ protected static <T> void stampajPreorder(Cvor<T> cvor) {\r
+ if (cvor == null) {\r
+ return;\r
+ }\r
+ Svetovid.out.println(cvor.element);\r
+ stampajPreorder(cvor.levo);\r
+ stampajPreorder(cvor.desno);\r
+ }\r
+\r
+ public void stampajInorder() {\r
+ stampajInorder(koren);\r
+ }\r
+ \r
+ protected static <T> void stampajInorder(Cvor<T> cvor) {\r
+ if (cvor == null) {\r
+ return;\r
+ }\r
+ stampajInorder(cvor.levo);\r
+ Svetovid.out.println(cvor.element);\r
+ stampajInorder(cvor.desno);\r
+ }\r
+ \r
+ public void stampajPostorder() {\r
+ stampajPostorder(koren);\r
+ }\r
+ \r
+ protected static <T> void stampajPostorder(Cvor<T> cvor) {\r
+ if (cvor == null) {\r
+ return;\r
+ }\r
+ stampajPostorder(cvor.levo);\r
+ stampajPostorder(cvor.desno);\r
+ Svetovid.out.println(cvor.element);\r
+ }\r
+ \r
+ public void stampajListove() {\r
+ stampajListove(koren);\r
+ }\r
+ \r
+ protected static <T> void stampajListove(Cvor<T> cvor) {\r
+ if (cvor == null) {\r
+ return;\r
+ }\r
+ if ((cvor.levo == null) && (cvor.desno == null)) {\r
+ Svetovid.out.println(cvor.element);\r
+ }\r
+ stampajListove(cvor.levo);\r
+ stampajListove(cvor.desno);\r
+ }\r
+ \r
+ public void stampajSveIspod(T element) {\r
+ stampajSveIspod(koren, element);\r
+ }\r
+ \r
+ protected static <T> void stampajSveIspod(Cvor<T> cvor, T element) {\r
+ Cvor<T> nadjen = pronadji(cvor, element);\r
+ if (nadjen != null) {\r
+ stampajInorder(nadjen.levo);\r
+ stampajInorder(nadjen.desno);\r
+ }\r
+ }\r
+}\r
+\r
+ //definisemo neke komparatore za konkretnu klasu koju cemo\r
+ // ubacivati u nase stablo\r
+\r
+ class KomparatorPoStarosti implements Comparator<Osoba> {\r
+ public int compare(Osoba o1, Osoba o2) {\r
+ if (o1 == null && o2 == null) {\r
+ return 0;\r
+ }\r
+ if (o1 == null) {\r
+ return 1;\r
+ }\r
+ if (o2 == null) {\r
+ return -1;\r
+ }\r
+ return o2.getGodinaRodjenja() - o1.getGodinaRodjenja();\r
+ }\r
+ }\r
+ \r
+ class KomparatorPoDuziniPrezimena implements Comparator<Osoba> {\r
+ public int compare(Osoba o1, Osoba o2) {\r
+ if (o1 == null && o2 == null) {\r
+ return 0;\r
+ }\r
+ if (o1 == null) {\r
+ return 1;\r
+ }\r
+ if (o2 == null) {\r
+ return -1;\r
+ }\r
+ return o2.getPrezime().length() - o1.getPrezime().length();\r
+ }\r
+ }\r
+\r
+// Glavna klasa\r
+public class ResenoStabloProgram {\r
+\r
+ // Glavni program\r
+ public static void main(String[] args) {\r
+\r
+ // Kreiramo objekat koji koristimo za ucitavanje i ispisivanje stabla\r
+ StabloIOPretty<Osoba> io = new StabloIOPretty<>(Konverter.OSOBA);\r
+\r
+ // Ucitamo stablo\r
+ BinarnoStablo<Osoba> stablo = io.readStablo(Svetovid.in("Osobe.txt"));\r
+\r
+ // Ispisemo ucitano stablo na ekran\r
+ Svetovid.out.println("Ucitano stablo:");\r
+ io.printStablo(Svetovid.out, stablo);\r
+ Svetovid.out.println();\r
+\r
+ // Ilustrujemo pozive metoda\r
+ \r
+ int brojElemenata = stablo.brojElemenata();\r
+ Svetovid.out.println();\r
+ Svetovid.out.println("Broj elemenata je ", brojElemenata);\r
+ \r
+ int brojNivoa = stablo.brojNivoa();\r
+ Svetovid.out.println("Broj nivoa je ", brojNivoa);\r
+\r
+ if (stablo.jePrazno()) {\r
+ Svetovid.out.println("Stablo je prazno");\r
+ } else {\r
+ Svetovid.out.println("Stablo nije prazno");\r
+ }\r
+ \r
+ Osoba o1 = new Osoba("Lazar", "Lazarevic", 1976);\r
+ if (stablo.postojiElement(o1)) {\r
+ Svetovid.out.println(o1 + " se nalazi u stablu");\r
+ } else {\r
+ Svetovid.out.println(o1 + " se ne nalazi u stablu");\r
+ }\r
+\r
+ Osoba najmladji = stablo.min(new KomparatorPoStarosti());\r
+ Svetovid.out.println("Najmladja osoba je " + najmladji);\r
+\r
+ Osoba najduzePrezime = stablo.max(new KomparatorPoDuziniPrezimena());\r
+ Svetovid.out.println("Osoba sa najduzim prezimenom je " + najduzePrezime);\r
+\r
+ BinarnoStablo<Osoba> podstablo = stablo.pronadji(o1);\r
+ if (podstablo != null) {\r
+ Svetovid.out.println("Podstablo sa korenom u " + o1 + ":");\r
+ io.printStablo(Svetovid.out, podstablo);\r
+ } else {\r
+ Svetovid.out.println("Podstablo sa korenom u " + o1 + " je prazno");\r
+ }\r
+\r
+ Osoba o2 = new Osoba("Krsta", "Krstic", 1988);\r
+ boolean ubacili = stablo.ubaci(o1, o2, true);\r
+ if (ubacili) {\r
+ Svetovid.out.println("Uspesno smo ubacili " + o2 + ":");\r
+ } else {\r
+ Svetovid.out.println("Nismo uspeli da ubacimo novu osobu");\r
+ }\r
+\r
+ BinarnoStablo<Osoba> roditelj = stablo.roditeljOd(o1);\r
+ if (roditelj != null) {\r
+ Svetovid.out.println(o1 + " za roditelja ima " + roditelj);\r
+ } else {\r
+ Svetovid.out.println(o1 + " nema roditelja");\r
+ }\r
+\r
+ BinarnoStablo<Osoba> kopija = stablo.kopija();\r
+ kopija.setLevoPodstablo(null);\r
+ BinarnoStablo<Osoba> obrnuto = stablo.obrnuto();\r
+ Svetovid.out.println();\r
+ Svetovid.out.println("Kopija stabla (sa odstranjenim levim podstablom):");\r
+ io.printStablo(Svetovid.out, kopija);\r
+ Svetovid.out.println();\r
+ Svetovid.out.println("Obrnuto stablo:");\r
+ io.printStablo(Svetovid.out, obrnuto);\r
+ Svetovid.out.println();\r
+ Svetovid.out.println("Originalno stablo:");\r
+ io.printStablo(Svetovid.out, stablo);\r
+\r
+ Svetovid.out.println();\r
+ Svetovid.out.println("Preorder:");\r
+ stablo.stampajPreorder();\r
+\r
+ Svetovid.out.println();\r
+ Svetovid.out.println("Inorder:");\r
+ stablo.stampajInorder();\r
+\r
+ Svetovid.out.println();\r
+ Svetovid.out.println("Postorder:");\r
+ stablo.stampajPostorder();\r
+\r
+ Svetovid.out.println();\r
+ Svetovid.out.println("Listovi:");\r
+ stablo.stampajListove();\r
+\r
+ Svetovid.out.println();\r
+ Svetovid.out.println("Svi ispod " + o1 + ":");\r
+ stablo.stampajSveIspod(o1);\r
+\r
+ }\r
+}\r