4. sada domácich zadaní
Najneskorší termín odovzdania: 17.3.2013 (nedeľa) o 21:00
Odovzdávané súbory: Osoba.java, Uzol.java
Doplňujúce požiadavky:
- riešenia, ktoré nebude možné skompilovať (t.j. riešenia so syntaktickými chybami) nebudú hodnotené,
- zdrojový kód správne naformátujte (CTRL+SHIFT+F),
- komentovaný zdrojový kód je vítaný
Potomkovia s viac deťmi (2 body)
V triede Osoba implementujte metódu pocetPotomkovSViacDetmi, ktorá pre zadaný uzol vráti počet všetkých potomkov tejto osoby, ktorí mali aspoň zadaný počet detí.
import java.util.*;
public class Osoba {
private String meno;
private List<Osoba> deti = new ArrayList<Osoba>();
public Osoba(String meno) {
this.meno = meno;
}
public void pridajDieta(Osoba dieta) {
deti.add(dieta);
}
public int pocetPotomkovSViacDetmi(int pocetDeti) {
// Riesenie?
}
}
public class Osoba {
private String meno;
private List<Osoba> deti = new ArrayList<Osoba>();
public Osoba(String meno) {
this.meno = meno;
}
public void pridajDieta(Osoba dieta) {
deti.add(dieta);
}
public int pocetPotomkovSViacDetmi(int pocetDeti) {
// Riesenie?
}
}
Úplný strom? (3 body)
Do triedy Uzol pridajte metódu jeUplny(), ktorá vráti, či strom, ktorého koreňom je daný uzol, je úplný. Povieme, že binárny strom je úplný, ak:
- všetky uzly, ktoré nie sú listy, majú práve 2 deti,
- všetky listy v strome sú na tej istej úrovni.
public boolean jeUplny();
Binárne vyhľadávacie stromy (3 body)
Do triedy Uzol pridajte statickú metódu vytvorBVS, ktorá vráti referenciu na novovytvorený koreňový uzol binárneho vyhľadávacieho stromu naplného zadanými hodnotami. Vytvorený binárny strom musí mať zároveň minimálnu možnú výšku.
public static Uzol vytvorBVS(Set<Integer> hodnoty);
Trieda Uzol:
public class Uzol {
private int hodnota;
private Uzol lavy;
private Uzol pravy;
public Uzol(int hodnota, Uzol lavy, Uzol pravy) {
this.hodnota = hodnota;
this.lavy = lavy;
this.pravy = pravy;
}
public int getHodnota() {
return hodnota;
}
public void setHodnota(int hodnota) {
this.hodnota = hodnota;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (lavy != null)
sb.append("(" + lavy.toString() + ") ");
sb.append(hodnota);
if (pravy != null)
sb.append(" (" + pravy.toString() + ")");
return sb.toString();
}
}
private int hodnota;
private Uzol lavy;
private Uzol pravy;
public Uzol(int hodnota, Uzol lavy, Uzol pravy) {
this.hodnota = hodnota;
this.lavy = lavy;
this.pravy = pravy;
}
public int getHodnota() {
return hodnota;
}
public void setHodnota(int hodnota) {
this.hodnota = hodnota;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (lavy != null)
sb.append("(" + lavy.toString() + ") ");
sb.append(hodnota);
if (pravy != null)
sb.append(" (" + pravy.toString() + ")");
return sb.toString();
}
}