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
@@ -1,502 +0,0 @@
-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