gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
diff --git a/Stabla/Primeri za test/StabloProgram.java b/Stabla/Primeri za test/StabloProgram.java
+++ /dev/null
@@ -1,242 +0,0 @@
-import java.util.ArrayList;\r
-import java.util.List;\r
-import java.util.Objects;\r
-\r
-// Tip podataka koji predstavlja binarno stablo\r
-// ID svakog cvora je tipa int a vrednost sadrzana u njemu tipa String\r
-// Na velikom testu, studenti ce dobiti ovu klasu\r
-class Stablo {\r
-\r
- private final int id;\r
- private String vrednost;\r
- private Stablo levi;\r
- private Stablo desni;\r
-\r
- public Stablo(int id) {\r
- this(id, null);\r
- }\r
-\r
- public Stablo(int id, String vrednost) {\r
- this(id, vrednost, null, null);\r
- }\r
-\r
- public Stablo(int id, String vrednost, Stablo levi, Stablo desni) {\r
- this.id = id;\r
- this.vrednost = vrednost;\r
- this.levi = levi;\r
- this.desni = desni;\r
- }\r
-\r
- public int getId() {\r
- return id;\r
- }\r
-\r
- public String getVrednost() {\r
- return vrednost;\r
- }\r
-\r
- public void setVrednost(String vrednost) {\r
- this.vrednost = vrednost;\r
- }\r
-\r
- public Stablo getLevi() {\r
- return levi;\r
- }\r
-\r
- public void setLevi(Stablo levi) {\r
- this.levi = levi;\r
- }\r
-\r
- public Stablo getDesni() {\r
- return desni;\r
- }\r
-\r
- public void setDesni(Stablo desni) {\r
- this.desni = desni;\r
- }\r
-\r
- @Override\r
- public String toString() {\r
- return "(" + id + " \"" + vrednost + "\"" + (levi == null ? "" : " " + levi) + (desni == null ? "" : " " + desni) + ")";\r
- }\r
-\r
- @Override\r
- public int hashCode() {\r
- final int prostBroj = 31;\r
- int rezultat = 1;\r
- rezultat = rezultat * prostBroj + id;\r
- rezultat = rezultat * prostBroj + ((vrednost == null) ? 0 : vrednost.hashCode());\r
- rezultat = rezultat * prostBroj + ((levi == null) ? 0 : levi.hashCode());\r
- rezultat = rezultat * prostBroj + ((desni == null) ? 0 : desni.hashCode());\r
- return rezultat;\r
- }\r
-\r
- @Override\r
- public boolean equals(Object obj) {\r
-\r
- // Objekat je jednak ako je identican\r
- if (this == obj) {\r
- return true;\r
- }\r
-\r
- // Null je razlicit od svih objekata\r
- if (obj == null) {\r
- return false;\r
- }\r
-\r
- // Ako su klase objekata razlicite, onda su i objekti razliciti\r
- if (getClass() != obj.getClass()) {\r
- return false;\r
- }\r
-\r
- // Pretvorimo prosledjeni objekat u stablo\r
- Stablo that = (Stablo) obj;\r
-\r
- // Razlicit ID znaci da su objekti razliciti\r
- if (this.id != that.id) {\r
- return false;\r
- }\r
-\r
- // Takodje i vrednost\r
- if (Objects.equals(this.vrednost, that.vrednost)) {\r
- return false;\r
- }\r
-\r
- // Potom levo podstablo\r
- if (Objects.equals(this.levi, that.levi)) {\r
- return false;\r
- }\r
-\r
- // Pa desno podstablo\r
- if (Objects.equals(this.desni, that.desni)) {\r
- return false;\r
- }\r
-\r
- // Sva polja se poklapaju\r
- return true;\r
-\r
- }\r
-}\r
-\r
-// Glavni program\r
-// Na velikom testu ce biti dat kostur koji ucitava potrebno stablo\r
-// Od studenata ce se ocekivati da implementiraju neki algoritam poput\r
-// statickih metoda koje se pozivaju u ovoj klasi\r
-public class StabloProgram {\r
-\r
- public static void main(String[] args) {\r
-\r
- // Ucitavanje stabla iz fajla u "pretty" formatu\r
- // StabloIO inIO = new StabloIOPretty();\r
- // Stablo stablo = inIO.readStablo(Svetovid.in("pretty.txt"));\r
-\r
- // Generisanje random stabla\r
- StabloIO inIO = new StabloIORandom(12345);\r
- Stablo stablo = inIO.readStablo(null);\r
-\r
- // Ispisivanje stabla na ekran\r
- StabloIO outIO = new StabloIOPretty();\r
- outIO.printStablo(Svetovid.out, stablo);\r
- Svetovid.out.println();\r
-\r
- // Broj nivoa\r
- int brojNivoa = brojNivoa(stablo);\r
- Svetovid.out.println("Broj nivoa:", brojNivoa);\r
- Svetovid.out.println();\r
-\r
- // Broj elemenata\r
- int brojElementata = brojElementata(stablo);\r
- Svetovid.out.println("Broj elementata:", brojElementata);\r
- Svetovid.out.println();\r
-\r
- // Najduza String vrednost u stablu\r
- String najduzaVrednost = najduzaVrednost(stablo);\r
- Svetovid.out.println("Najduza vrednost:", najduzaVrednost);\r
- Svetovid.out.println();\r
-\r
- // Svi Putevi od korena do listova\r
- sviPutevi(stablo, new ArrayList<>(brojNivoa));\r
- Svetovid.out.println();\r
-\r
- // Obrnuto stablo\r
- Stablo obrnuto = obrni(stablo);\r
- outIO.printStablo(Svetovid.out, obrnuto);\r
- Svetovid.out.println();\r
-\r
- // Implementacije ovih algoritama su date ispod kao staticki metodi\r
- // Za veliki test, od studenata ce se ocekivati da na isti nacin\r
- // implementiraju algoritam koji se bude trazio u zadatku.\r
- //\r
- // Pored ovde implementiranih algoritama, sledi i par ideja za vezbanje:\r
- // - Ispisati vrednosti cvorova sa parnim IDom\r
- // - Ispisati sve vrednosti cvorova na nivou koji se ucitava sa tastature\r
- // - Utvrditi da li postoji postoji putanja od korena do lista koja sadrzi\r
- // string duzine 5\r
- // - Napraviti novo stablo iste strukture ali sa svim vrednostima ALL CAPS\r
- // - Proveriti da li je dato stablo binarno stablo pretrazivanj, tj. da\r
- // su sve vrednosti u levom podstablu leksikografski pre vrednosti u\r
- // korenu, svi elementi u desnom leksikografski posle, i ovo takodje\r
- // vazi za oba podstabla\r
- // - Koliko ima cvorova na nivou 7\r
- // - Koliko se puta string "abc" javlja u stablu\r
-\r
- }\r
-\r
- // Vraca ukupan broj elemenata u stablu\r
- private static int brojElementata(Stablo stablo) {\r
- if (stablo == null) {\r
- return 0; // Prazno stablo ima 0 elemenata\r
- }\r
- return 1 + brojElementata(stablo.getLevi()) + brojElementata(stablo.getDesni());\r
- }\r
-\r
- // Vraca visinu stabla\r
- private static int brojNivoa(Stablo stablo) {\r
- if (stablo == null) {\r
- return 0; // Prazno stablo je visine 0\r
- }\r
- return 1 + Math.max(brojNivoa(stablo.getLevi()), brojNivoa(stablo.getDesni()));\r
- }\r
-\r
- // Vraca najduzi string sadrzan kao vrednos u nekom od cvorova\r
- private static String najduzaVrednost(Stablo stablo) {\r
- if (stablo == null) {\r
- return null; // Prazno stablo ne sadrzi vrednosti\r
- }\r
- String rezultat = stablo.getVrednost();\r
- String levaVrednost = najduzaVrednost(stablo.getLevi());\r
- String desnaVrednost = najduzaVrednost(stablo.getDesni());\r
- if (rezultat == null || (levaVrednost != null && rezultat.length() < levaVrednost.length())) {\r
- rezultat = levaVrednost;\r
- }\r
- if (rezultat == null || (desnaVrednost != null && rezultat.length() < desnaVrednost.length())) {\r
- rezultat = desnaVrednost;\r
- }\r
- return rezultat;\r
- }\r
-\r
- // Ispisuje sve puteve od korena do listova\r
- private static void sviPutevi(Stablo stablo, List<String> put) {\r
- if (stablo == null) {\r
- return;\r
- }\r
- put.add(stablo.getVrednost());\r
- if ((stablo.getLevi() == null) && (stablo.getDesni() == null)) {\r
- Svetovid.out.println("Put: " + put);\r
- }\r
- sviPutevi(stablo.getLevi(), put);\r
- sviPutevi(stablo.getDesni(), put);\r
- put.remove(put.size() - 1);\r
- }\r
-\r
- // Vraca obrnuto stablo od datog\r
- private static Stablo obrni(Stablo stablo) {\r
- if (stablo == null) {\r
- return null;\r
- }\r
- Stablo levi = obrni(stablo.getLevi());\r
- Stablo desni = obrni(stablo.getDesni());\r
- Stablo obrnuto = new Stablo(stablo.getId(), stablo.getVrednost(), desni, levi);\r
- return obrnuto;\r
- }\r
-}\r