gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under
the git version control system
1 import java
.util
.Comparator
;
2 import java
.util
.NoSuchElementException
;
3 import java
.util
.Objects
;
5 // Tip podataka koji sadrzi binarno stablo
6 class BinarnoStablo
<T
> {
8 // Tip podataka koji opisuje jedan cvor stabla
9 private static class Cvor
<T
> {
15 Cvor(T element
, Cvor
<T
> levo
, Cvor
<T
> desno
) {
16 this.element
= element
;
22 // Cvor koji je koren stabla
23 // Ako je stablo prazno, koren je null
24 protected Cvor
<T
> koren
;
26 // Kreiramo prazno stablo
27 public BinarnoStablo() {
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);
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
);
43 // Zasticeni konstruktor za kreiranje novog stabla
44 // sa korenom u datom cvoru ovog stabla
45 protected BinarnoStablo(Cvor
<T
> koren
) {
49 public T
getElement() {
50 if (koren
== null) { // Stablo je prazno
51 throw new NoSuchElementException();
56 public void setElement(T element
) {
57 if (koren
== null) { // Stablo je prazno
58 throw new NoSuchElementException();
60 koren
.element
= element
;
63 public BinarnoStablo
<T
> getLevoPodstablo() {
64 if (koren
== null) { // Stablo je prazno
65 throw new NoSuchElementException();
67 if (koren
.levo
== null) { // Nema levog podstabla
70 return new BinarnoStablo
<T
>(koren
.levo
);
73 public void setLevoPodstablo(BinarnoStablo
<T
> levo
) {
74 if (koren
== null) { // Stablo je prazno
75 throw new NoSuchElementException();
80 koren
.levo
= levo
.koren
;
84 public BinarnoStablo
<T
> getDesnoPodstablo() {
85 if (koren
== null) { // Stablo je prazno
86 throw new NoSuchElementException();
88 if (koren
.desno
== null) {
91 return new BinarnoStablo
<T
>(koren
.desno
);
94 public void setDesnoPodstablo(BinarnoStablo
<T
> desno
) {
95 if (koren
== null) { // Stablo je prazno
96 throw new NoSuchElementException();
101 koren
.desno
= desno
.koren
;
106 public int brojElemenata() {
107 // Spremimo argumente i pozovemo rekurzivni metod
108 return brojElemenata(koren
);
111 // Metod koji zapravo resava dati problem
113 protected static <T
> int brojElemenata(Cvor
<T
> cvor
) {
118 broj
= broj
+ brojElemenata(cvor
.levo
);
119 broj
= broj
+ brojElemenata(cvor
.desno
);
124 public int brojNivoa() {
125 // Spremimo argumente i pozovemo rekurzivni metod
126 return brojNivoa(koren
);
129 // Metod koji zapravo resava dati problem
131 protected static <T
> int brojNivoa(Cvor
<T
> cvor
) {
135 int brojNivoaLevog
= brojNivoa(cvor
.levo
);
136 int brojNivoaDesnog
= brojNivoa(cvor
.desno
);
137 return Math
.max(brojNivoaLevog
, brojNivoaDesnog
) + 1;
140 public boolean jePrazno() {
141 return koren
== null;
144 public boolean postojiElement(T element
) {
145 return postojiElement(koren
, element
);
148 protected static <T
> boolean postojiElement(Cvor
<T
> cvor
, T element
) {
152 if (Objects
.equals(cvor
.element
, element
)) {
155 if (postojiElement(cvor
.levo
, element
)) {
158 if (postojiElement(cvor
.desno
, element
)) {
164 public T
min(Comparator
<T
> komparator
) {
165 return min(koren
, komparator
);
168 protected static <T
> T
min(Cvor
<T
> cvor
, Comparator
<T
> komparator
) {
172 T min
= cvor
.element
;
173 T levoMin
= min(cvor
.levo
, komparator
);
174 if (komparator
.compare(min
, levoMin
) > 0) {
177 T desnoMin
= min(cvor
.desno
, komparator
);
178 if (komparator
.compare(min
, desnoMin
) > 0) {
184 public T
max(Comparator
<T
> komparator
) {
185 return max(koren
, komparator
);
188 protected static <T
> T
max(Cvor
<T
> cvor
, Comparator
<T
> komparator
) {
192 T max
= cvor
.element
;
193 T levoMax
= max(cvor
.levo
, komparator
);
194 if (komparator
.compare(max
, levoMax
) > 0) {
197 T desnoMax
= max(cvor
.desno
, komparator
);
198 if (komparator
.compare(max
, desnoMax
) > 0) {
204 public BinarnoStablo
<T
> pronadji(T element
) {
205 Cvor
<T
> cvor
= pronadji(koren
, element
);
209 return new BinarnoStablo
<>(cvor
);
212 protected static <T
> Cvor
<T
> pronadji(Cvor
<T
> cvor
, T element
) {
216 if (Objects
.equals(cvor
.element
, element
)) {
219 Cvor
<T
> nadjenLevo
= pronadji(cvor
.levo
, element
);
220 if (nadjenLevo
!= null) {
223 Cvor
<T
> nadjenDesno
= pronadji(cvor
.desno
, element
);
224 if (nadjenDesno
!= null) {
230 public boolean ubaci(T roditelj
, T potomak
, boolean levo
) {
231 return ubaci(koren
, roditelj
, potomak
, levo
);
234 protected static <T
> boolean ubaci(Cvor
<T
> cvor
, T roditelj
, T potomak
, boolean levo
) {
235 cvor
= pronadji(cvor
, roditelj
);
240 if (cvor
.levo
!= null) {
243 cvor
.levo
= new Cvor
<T
>(potomak
, null, null);
245 if (cvor
.desno
!= null) {
248 cvor
.desno
= new Cvor
<T
>(potomak
, null, null);
253 public BinarnoStablo
<T
> roditeljOd(T potomak
) {
254 Cvor
<T
> cvor
= roditeljOd(koren
, null, potomak
);
258 return new BinarnoStablo
<>(cvor
);
261 protected static <T
> Cvor
<T
> roditeljOd(Cvor
<T
> cvor
, Cvor
<T
> roditelj
, T potomak
) {
265 if (Objects
.equals(cvor
.element
, potomak
)) {
268 Cvor
<T
> roditeljLevo
= roditeljOd(cvor
.levo
, cvor
, potomak
);
269 if (roditeljLevo
!= null) {
272 Cvor
<T
> roditeljDesno
= roditeljOd(cvor
.desno
, cvor
, potomak
);
273 if (roditeljDesno
!= null) {
274 return roditeljDesno
;
279 public BinarnoStablo
<T
> kopija() {
280 return new BinarnoStablo
<T
>(kopija(koren
));
283 protected static <T
> Cvor
<T
> kopija(Cvor
<T
> cvor
) {
287 return new Cvor
<T
>(cvor
.element
, kopija(cvor
.levo
), kopija(cvor
.desno
));
290 public BinarnoStablo
<T
> obrnuto() {
291 return new BinarnoStablo
<T
>(obrnuto(koren
));
294 protected static <T
> Cvor
<T
> obrnuto(Cvor
<T
> cvor
) {
298 return new Cvor
<T
>(cvor
.element
, obrnuto(cvor
.desno
), obrnuto(cvor
.levo
));
301 public void stampajPreorder() {
302 stampajPreorder(koren
);
304 protected static <T
> void stampajPreorder(Cvor
<T
> cvor
) {
308 Svetovid
.out
.println(cvor
.element
);
309 stampajPreorder(cvor
.levo
);
310 stampajPreorder(cvor
.desno
);
313 public void stampajInorder() {
314 stampajInorder(koren
);
317 protected static <T
> void stampajInorder(Cvor
<T
> cvor
) {
321 stampajInorder(cvor
.levo
);
322 Svetovid
.out
.println(cvor
.element
);
323 stampajInorder(cvor
.desno
);
326 public void stampajPostorder() {
327 stampajPostorder(koren
);
330 protected static <T
> void stampajPostorder(Cvor
<T
> cvor
) {
334 stampajPostorder(cvor
.levo
);
335 stampajPostorder(cvor
.desno
);
336 Svetovid
.out
.println(cvor
.element
);
339 public void stampajListove() {
340 stampajListove(koren
);
343 protected static <T
> void stampajListove(Cvor
<T
> cvor
) {
347 if ((cvor
.levo
== null) && (cvor
.desno
== null)) {
348 Svetovid
.out
.println(cvor
.element
);
350 stampajListove(cvor
.levo
);
351 stampajListove(cvor
.desno
);
354 public void stampajSveIspod(T element
) {
355 stampajSveIspod(koren
, element
);
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
);
367 //definisemo neke komparatore za konkretnu klasu koju cemo
368 // ubacivati u nase stablo
370 class KomparatorPoStarosti
implements Comparator
<Osoba
> {
371 public int compare(Osoba o1
, Osoba o2
) {
372 if (o1
== null && o2
== null) {
381 return o2
.getGodinaRodjenja() - o1
.getGodinaRodjenja();
385 class KomparatorPoDuziniPrezimena
implements Comparator
<Osoba
> {
386 public int compare(Osoba o1
, Osoba o2
) {
387 if (o1
== null && o2
== null) {
396 return o2
.getPrezime().length() - o1
.getPrezime().length();
401 public class ResenoStabloProgram
{
404 public static void main(String
[] args
) {
406 // Kreiramo objekat koji koristimo za ucitavanje i ispisivanje stabla
407 StabloIOPretty
<Osoba
> io
= new StabloIOPretty
<>(Konverter
.OSOBA
);
410 BinarnoStablo
<Osoba
> stablo
= io
.readStablo(Svetovid
.in("Osobe.txt"));
412 // Ispisemo ucitano stablo na ekran
413 Svetovid
.out
.println("Ucitano stablo:");
414 io
.printStablo(Svetovid
.out
, stablo
);
415 Svetovid
.out
.println();
417 // Ilustrujemo pozive metoda
419 int brojElemenata
= stablo
.brojElemenata();
420 Svetovid
.out
.println();
421 Svetovid
.out
.println("Broj elemenata je ", brojElemenata
);
423 int brojNivoa
= stablo
.brojNivoa();
424 Svetovid
.out
.println("Broj nivoa je ", brojNivoa
);
426 if (stablo
.jePrazno()) {
427 Svetovid
.out
.println("Stablo je prazno");
429 Svetovid
.out
.println("Stablo nije prazno");
432 Osoba o1
= new Osoba("Lazar", "Lazarevic", 1976);
433 if (stablo
.postojiElement(o1
)) {
434 Svetovid
.out
.println(o1
+ " se nalazi u stablu");
436 Svetovid
.out
.println(o1
+ " se ne nalazi u stablu");
439 Osoba najmladji
= stablo
.min(new KomparatorPoStarosti());
440 Svetovid
.out
.println("Najmladja osoba je " + najmladji
);
442 Osoba najduzePrezime
= stablo
.max(new KomparatorPoDuziniPrezimena());
443 Svetovid
.out
.println("Osoba sa najduzim prezimenom je " + najduzePrezime
);
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
);
450 Svetovid
.out
.println("Podstablo sa korenom u " + o1
+ " je prazno");
453 Osoba o2
= new Osoba("Krsta", "Krstic", 1988);
454 boolean ubacili
= stablo
.ubaci(o1
, o2
, true);
456 Svetovid
.out
.println("Uspesno smo ubacili " + o2
+ ":");
458 Svetovid
.out
.println("Nismo uspeli da ubacimo novu osobu");
461 BinarnoStablo
<Osoba
> roditelj
= stablo
.roditeljOd(o1
);
462 if (roditelj
!= null) {
463 Svetovid
.out
.println(o1
+ " za roditelja ima " + roditelj
);
465 Svetovid
.out
.println(o1
+ " nema roditelja");
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
);
481 Svetovid
.out
.println();
482 Svetovid
.out
.println("Preorder:");
483 stablo
.stampajPreorder();
485 Svetovid
.out
.println();
486 Svetovid
.out
.println("Inorder:");
487 stablo
.stampajInorder();
489 Svetovid
.out
.println();
490 Svetovid
.out
.println("Postorder:");
491 stablo
.stampajPostorder();
493 Svetovid
.out
.println();
494 Svetovid
.out
.println("Listovi:");
495 stablo
.stampajListove();
497 Svetovid
.out
.println();
498 Svetovid
.out
.println("Svi ispod " + o1
+ ":");
499 stablo
.stampajSveIspod(o1
);
Svarog.pmf.uns.ac.rs/gitweb
maintanance
Doni Pracner