X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa2-materijali.git;a=blobdiff_plain;f=Stabla%2FPrimeri%20za%20test%2FStabloProgram.java;h=ee70acebeeeff05a36137139d50dad50a5291233;hp=148ce7b3e43cb97bbcda6aa26aac122dd86cad11;hb=8ce9bb7b0e2a94776b901111b90f2070734267d7;hpb=cfa94f3c006a9ca193333a3efca1e48b512f55e8

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