Stabla/StabloOpstegTipa/StabloProgram.java

   1 import java.util.NoSuchElementException;
   2 //@interface DatoNaVezbama {}
   3
   4 // Tip podataka koji sadrzi binarno stablo
   5 class BinarnoStablo<T> {
   6
   7         // Tip podataka koji opisuje jedan cvor stabla
   8         private static class Cvor<T> {
   9
  10                 T element;
  11                 Cvor<T> levo;
  12                 Cvor<T> desno;
  13
  14                 Cvor(T element, Cvor<T> levo, Cvor<T> desno) {
  15                         this.element = element;
  16                         this.levo = levo;
  17                         this.desno = desno;
  18                 }
  19         }
  20
  21         // Cvor koji je koren stabla
  22         // Ako je stablo prazno, koren je null
  23         protected Cvor<T> koren;
  24
  25         // Kreiramo prazno stablo
  26         public BinarnoStablo() {
  27                 koren = null;
  28         }
  29
  30         // Kreiramo stablo sa datim elementom u korenu
  31         // bez levog i desnog podstabla
  32         public BinarnoStablo(T element) {
  33                 koren = new Cvor<>(element, null, null);
  34         }
  35
  36         // Kreiramo novo stablo sa datim elementom u korenu
  37         // i datim levim i desnim podstablom
  38         public BinarnoStablo(T element, BinarnoStablo<T> levo, BinarnoStablo<T> desno) {
  39                 koren = new Cvor<T>(element, levo.koren, desno.koren);
  40         }
  41
  42         // Zasticeni konstruktor za kreiranje novog stabla
  43         // sa korenom u datom cvoru ovog stabla
  44         protected BinarnoStablo(Cvor<T> koren) {
  45                 this.koren = koren;
  46         }
  47
  48         public T getElement() {
  49                 if (koren == null) { // Stablo je prazno
  50                         throw new NoSuchElementException();
  51                 }
  52                 return koren.element;
  53         }
  54
  55         public void setElement(T element) {
  56                 if (koren == null) { // Stablo je prazno
  57                         throw new NoSuchElementException();
  58                 }
  59                 koren.element = element;
  60         }
  61
  62         public BinarnoStablo<T> getLevoPodstablo() {
  63                 if (koren == null) { // Stablo je prazno
  64                         throw new NoSuchElementException();
  65                 }
  66                 if (koren.levo == null) { // Nema levog podstabla
  67                         return null;
  68                 }
  69                 return new BinarnoStablo<T>(koren.levo);
  70         }
  71
  72         public void setLevoPodstablo(BinarnoStablo<T> levo) {
  73                 if (koren == null) { // Stablo je prazno
  74                         throw new NoSuchElementException();
  75                 }
  76                 if (levo == null) {
  77                         koren.levo = null;
  78                 } else {
  79                         koren.levo = levo.koren;
  80                 }
  81         }
  82
  83         public BinarnoStablo<T> getDesnoPodstablo() {
  84                 if (koren == null) { // Stablo je prazno
  85                         throw new NoSuchElementException();
  86                 }
  87                 if (koren.desno == null) {
  88                         return null;
  89                 }
  90                 return new BinarnoStablo<T>(koren.desno);
  91         }
  92
  93         public void setDesnoPodstablo(BinarnoStablo<T> desno) {
  94                 if (koren == null) { // Stablo je prazno
  95                         throw new NoSuchElementException();
  96                 }
  97                 if (desno == null) {
  98                         koren.desno = null;
  99                 } else {
 100                         koren.desno = desno.koren;
 101                 }
 102         }
 103
 104 //    @DatoNaVezbama
 105         public int brojElemenata() {
 106         // Spremimo argumente i pozovemo rekurzivni metod
 107         return brojElemenata(koren);
 108         }
 109
 110   //  @DatoNaVezbama
 111     // Metod koji zapravo resava dati problem
 112     protected static <T> int brojElemenata(Cvor<T> cvor) {
 113         if (cvor == null) {
 114                 return 0;
 115         }
 116                 int broj = 1;
 117                 broj = broj + brojElemenata(cvor.levo);
 118                 broj = broj + brojElemenata(cvor.desno);
 119                 return broj;
 120     }
 121
 122  //   @DatoNaVezbama
 123         public int brojNivoa() {
 124         // Spremimo argumente i pozovemo rekurzivni metod
 125         return brojNivoa(koren);
 126         }
 127
 128    @DatoNaVezbama
 129     // Metod koji zapravo resava dati problem
 130         protected static int brojNivoa(Cvor cvor) {
 131         if (cvor == null) {
 132                 return 0;
 133         }
 134                 int brojNivoaLevog = brojNivoa(cvor.levo);
 135                 int brojNivoaDesnog = brojNivoa(cvor.desno);
 136                 return Math.max(brojNivoaLevog, brojNivoaDesnog) + 1;
 137         }
 138 }
 139
 140 // Glavna klasa
 141 public class StabloProgram {
 142
 143         // Glavni program
 144         public static void main(String[] args) {
 145
 146                 // Kreiramo objekat koji koristimo za ucitavanje i ispisivanje stabla
 147                 StabloIOPretty<Osoba> io = new StabloIOPretty<>(Konverter.OSOBA);
 148
 149                 // Ucitamo stablo
 150                 BinarnoStablo<Osoba> stablo = io.readStablo(Svetovid.in("Osobe.txt"));
 151
 152                 // Ispisemo ucitano stablo na ekran
 153                 io.printStablo(Svetovid.out, stablo);
 154                 Svetovid.out.println();
 155
 156                 // Ilustrujemo poziv metoda
 157
 158                 int brojElemenata = stablo.brojElemenata();
 159                 Svetovid.out.println("Broj elemenata:", brojElemenata);
 160
 161                 int brojNivoa = stablo.brojNivoa();
 162                 Svetovid.out.println("Broj nivoa:", brojNivoa);
 163
 164                 // TODO Dodati pozive ostalih metoda
 165
 166         }
 167 }