gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
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
- public final int id;\r
- public String vrednost;\r
- public Stablo levi;\r
- public Stablo desni;\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
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\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
Svetovid.out.println("Broj nivoa:", brojNivoa);\r
Svetovid.out.println();\r
\r
- // Broj nivoa\r
+ // Broj elemenata\r
int brojElementata = brojElementata(stablo);\r
Svetovid.out.println("Broj elementata:", brojElementata);\r
Svetovid.out.println();\r
\r
- // Broj nivoa\r
+ // Najduza String vrednost u stablu\r
String najduzaVrednost = najduzaVrednost(stablo);\r
Svetovid.out.println("Najduza vrednost:", najduzaVrednost);\r
Svetovid.out.println();\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;\r
+ return 0; // Prazno stablo ima 0 elemenata\r
}\r
- return 1 + brojElementata(stablo.levi) + brojElementata(stablo.desni);\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;\r
+ return 0; // Prazno stablo je visine 0\r
}\r
- return 1 + Math.max(brojNivoa(stablo.levi), brojNivoa(stablo.desni));\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;\r
+ return null; // Prazno stablo ne sadrzi vrednosti\r
}\r
- String rezultat = stablo.vrednost;\r
- String levaVrednost = najduzaVrednost(stablo.levi);\r
- String desnaVrednost = najduzaVrednost(stablo.desni);\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
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.vrednost);\r
- if ((stablo.levi == null) && (stablo.desni == null)) {\r
+ put.add(stablo.getVrednost());\r
+ if ((stablo.getLevi() == null) && (stablo.getDesni() == null)) {\r
Svetovid.out.println("Put: " + put);\r
}\r
- sviPutevi(stablo.levi, put);\r
- sviPutevi(stablo.desni, put);\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.levi);\r
- Stablo desni = obrni(stablo.desni);\r
- Stablo obrnuto = new Stablo(stablo.id, stablo.vrednost, desni, levi);\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