Stabla/StabloOpstegTipa/ResenoStabloProgram.java

   1 import java.util.Comparator;
   2 import java.util.NoSuchElementException;
   3 import java.util.Objects;
   4
   5 // Tip podataka koji sadrzi binarno stablo
   6 class BinarnoStablo<T> {
   7
   8         // Tip podataka koji opisuje jedan cvor stabla
   9         private static class Cvor<T> {
  10
  11                 T element;
  12                 Cvor<T> levo;
  13                 Cvor<T> desno;
  14
  15                 Cvor(T element, Cvor<T> levo, Cvor<T> desno) {
  16                         this.element = element;
  17                         this.levo = levo;
  18                         this.desno = desno;
  19                 }
  20         }
  21
  22         // Cvor koji je koren stabla
  23         // Ako je stablo prazno, koren je null
  24         protected Cvor<T> koren;
  25
  26         // Kreiramo prazno stablo
  27         public BinarnoStablo() {
  28                 koren = null;
  29         }
  30
  31         // Kreiramo stablo sa datim elementom u korenu
  32         // bez levog i desnog podstabla
  33         public BinarnoStablo(T element) {
  34                 koren = new Cvor<>(element, null, null);
  35         }
  36
  37         // Kreiramo novo stablo sa datim elementom u korenu
  38         // i datim levim i desnim podstablom
  39         public BinarnoStablo(T element, BinarnoStablo<T> levo, BinarnoStablo<T> desno) {
  40                 koren = new Cvor<T>(element, levo.koren, desno.koren);
  41         }
  42
  43         // Zasticeni konstruktor za kreiranje novog stabla
  44         // sa korenom u datom cvoru ovog stabla
  45         protected BinarnoStablo(Cvor<T> koren) {
  46                 this.koren = koren;
  47         }
  48
  49         public T getElement() {
  50                 if (koren == null) { // Stablo je prazno
  51                         throw new NoSuchElementException();
  52                 }
  53                 return koren.element;
  54         }
  55
  56         public void setElement(T element) {
  57                 if (koren == null) { // Stablo je prazno
  58                         throw new NoSuchElementException();
  59                 }
  60                 koren.element = element;
  61         }
  62
  63         public BinarnoStablo<T> getLevoPodstablo() {
  64                 if (koren == null) { // Stablo je prazno
  65                         throw new NoSuchElementException();
  66                 }
  67                 if (koren.levo == null) { // Nema levog podstabla
  68                         return null;
  69                 }
  70                 return new BinarnoStablo<T>(koren.levo);
  71         }
  72
  73         public void setLevoPodstablo(BinarnoStablo<T> levo) {
  74                 if (koren == null) { // Stablo je prazno
  75                         throw new NoSuchElementException();
  76                 }
  77                 if (levo == null) {
  78                         koren.levo = null;
  79                 } else {
  80                         koren.levo = levo.koren;
  81                 }
  82         }
  83
  84         public BinarnoStablo<T> getDesnoPodstablo() {
  85                 if (koren == null) { // Stablo je prazno
  86                         throw new NoSuchElementException();
  87                 }
  88                 if (koren.desno == null) {
  89                         return null;
  90                 }
  91                 return new BinarnoStablo<T>(koren.desno);
  92         }
  93
  94         public void setDesnoPodstablo(BinarnoStablo<T> desno) {
  95                 if (koren == null) { // Stablo je prazno
  96                         throw new NoSuchElementException();
  97                 }
  98                 if (desno == null) {
  99                         koren.desno = null;
 100                 } else {
 101                         koren.desno = desno.koren;
 102                 }
 103         }
 104
 105         //DatoNaVezbama
 106         public int brojElemenata() {
 107                 // Spremimo argumente i pozovemo rekurzivni metod
 108                 return brojElemenata(koren);
 109         }
 110
 111         // Metod koji zapravo resava dati problem
 112         //DatoNaVezbama
 113         protected static <T> int brojElemenata(Cvor<T> cvor) {
 114                 if (cvor == null) {
 115                         return 0;
 116                 }
 117                 int broj = 1;
 118                 broj = broj + brojElemenata(cvor.levo);
 119                 broj = broj + brojElemenata(cvor.desno);
 120                 return broj;
 121         }
 122
 123         //DatoNaVezbama
 124         public int brojNivoa() {
 125                 // Spremimo argumente i pozovemo rekurzivni metod
 126                 return brojNivoa(koren);
 127         }
 128
 129         // Metod koji zapravo resava dati problem
 130         //DatoNaVezbama
 131         protected static <T> int brojNivoa(Cvor<T> cvor) {
 132                 if (cvor == null) {
 133                         return 0;
 134                 }
 135                 int brojNivoaLevog = brojNivoa(cvor.levo);
 136                 int brojNivoaDesnog = brojNivoa(cvor.desno);
 137                 return Math.max(brojNivoaLevog, brojNivoaDesnog) + 1;
 138         }
 139
 140         public boolean jePrazno() {
 141                 return koren == null;
 142         }
 143
 144         public boolean postojiElement(T element) {
 145                 return postojiElement(koren, element);
 146         }
 147
 148         protected static <T> boolean postojiElement(Cvor<T> cvor, T element) {
 149                 if (cvor == null) {
 150                         return false;
 151                 }
 152                 if (Objects.equals(cvor.element, element)) {
 153                         return true;
 154                 }
 155                 if (postojiElement(cvor.levo, element)) {
 156                         return true;
 157                 }
 158                 if (postojiElement(cvor.desno, element)) {
 159                         return true;
 160                 }
 161                 return false;
 162         }
 163
 164         public T min(Comparator<T> komparator) {
 165                 return min(koren, komparator);
 166         }
 167
 168         protected static <T> T min(Cvor<T> cvor, Comparator<T> komparator) {
 169                 if (cvor == null) {
 170                         return null;
 171                 }
 172                 T min = cvor.element;
 173                 T levoMin = min(cvor.levo, komparator);
 174                 if (komparator.compare(min, levoMin) > 0) {
 175                         min = levoMin;
 176                 }
 177                 T desnoMin = min(cvor.desno, komparator);
 178                 if (komparator.compare(min, desnoMin) > 0) {
 179                         min = desnoMin;
 180                 }
 181                 return min;
 182         }
 183
 184         public T max(Comparator<T> komparator) {
 185                 return max(koren, komparator);
 186         }
 187
 188         protected static <T> T max(Cvor<T> cvor, Comparator<T> komparator) {
 189                 if (cvor == null) {
 190                         return null;
 191                 }
 192                 T max = cvor.element;
 193                 T levoMax = max(cvor.levo, komparator);
 194                 if (komparator.compare(max, levoMax) > 0) {
 195                         max = levoMax;
 196                 }
 197                 T desnoMax = max(cvor.desno, komparator);
 198                 if (komparator.compare(max, desnoMax) > 0) {
 199                         max = desnoMax;
 200                 }
 201                 return max;
 202         }
 203
 204         public BinarnoStablo<T> pronadji(T element) {
 205                 Cvor<T> cvor = pronadji(koren, element);
 206                 if (cvor == null) {
 207                         return null;
 208                 }
 209                 return new BinarnoStablo<>(cvor);
 210         }
 211
 212         protected static <T> Cvor<T> pronadji(Cvor<T> cvor, T element) {
 213                 if (cvor == null) {
 214                         return null;
 215                 }
 216                 if (Objects.equals(cvor.element, element)) {
 217                         return cvor;
 218                 }
 219                 Cvor<T> nadjenLevo = pronadji(cvor.levo, element);
 220                 if (nadjenLevo != null) {
 221                         return nadjenLevo;
 222                 }
 223                 Cvor<T> nadjenDesno = pronadji(cvor.desno, element);
 224                 if (nadjenDesno != null) {
 225                         return nadjenDesno;
 226                 }
 227                 return null;
 228         }
 229
 230         public boolean ubaci(T roditelj, T potomak, boolean levo) {
 231                 return ubaci(koren, roditelj, potomak, levo);
 232         }
 233
 234         protected static <T> boolean ubaci(Cvor<T> cvor, T roditelj, T potomak, boolean levo) {
 235                 cvor = pronadji(cvor, roditelj);
 236                 if (cvor == null) {
 237                         return false;
 238                 }
 239                 if (levo) {
 240                         if (cvor.levo != null) {
 241                                 return false;
 242                         }
 243                         cvor.levo = new Cvor<T>(potomak, null, null);
 244                 } else {
 245                         if (cvor.desno != null) {
 246                                 return false;
 247                         }
 248                         cvor.desno = new Cvor<T>(potomak, null, null);
 249                 }
 250                 return true;
 251         }
 252
 253         public BinarnoStablo<T> roditeljOd(T potomak) {
 254                 Cvor<T> cvor = roditeljOd(koren, null, potomak);
 255                 if (cvor == null) {
 256                         return null;
 257                 }
 258                 return new BinarnoStablo<>(cvor);
 259         }
 260
 261         protected static <T> Cvor<T> roditeljOd(Cvor<T> cvor, Cvor<T> roditelj, T potomak) {
 262                 if (cvor == null) {
 263                         return null;
 264                 }
 265                 if (Objects.equals(cvor.element, potomak)) {
 266                         return roditelj;
 267                 }
 268                 Cvor<T> roditeljLevo = roditeljOd(cvor.levo, cvor, potomak);
 269                 if (roditeljLevo != null) {
 270                         return roditeljLevo;
 271                 }
 272                 Cvor<T> roditeljDesno = roditeljOd(cvor.desno, cvor, potomak);
 273                 if (roditeljDesno != null) {
 274                         return roditeljDesno;
 275                 }
 276                 return null;
 277         }
 278
 279         public BinarnoStablo<T> kopija() {
 280                 return new BinarnoStablo<T>(kopija(koren));
 281         }
 282
 283         protected static <T> Cvor<T> kopija(Cvor<T> cvor) {
 284                 if (cvor == null) {
 285                         return null;
 286                 }
 287                 return new Cvor<T>(cvor.element, kopija(cvor.levo), kopija(cvor.desno));
 288         }
 289
 290         public BinarnoStablo<T> obrnuto() {
 291                 return new BinarnoStablo<T>(obrnuto(koren));
 292         }
 293
 294         protected static <T> Cvor<T> obrnuto(Cvor<T> cvor) {
 295                 if (cvor == null) {
 296                         return null;
 297                 }
 298                 return new Cvor<T>(cvor.element, obrnuto(cvor.desno), obrnuto(cvor.levo));
 299         }
 300
 301         public void stampajPreorder() {
 302                 stampajPreorder(koren);
 303         }
 304         protected static <T> void stampajPreorder(Cvor<T> cvor) {
 305                 if (cvor == null) {
 306                         return;
 307                 }
 308                 Svetovid.out.println(cvor.element);
 309                 stampajPreorder(cvor.levo);
 310                 stampajPreorder(cvor.desno);
 311         }
 312
 313         public void stampajInorder() {
 314                 stampajInorder(koren);
 315         }
 316
 317         protected static <T> void stampajInorder(Cvor<T> cvor) {
 318                 if (cvor == null) {
 319                         return;
 320                 }
 321                 stampajInorder(cvor.levo);
 322                 Svetovid.out.println(cvor.element);
 323                 stampajInorder(cvor.desno);
 324         }
 325
 326         public void stampajPostorder() {
 327                 stampajPostorder(koren);
 328         }
 329
 330         protected static <T> void stampajPostorder(Cvor<T> cvor) {
 331                 if (cvor == null) {
 332                         return;
 333                 }
 334                 stampajPostorder(cvor.levo);
 335                 stampajPostorder(cvor.desno);
 336                 Svetovid.out.println(cvor.element);
 337         }
 338
 339         public void stampajListove() {
 340                 stampajListove(koren);
 341         }
 342
 343         protected static <T> void stampajListove(Cvor<T> cvor) {
 344                 if (cvor == null) {
 345                         return;
 346                 }
 347                 if ((cvor.levo == null) && (cvor.desno == null)) {
 348                         Svetovid.out.println(cvor.element);
 349                 }
 350                 stampajListove(cvor.levo);
 351                 stampajListove(cvor.desno);
 352         }
 353
 354         public void stampajSveIspod(T element) {
 355                 stampajSveIspod(koren, element);
 356         }
 357
 358         protected static <T> void stampajSveIspod(Cvor<T> cvor, T element) {
 359                 Cvor<T> nadjen = pronadji(cvor, element);
 360                 if (nadjen != null) {
 361                         stampajInorder(nadjen.levo);
 362                         stampajInorder(nadjen.desno);
 363                 }
 364         }
 365 }
 366
 367         //definisemo neke komparatore za konkretnu klasu koju cemo
 368         // ubacivati u nase stablo
 369
 370         class KomparatorPoStarosti implements Comparator<Osoba> {
 371                 public int compare(Osoba o1, Osoba o2) {
 372                         if (o1 == null && o2 == null) {
 373                                 return 0;
 374                         }
 375                         if (o1 == null) {
 376                                 return 1;
 377                         }
 378                         if (o2 == null) {
 379                                 return -1;
 380                         }
 381                         return o2.getGodinaRodjenja() - o1.getGodinaRodjenja();
 382                 }
 383         }
 384
 385         class KomparatorPoDuziniPrezimena implements Comparator<Osoba> {
 386                 public int compare(Osoba o1, Osoba o2) {
 387                         if (o1 == null && o2 == null) {
 388                                 return 0;
 389                         }
 390                         if (o1 == null) {
 391                                 return 1;
 392                         }
 393                         if (o2 == null) {
 394                                 return -1;
 395                         }
 396                         return o2.getPrezime().length() - o1.getPrezime().length();
 397                 }
 398         }
 399
 400 // Glavna klasa
 401 public class ResenoStabloProgram {
 402
 403         // Glavni program
 404         public static void main(String[] args) {
 405
 406                 // Kreiramo objekat koji koristimo za ucitavanje i ispisivanje stabla
 407                 StabloIOPretty<Osoba> io = new StabloIOPretty<>(Konverter.OSOBA);
 408
 409                 // Ucitamo stablo
 410                 BinarnoStablo<Osoba> stablo = io.readStablo(Svetovid.in("Osobe.txt"));
 411
 412                 // Ispisemo ucitano stablo na ekran
 413                 Svetovid.out.println("Ucitano stablo:");
 414                 io.printStablo(Svetovid.out, stablo);
 415                 Svetovid.out.println();
 416
 417                 // Ilustrujemo pozive metoda
 418
 419                 int brojElemenata = stablo.brojElemenata();
 420                 Svetovid.out.println();
 421                 Svetovid.out.println("Broj elemenata je ", brojElemenata);
 422
 423                 int brojNivoa = stablo.brojNivoa();
 424                 Svetovid.out.println("Broj nivoa je ", brojNivoa);
 425
 426                 if (stablo.jePrazno()) {
 427                         Svetovid.out.println("Stablo je prazno");
 428                 } else {
 429                         Svetovid.out.println("Stablo nije prazno");
 430                 }
 431
 432                 Osoba o1 = new Osoba("Lazar", "Lazarevic", 1976);
 433                 if (stablo.postojiElement(o1)) {
 434                         Svetovid.out.println(o1 + " se nalazi u stablu");
 435                 } else {
 436                         Svetovid.out.println(o1 + " se ne nalazi u stablu");
 437                 }
 438
 439                 Osoba najmladji = stablo.min(new KomparatorPoStarosti());
 440                 Svetovid.out.println("Najmladja osoba je " + najmladji);
 441
 442                 Osoba najduzePrezime = stablo.max(new KomparatorPoDuziniPrezimena());
 443                 Svetovid.out.println("Osoba sa najduzim prezimenom je " + najduzePrezime);
 444
 445                 BinarnoStablo<Osoba> podstablo = stablo.pronadji(o1);
 446                 if (podstablo != null) {
 447                         Svetovid.out.println("Podstablo sa korenom u " + o1 + ":");
 448                         io.printStablo(Svetovid.out, podstablo);
 449                 } else {
 450                         Svetovid.out.println("Podstablo sa korenom u " + o1 + " je prazno");
 451                 }
 452
 453                 Osoba o2 = new Osoba("Krsta", "Krstic", 1988);
 454                 boolean ubacili = stablo.ubaci(o1, o2, true);
 455                 if (ubacili) {
 456                         Svetovid.out.println("Uspesno smo ubacili " + o2 + ":");
 457                 } else {
 458                         Svetovid.out.println("Nismo uspeli da ubacimo novu osobu");
 459                 }
 460
 461                 BinarnoStablo<Osoba> roditelj = stablo.roditeljOd(o1);
 462                 if (roditelj != null) {
 463                         Svetovid.out.println(o1 + " za roditelja ima " + roditelj);
 464                 } else {
 465                         Svetovid.out.println(o1 + " nema roditelja");
 466                 }
 467
 468                 BinarnoStablo<Osoba> kopija = stablo.kopija();
 469                 kopija.setLevoPodstablo(null);
 470                 BinarnoStablo<Osoba> obrnuto = stablo.obrnuto();
 471                 Svetovid.out.println();
 472                 Svetovid.out.println("Kopija stabla (sa odstranjenim levim podstablom):");
 473                 io.printStablo(Svetovid.out, kopija);
 474                 Svetovid.out.println();
 475                 Svetovid.out.println("Obrnuto stablo:");
 476                 io.printStablo(Svetovid.out, obrnuto);
 477                 Svetovid.out.println();
 478                 Svetovid.out.println("Originalno stablo:");
 479                 io.printStablo(Svetovid.out, stablo);
 480
 481                 Svetovid.out.println();
 482                 Svetovid.out.println("Preorder:");
 483                 stablo.stampajPreorder();
 484
 485                 Svetovid.out.println();
 486                 Svetovid.out.println("Inorder:");
 487                 stablo.stampajInorder();
 488
 489                 Svetovid.out.println();
 490                 Svetovid.out.println("Postorder:");
 491                 stablo.stampajPostorder();
 492
 493                 Svetovid.out.println();
 494                 Svetovid.out.println("Listovi:");
 495                 stablo.stampajListove();
 496
 497                 Svetovid.out.println();
 498                 Svetovid.out.println("Svi ispod " + o1 + ":");
 499                 stablo.stampajSveIspod(o1);
 500
 501         }
 502 }