Stabla/StabloOpstegTipa/_zadatak-stabla.txt

   1 ************************************************************
   2          Zadatak - binarna stabla
   3 ************************************************************
   4
   5 Data je klasa BinarnoStablo koja implementira opste binarno
   6 stablo. Takodje je dat i glavni program koji ucitava jedno
   7 stablo i poziva neke od operacija nad njim.
   8
   9 Implementirati operacije navedene u nastavku i ilustrovati
  10 njihov rad pozivanjem iz glavnog programa. Svaki metod je
  11 potrebno implementirati kao javan metod klase BinarnoStablo,
  12 uz pomocni zasticen staticki metod istog imena. Pogledati
  13 primer implementacije metoda brojElemenata() i brojNivoa().
  14
  15 Sve promene treba raditi u fajlu StabloProgram.java u kome
  16 su pomenute klase. Ostali fajlovi su klasa Osoba koja
  17 predstavlja element koji ubacujemo u konkretnom programu,
  18 kao i pomocne klase koje sluze za ucitavanje stabla iz fajla
  19 u urednom formatu. Ucitavanje stabla na ovaj nacin nije
  20 neophodno uciti.
  21
  22
  23 Metodi
  24 ======
  25
  26 public boolean jePrazno()
  27 -------------------------
  28
  29 U klasi BinarnoStablo, implementirati metod koji
  30 vraca true ako je stablo prazno, false ako nije.
  31
  32 public boolean postojiElement(T element)
  33 ----------------------------------------
  34
  35 U klasi BinarnoStablo, implementirati metod koji
  36 vraca true ako se prosledjeni elemnt nalazi u
  37 stablu, false inace.
  38
  39 Prilikom pretrage stabla koristiti metod equals().
  40
  41
  42 public void stampajPreorder()
  43 ----------------------------
  44
  45 U klasi BinarnoStablo, implementirati metod koji
  46 stampa sve elemente preorder nacinom obilaska.
  47
  48 public void stampajInOrder()
  49 ----------------------------
  50
  51 U klasi BinarnoStablo, implementirati metod koji
  52 stampa sve elemente inorder nacinom obilaska.
  53
  54 public void stampajPostOrder()
  55 ----------------------------
  56
  57 U klasi BinarnoStablo, implementirati metod koji
  58 stampa sve elemente postorder nacinom obilaska.
  59
  60 public void stampajListove()
  61 ----------------------------
  62
  63 U klasi BinarnoStablo, implementirati metod koji
  64 stampa sve elemente koji se nalaze u listovima.
  65
  66 List je cvor koji nema ni levog ni desnog potomka.
  67
  68 private Cvor<T> pronadji(T element)
  69 ------------------------------------
  70
  71 U klasi BinarnoStablo, implementirati metod koji
  72 pronalazi dati element i vraca stablo sa korenom
  73 u tom elementu.
  74
  75 Ako element ne postoji u stablu, vratiti null.
  76
  77 Ovaj metod koristiti kao pomocni za sledeci.
  78
  79
  80 public void stampajSveIspod(T element)
  81 --------------------------------------
  82
  83 U klasi BinarnoStablo, implementirati metod koji
  84 stampa sve elemnte koji su direktni ili indirektni
  85 potomci datog.
  86
  87
  88 public boolean ubaci(T roditelj, T potomak, boolean levo)
  89 ---------------------------------------------------------
  90
  91 U klasi BinarnoStablo, implementirati metod koji
  92 pronalazi element dat u prvom argumentu (roditelj)
  93 i kao njegovog poromka ubacuje element dat u drugom
  94 argumentu (potomak). Ako je treci argument (levo)
  95 true tada se element ubacuje kao levi potomak, a
  96 ako je false, kao desni.
  97
  98 Ako se na zeljenom mestu vec nalazi nesto, vratiti false
  99 i ne ubacivati element, inace vratiti true pri uspesnom
 100 ubacivanju.
 101
 102
 103 public T roditeljOd(T potomak)
 104 --------------------------------------
 105
 106 U klasi BinarnoStablo, implementirati metod koji
 107 pronalazi i vraca roditelja datog elementa. Ako
 108 je prosledjeni element koren celog stabla
 109 vratiti null.
 110
 111 public T min(Comparator<T> komparator)
 112 public T max(Comparator<T> komparator)
 113 --------------------------------------
 114
 115 U klasi BinarnoStablo, implementirati metod koji
 116 pronalazi i vraca najmanji, odnosno najveci, element
 117 stabla.
 118
 119 Prilikom pretrage koristiti prosledjeni komparator.
 120
 121
 122 public BinarnoStablo<T> kopija()
 123 -------------------------
 124
 125 U klasi BinarnoStablo, implementirati metod koji
 126 vraca kopiju stabla.
 127
 128 Potrebno je iskopirati i sve cvorove kako izmene
 129 jednog stabla ne bi uticale na drugo.
 130
 131
 132 public BinarnoStablo<T> obrnuto()
 133 --------------------------
 134
 135 U klasi BinarnoStablo, implementirati metod koji
 136 vraca novo stablo nastalo obrtanjem originalng.
 137 Stablo se obrce tako sto se zamene mesta levih
 138 i desnih podstabala koja se pre toga takogje
 139 obrnu.
 140
 141 Posle poziva metoda originalno stablo mora ostati
 142 nepromenjeno.