Riešenia (skupina A, 4. týždeň)

import java.util.*;

public class Osoba {
        /**
         * Meno osoby
         */
        private String meno;
        /**
         * Zoznam deti osoby
         */
        private List<Osoba> deti = new ArrayList<Osoba>();

        /**
         * Konstruktor osoby v strome potomkov
         *
         * @param meno
         *            meno osoby
         */
        public Osoba(String meno) {
                this.meno = meno;
        }

        /**
         * Prida osobe dieta
         *
         * @param dieta
         *            referencia na pridavane dieta
         */
        public void pridajDieta(Osoba dieta) {
                deti.add(dieta);
        }

        /**
         * Vrati celkovy pocet potomkov osoby
         */
        public int pocetPotomkov() {
                int pocetPotomkovDeti = 0;
                for (Osoba dieta : deti)
                        pocetPotomkovDeti += dieta.pocetPotomkov();

                return pocetPotomkovDeti + deti.size();
        }

        /**
         * Vypise rodostrom osoby
         */
        public void vypisRodostrom() {
                System.out.println(meno);
                for (Osoba dieta : deti)
                        dieta.vypisRodostrom();
        }

        public int pocetGeneracii() {
                int vysledok = 0;
                for (Osoba dieta : deti) {
                        // int pom = dieta.pocetGeneracii();
                        // if (vysledok < 1 + pom)
                        // vysledok = 1 + pom;

                        vysledok = Math.max(1 + dieta.pocetGeneracii(), vysledok);
                }
                return vysledok;
        }

        public void pridajDoZoznamu(List<Osoba> zoznam) {
                zoznam.add(this);

                for (Osoba dieta: deti)
                        dieta.pridajDoZoznamu(zoznam);
        }

        @Override
        public String toString() {
                return meno;
        }

        /**
         * Main s vytvorenim stromu potomkov pre Janka
         */
        public static void main(String[] args) {
                Osoba janko = new Osoba("Janko");
                Osoba jozko = new Osoba("Jozko");
                Osoba maria = new Osoba("Maria");
                Osoba karol = new Osoba("Karol");
                Osoba lucia = new Osoba("Lucia");
                Osoba petra = new Osoba("Petra");
                janko.pridajDieta(jozko);
                janko.pridajDieta(maria);
                janko.pridajDieta(karol);
                karol.pridajDieta(lucia);
                karol.pridajDieta(petra);
                janko.vypisRodostrom();
                System.out.println(janko.pocetGeneracii());

                List<Osoba> z = new ArrayList<Osoba>();
                janko.pridajDoZoznamu(z);
                System.out.println(z);
        }
}

public class Uzol {
        /**
         * Hodnota ulozena v uzle stromu
         */
        private int hodnota;

        /**
         * Referencia na laveho syna uzla (koren laveho podstromu)
         */
        private Uzol lavy;

        /**
         * Referencia na praveho syna uzla (koren praveho podstromu)
         */
        private Uzol pravy;

        /**
         * Konstruktor uzla binarneho stromu
         *
         * @param hodnota
         * @param lavy
         * @param pravy
         */
        public Uzol(int hodnota, Uzol lavy, Uzol pravy) {
                this.hodnota = hodnota;
                this.lavy = lavy;
                this.pravy = pravy;
        }

        /**
         * Vypise obsah uzlov stromu, ktoreho korenom je tento vrchol. Realizuje
         * preorder prechod.
         */
        public void vypis() {
                // Vypiseme hodnotu
                System.out.println(hodnota);

                // Ak je lavy syn, poziadame ho o vypis hodnot laveho podstromu
                if (lavy != null)
                        lavy.vypis();

                // Ak je pravy syn, poziadame ho o vypis hodnot praveho podstromu
                if (pravy != null)
                        pravy.vypis();
        }

        /**
         * Vrati maximum v strome, ktoreho je tento uzol korenom
         */
        public int maximum() {
                // Predpokladame, ze maximum je hodnota v tomto uzle
                int vysledok = hodnota;

                // Ak je lavy syn, vyberieme bud maximum z laveho podstromu
                // alebo hodnotu v tomto uzle - podla toho, co je vacsie
                if (lavy != null)
                        vysledok = Math.max(vysledok, lavy.maximum());

                // Ak je pravy syn, skusime, ci maximum v pravom podstrome nie je
                // vacsie
                if (pravy != null)
                        vysledok = Math.max(vysledok, pravy.maximum());

                return vysledok;
        }

        /**
         * Zisti, ci sa zadana hodnota nachadza v strome, ktoreho je tento uzol
         * korenom
         *
         * @param hladany
         *            hladana hodnota
         */
        public boolean obsahuje(int hladany) {
                // Ak je hladana hodnota v tomto uzle, koncime ihned
                if (hodnota == hladany)
                        return true;

                // Ak je lavy syn, skusime, ci hladana hodnota nie je v podstrome,
                // ktoreho je lavy syn korenom
                if (lavy != null)
                        if (lavy.obsahuje(hladany))
                                return true;

                // Ak je pravy syn, skusime, ci hladana hodnota nie je v podstrome,
                // ktoreho je pravy syn korenom
                if (pravy != null)
                        if (pravy.obsahuje(hladany))
                                return true;

                return false;
        }

        public int getHodnota() {
                return hodnota;
        }

        public void setHodnota(int hodnota) {
                this.hodnota = hodnota;
        }

        public static Uzol stromZRetazca(String opisStromu) {
                // Zlikvidujeme zbytocne medzery na zaciatku a na konci retazca
                opisStromu = opisStromu.trim();

                // Trivialny pripad - retazec je prazdny
                if (opisStromu.length() == 0)
                        return null;

                // Najdeme, kde zacina koren
                int pocetZatvoriek = 0;

                // Index prveho znaku opisu korena
                int idxZaciatokKorena = 0;
                for (int i = 0; i < opisStromu.length(); i++) {
                        if (opisStromu.charAt(i) == '(') {
                                pocetZatvoriek++;
                                continue;
                        }

                        if (opisStromu.charAt(i) == ')') {
                                pocetZatvoriek--;
                                continue;
                        }

                        if (pocetZatvoriek == 0) {
                                idxZaciatokKorena = i;
                                break;
                        }
                }

                // Index posledneho znaku opisu korena
                int idxKoniecKorena = opisStromu.indexOf('(', idxZaciatokKorena);
                if (idxKoniecKorena == -1)
                        idxKoniecKorena = opisStromu.length() - 1;
                else
                        idxKoniecKorena--;

                // Vyberieme obsah opisu korena
                String obsah = opisStromu.substring(idxZaciatokKorena,
                                idxKoniecKorena + 1).trim();

                // Vyberieme opis laveho a praveho podstromu (specialne riesime,
                // ak opis je prazdny, t.j. neexistuje)
                String lavaCast = "";
                String pravaCast = "";
                if (idxZaciatokKorena > 0)
                        lavaCast = opisStromu.substring(1, idxZaciatokKorena - 1);

                if (idxKoniecKorena != opisStromu.length() - 1)
                        pravaCast = opisStromu.substring(idxKoniecKorena + 2,
                                        opisStromu.length() - 1);

                // Vytvorime koren stromu a vratime referenciu nan
                return new Uzol(Integer.parseInt(obsah), stromZRetazca(lavaCast),
                                stromZRetazca(pravaCast));
        }

        public static void main(String[] args) {
                Uzol korienok = stromZRetazca("((2) 7 ((5) 6 (11))) 2 (5 ((4) 9))");
                korienok.vypis();
                System.out.println(korienok.maximum());
        }
}

public class Uzol {
        /**
         * Hodnota ulozena v uzle stromu
         */
        private int hodnota;

        /**
         * Referencia na laveho syna uzla (koren laveho podstromu)
         */
        private Uzol lavy;

        /**
         * Referencia na praveho syna uzla (koren praveho podstromu)
         */
        private Uzol pravy;

        /**
         * Konstruktor uzla binarneho stromu
         *
         * @param hodnota
         * @param lavy
         * @param pravy
         */
        public Uzol(int hodnota, Uzol lavy, Uzol pravy) {
                this.hodnota = hodnota;
                this.lavy = lavy;
                this.pravy = pravy;
        }

        /**
         * Vypise obsah uzlov stromu, ktoreho korenom je tento vrchol. Realizuje
         * preorder prechod.
         */
        public void vypis() {
                // Vypiseme hodnotu
                System.out.println(hodnota);

                // Ak je lavy syn, poziadame ho o vypis hodnot laveho podstromu
                if (lavy != null)
                        lavy.vypis();

                // Ak je pravy syn, poziadame ho o vypis hodnot praveho podstromu
                if (pravy != null)
                        pravy.vypis();
        }

        /**
         * Vrati maximum v strome, ktoreho je tento uzol korenom
         */
        public int maximum() {
                // Predpokladame, ze maximum je hodnota v tomto uzle
                int vysledok = hodnota;

                // Ak je lavy syn, vyberieme bud maximum z laveho podstromu
                // alebo hodnotu v tomto uzle - podla toho, co je vacsie
                if (lavy != null)
                        vysledok = Math.max(vysledok, lavy.maximum());

                // Ak je pravy syn, skusime, ci maximum v pravom podstrome nie je
                // vacsie
                if (pravy != null)
                        vysledok = Math.max(vysledok, pravy.maximum());

                return vysledok;
        }

        /**
         * Zisti, ci sa zadana hodnota nachadza v strome, ktoreho je tento uzol
         * korenom
         *
         * @param hladany
         *            hladana hodnota
         */
        public boolean obsahuje(int hladany) {
                // Ak je hladana hodnota v tomto uzle, koncime ihned
                if (hodnota == hladany)
                        return true;

                // Ak je lavy syn, skusime, ci hladana hodnota nie je v podstrome,
                // ktoreho je lavy syn korenom
                if (lavy != null)
                        if (lavy.obsahuje(hladany))
                                return true;

                // Ak je pravy syn, skusime, ci hladana hodnota nie je v podstrome,
                // ktoreho je pravy syn korenom
                if (pravy != null)
                        if (pravy.obsahuje(hladany))
                                return true;

                return false;
        }

        public int getHodnota() {
                return hodnota;
        }

        public void setHodnota(int hodnota) {
                this.hodnota = hodnota;
        }

        public int sucet() {
                int sucet = hodnota;
                if (lavy != null) {
                        sucet += lavy.sucet();
                }
                if (pravy != null) {
                        sucet += pravy.sucet();
                }
                return sucet;
        }

        public int vyska() {
                int vysledok = 0;
                if (lavy != null)
                        vysledok = Math.max(1 + lavy.vyska(), vysledok);
                if (pravy != null)
                        vysledok = Math.max(1 + pravy.vyska(), vysledok);

                return vysledok;
        }

        public static Uzol stromZRetazca(String opisStromu) {
                // Zlikvidujeme zbytocne medzery na zaciatku a na konci retazca
                opisStromu = opisStromu.trim();

                // Trivialny pripad - retazec je prazdny
                if (opisStromu.length() == 0)
                        return null;

                // Najdeme, kde zacina koren
                int pocetZatvoriek = 0;

                // Index prveho znaku opisu korena
                int idxZaciatokKorena = 0;
                for (int i = 0; i < opisStromu.length(); i++) {
                        if (opisStromu.charAt(i) == '(') {
                                pocetZatvoriek++;
                                continue;
                        }

                        if (opisStromu.charAt(i) == ')') {
                                pocetZatvoriek--;
                                continue;
                        }

                        if (pocetZatvoriek == 0) {
                                idxZaciatokKorena = i;
                                break;
                        }
                }

                // Index posledneho znaku opisu korena
                int idxKoniecKorena = opisStromu.indexOf('(', idxZaciatokKorena);
                if (idxKoniecKorena == -1)
                        idxKoniecKorena = opisStromu.length() - 1;
                else
                        idxKoniecKorena--;

                // Vyberieme obsah opisu korena
                String obsah = opisStromu.substring(idxZaciatokKorena,
                                idxKoniecKorena + 1).trim();

                // Vyberieme opis laveho a praveho podstromu (specialne riesime,
                // ak opis je prazdny, t.j. neexistuje)
                String lavaCast = "";
                String pravaCast = "";
                if (idxZaciatokKorena > 0)
                        lavaCast = opisStromu.substring(1, idxZaciatokKorena - 1);

                if (idxKoniecKorena != opisStromu.length() - 1)
                        pravaCast = opisStromu.substring(idxKoniecKorena + 2,
                                        opisStromu.length() - 1);

                // Vytvorime koren stromu a vratime referenciu nan
                return new Uzol(Integer.parseInt(obsah), stromZRetazca(lavaCast),
                                stromZRetazca(pravaCast));
        }

        public static void main(String[] args) {
                Uzol korienok = stromZRetazca("((2) 7 ((5) 6 (11))) 2 (5 ((4) 9))");
                korienok.vypis();
                System.out.println(korienok.maximum());
                System.out.println(korienok.sucet());
        }
}