C4

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 pocetGeneracii = 0;
                for (Osoba dieta : deti) {
                        pocetGeneracii = Math.max(pocetGeneracii, dieta.pocetGeneracii());
//                              int p = dieta.pocetGeneracii();
//                              if (p > pocetGeneracii) {
//                                      pocetGeneracii = p;
//                              }
                        }

                return pocetGeneracii + 1;
        }

        public void pridajDoZoznamu(List<Osoba> zoznam) {
                zoznam.add(this);
                for (Osoba dieta : deti)
                        dieta.pridajDoZoznamu(zoznam);
        }

        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(petra.pocetGeneracii());
                System.out.println(janko.pocetGeneracii());

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

/**
 * Trieda reprezentujuca uzol binarneho stromu
 */
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) {
                int pocitadloZatvoriek = 0;
                int poziciaLavej = 0;
                String lavy = null;
                String pravy = null;
                int hodnota = 0;
                StringBuilder sb = new StringBuilder();

                if (opisStromu.charAt(0) == '(') {
                        pocitadloZatvoriek++;
                        for (int i = 1; i < opisStromu.length(); i++) {
                                if (opisStromu.charAt(i) == '(')
                                        pocitadloZatvoriek++;
                                if (opisStromu.charAt(i) == ')')
                                        pocitadloZatvoriek--;
                                if (pocitadloZatvoriek == 0) {
                                        lavy = opisStromu.substring(1, i);
                                        poziciaLavej = i + 2;
                                        break;
                                }
                        }
                }

                for (int i = poziciaLavej; i < opisStromu.length(); i++) {
                        if (opisStromu.charAt(i) == ' ') {
                                pravy = opisStromu.substring(i + 2, opisStromu.length() - 1);
                                break;
                        }
                        sb.append(opisStromu.charAt(i));
                }
                hodnota = Integer.parseInt(sb.toString());

                if (lavy == null && pravy == null)
                        return new Uzol(hodnota, null, null);

                if (lavy == null)
                        return new Uzol(hodnota, null, stromZRetazca(pravy));

                if (pravy == null)
                        return new Uzol(hodnota, stromZRetazca(lavy), null);

                return new Uzol(hodnota, stromZRetazca(lavy), stromZRetazca(pravy));
        }

        public int minimum() {
                // Predpokladame, ze minimum je hodnota v tomto uzle
                int vysledok = hodnota;

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

                // Ak je pravy syn, skusime, ci minimum v pravom podstrome nie je
                // mensie
                if (pravy != null)
                        vysledok = Math.min(vysledok, pravy.minimum());

                return vysledok;
        }

        public int vyskaStromu() {
                int vyska = 0;

                if (lavy != null)
                        vyska = Math.max(vyska, lavy.vyskaStromu());

                if (pravy != null)
                        vyska = Math.max(vyska, pravy.vyskaStromu());

                return vyska + 1;
        }

        public static void main(String[] args) {
                Uzol koren = new Uzol(5, new Uzol(2, new Uzol(8, null, null), null),
                                new Uzol(9, null, null));
                koren.vypis();
                System.out.println("Maximum je " + koren.maximum());
                System.out.println("Minimum je " + koren.minimum());

                String s = "((2) 7 ((5) 6 (11))) 2 (5 ((4) 9))";
                Uzol u = stromZRetazca(s);
                u.vypis();
                System.out.println("Vyska stromu je" + u.vyskaStromu());
        }
}

/**
 * Trieda reprezentujuca uzol binarneho stromu
 */
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;
        }

        public int pocetUzlov(){
                int pocet = 1;

                if (lavy != null)pocet+=lavy.pocetUzlov();
                if (pravy != null)pocet+=pravy.pocetUzlov();

                return pocet;
        }

        public int vyskaStromu(){
                int vyskaL = 0;
                int vyskaP = 0;

                if (lavy != null)
                        vyskaL = lavy.vyskaStromu();

                if (pravy != null)
                        vyskaP = pravy.vyskaStromu();

                if (lavy == null && pravy == null)
                        return 0;

                return Math.max(vyskaL, vyskaP)+1;
        }

        public void preorderVypis(){
                System.out.print(this.hodnota + " ");

                if(lavy != null)
                        lavy.preorderVypis();

                if(pravy != null)
                        pravy.preorderVypis();
        }
        public void inorderVypis(){
                if(lavy != null)
                        lavy.inorderVypis();
                System.out.print(this.hodnota + " ");
                if(pravy != null)
                        pravy.inorderVypis();



        }
        public void postorderVypis(){
                if(lavy != null)
                        lavy.postorderVypis();

                if(pravy != null)
                        pravy.postorderVypis();

                System.out.print(this.hodnota + " ");
        }


        public int minimum() {
            // 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.min(vysledok, lavy.minimum());

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

            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 sucetHodnot(){
                int sucet=hodnota;

                if (lavy!=null)
                   sucet+= lavy.sucetHodnot();

                if (pravy!=null)
                   sucet+= pravy.sucetHodnot();

            return sucet;
        }

        public int getHodnota() {
                return hodnota;
        }

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

        public static void main(String[] args) {
                Uzol koren = new Uzol(5, new Uzol(2, new Uzol(8, null, null), null), new Uzol(9, null, null));
                koren.vypis();
                System.out.println("Maximum je " + koren.maximum());
                System.out.println("Minimum je " + koren.minimum());
                System.out.println("Pocet uzlov:" + koren.pocetUzlov());
                System.out.println("Vyska stromu je:" + koren.vyskaStromu());
               /* koren.preorderVypis();
                System.out.println();
                koren.inorderVypis();
                System.out.println();
                koren.postorderVypis();*/
                System.out.println("Sucet hodnot je: "+koren.sucetHodnot());
        }
}