4. sada domácich zadaní

Najneskorší termín odovzdania: 19.3.2012 (pondelok) 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ý

Najdlhšia rodová línia (3 body)

V triede Osoba implementujte metódu najdlhsiaRodovaLinia, ktorá pre zadaný uzol vráti najdlhšiu možnú líniu potomkov danej osoby.

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 List<Osoba> najdlhsiaRodovaLinia() {
                // Riesenie?
        }
}
[$[Get Code]]

V strome uvedenom vyššie sú 3 najdlhšie rodové línie:

  • Janko, Mária, Ondrej, Kristína
  • Janko, Mária, Ondrej, Anna
  • Janko, Mária, Ondrej, Eva

Vyvážené stromy? (3 body)

Do triedy Uzol pridajte metódu jeVyvazeny, ktorá vráti, či strom, ktorého koreňom je daný uzol, je uzlovo vyvážený. Povieme, že strom je uzlovo vyvážený, ak (1) počet prvkov uložených v ľavom a pravom podstrome sa líši nanajvýš o 1 a (2) ľavý a pravý podstrom daného uzla sú vyvážené.

public boolean jeVyvazeny();
[$[Get Code]]

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);
[$[Get Code]]

Inorder BVS (2 body)

Z cvičení viete, že postupnosť uzlov binárneho vyhľadávacieho stromu pri inorder prechode tvorí usporiadanú postupnosť. Teda nasledujúce tvrdenie platí: Ak T je BVS, potom jeho postupnosť inorder prechodu je usporiadaná. Platí však aj opačné tvrdenie? Teda je pravda, že ak postupnosť inorder prechodu je usporiadaná, potom T je BVS?

Dokážte alebo vyvráťte: Ak postupnosť inorder prechodu je usporiadaná (=rastúca), potom T je BVS.

V prípade, že toto tvrdenie nie je pravdivé uveďte kontrapríklad - nájdite taký binárny strom, ktorý nie je BVS, no jeho postupnosť inorder prechodu je usporiadaná. Ak je tvrdenie pravdivé, formálne ho dokážte (napríklad indukciou na dĺžku postupnosti inorder prechodu).

Riešenie tejto úlohy odovzdajte najneskôr do začiatku cvičení 20.3.2012 svojmu cvičiacemu.

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();
        }
}
[$[Get Code]]