Riešenia (skupina D, 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();
        }

        /**
         * Vypise pocet generacii
         */
        int pocet = 0;
        int maxPocet = 0;

        public int pocetGeneracii() {
                if (deti == null) {
                        return 1;
                }

                for (Osoba dieta : deti)
                        pocet = 1 + dieta.pocetGeneracii();

                if (pocet > maxPocet)
                        maxPocet = pocet;

                return maxPocet;
        }

        public int pocetGeneracii2() {
                int maxPocet2 = 0;
                if (deti == null) {
                        return 1;
                }

                for (Osoba dieta : deti)
                        if (maxPocet2 < dieta.pocetGeneracii2())
                                maxPocet = pocet;

                return maxPocet;
        }

        /*
         * pocet generacii ako navrhla Erika
         * */
        public int pocetGeneracii3() {
        int pocet = 0;
        for (Osoba dieta : deti) {
                pocet = Math.max(1 + dieta.pocetGeneracii(), pocet);
        }
        return pocet;
}

        /**
         * uloží všetky osoby stromu potomkov danej osoby do zoznamu osôb.
         */
        public void pridajDoZoznamu(List<Osoba> zoznam) {
                if (deti == null) {
                        return;
                }

                for (Osoba dieta : deti) {
                        zoznam.add(dieta);
                        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");
                Osoba fero = new Osoba("Fero");
                janko.pridajDieta(jozko);
                janko.pridajDieta(maria);
                janko.pridajDieta(karol);
                karol.pridajDieta(lucia);
                karol.pridajDieta(petra);
                petra.pridajDieta(fero);
                janko.vypisRodostrom();

                System.out.println(janko.pocetGeneracii());
                System.out.println(janko.pocetGeneracii2());
                System.out.println(janko.pocetGeneracii3());

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

/**
 * 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 pocetZatvoriek = 0;
                int indexZaciatkuKorena = 0;
                int indexKoncaKorena = 0;
                int hodnotaKorena = 0;

                opisStromu.trim();

                if (opisStromu.length() == 0)
                        return null;

                if (opisStromu.charAt(0) == '(') {

                        for (int i = 0; i < opisStromu.length(); i++) {
                                if (opisStromu.charAt(i) == '(') {
                                        pocetZatvoriek++;
                                }
                                if (opisStromu.charAt(i) == ')') {
                                        pocetZatvoriek--;
                                }
                                if (pocetZatvoriek == 0) {
                                        indexZaciatkuKorena = i + 1;
                                        break;
                                }
                        }
                } else {
                        indexKoncaKorena = 0;
                }

                indexKoncaKorena = opisStromu.indexOf(' ', indexZaciatkuKorena + 1);

                if (indexKoncaKorena == -1)
                        indexKoncaKorena = opisStromu.length() - 1;

                System.out.println(indexZaciatkuKorena + "::" + (indexKoncaKorena + 1));
                hodnotaKorena = Integer.parseInt(opisStromu.substring(
                                indexZaciatkuKorena, indexKoncaKorena + 1).trim());

                String lavyPodstrom = "";
                String pravyPodstrom = "";

                if (indexZaciatkuKorena > 0)
                        lavyPodstrom = opisStromu.substring(1, indexZaciatkuKorena - 1);
                if (indexKoncaKorena != opisStromu.length() - 1)
                        pravyPodstrom = opisStromu.substring(indexKoncaKorena + 2,
                                        opisStromu.length() - 1);
                return new Uzol(hodnotaKorena, stromZRetazca(lavyPodstrom),
                                stromZRetazca(pravyPodstrom));
        }

        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());

                Uzol koren2 = stromZRetazca("((2) 7 ((5) 6 (11))) 2 (5 ((4) 9))");
//              Uzol koren2 = stromZRetazca("5 ((4) 9)");
//              Uzol koren2 = stromZRetazca("2");
                koren2.vypis();
                System.out.println(koren2.maximum());
        }
}

/**
 * Trieda implementujuca binarny vyhladavaci strom cisel
 */
public class BVS {

        /**
         * Sukromna privatna trieda reprezentujuca uzol stromu
         */
        private static class Uzol {
                // Hodnota ulozena v uzle
                int hodnota;
                // Referencia na laveho syna
                Uzol lavy;
                // Referencia na praveho syna
                Uzol pravy;

                /**
                 * Jednoduchy konstruktor ...
                 */
                public Uzol(int hodnota, Uzol lavy, Uzol pravy) {
                        this.hodnota = hodnota;
                        this.lavy = lavy;
                        this.pravy = pravy;
                }
        }

        /**
         * Referencia na uzol, ktory je korenom stromu
         */
        private Uzol koren = null;

        /**
         * Vrati, ci strom obsahuje zadanu hodnotu
         * @param hodnota hladana hodnota
         */
        public boolean contains(int hodnota) {
                // Cestu v strome zaciname v koreni stromu
                Uzol aktualny = koren;
                while (aktualny != null) {
                        if (aktualny.hodnota == hodnota)
                                return true;

                        // Na zaklade hodnoty v aktualnom uzle a hladanej hodnoty
                        // sa navigujeme ku jednemu zo synov (vid. vlastnosti BVS)
                        if (hodnota < aktualny.hodnota)
                                aktualny = aktualny.lavy;

                        if (aktualny.hodnota < hodnota)
                                aktualny = aktualny.pravy;
                }

                return false;  
        }

        /**
         * Prida zadanu hodnotu do stromu (ak v nom este nie je)
         * @param hodnota vkladana hodnota
         */
        public void add(int hodnota) {
                // Specialne osetrime pripad, ked vkladame do prazdneho stromu
                if (koren == null) {
                        koren = new Uzol(hodnota, null, null);
                        return;
                }

                // Vkladanie hodnoty do neprazdneho stromu (zaciname v koreni)
                Uzol aktualny = koren;
                while (true) {

                        // Ak taka hodnota uz je v BVS, niet co pridavat
                        if (aktualny.hodnota == hodnota)
                                break;

                        // Ak je vkladana hodnota mensia, ako hodnota v aktualnom uzle
                        // tak hodnotu treba vlozit do laveho podstromu
                        if (hodnota < aktualny.hodnota) {
                                // Ak laveho syna niet, tak namiesto neho vytvorime uzol
                                // s vkladanou hodnotou a koncime. V opacnom pripade sa
                                // presunieme do laveho syna
                                if (aktualny.lavy == null) {
                                        aktualny.lavy = new Uzol(hodnota, null, null);
                                        break;
                                } else
                                        aktualny = aktualny.lavy;
                        }

                        // Ak je vkladana hodnota vacsia, ako hodnota v aktualnom uzle
                        // tak hodnotu treba vlozit do praveho podstromu              
                        if (aktualny.hodnota < hodnota) {
                                // Ak praveho syna niet, tak namiesto neho vytvorime uzol
                                // s vkladanou hodnotou a koncime. V opacnom pripade sa
                                // presunieme do praveho syna
                                if (aktualny.pravy == null) {
                                        aktualny.pravy = new Uzol(hodnota, null, null);
                                        break;
                                } else
                                        aktualny = aktualny.pravy;
                        }
                }
        }

        public void remove(int hodnota) {
                // Uzol, v ktorom sa nachadzame pri zostupe stromom
                Uzol aktualny = koren;
                // Uzol, ktory je rodicom uzla "aktualny"
                Uzol rodicAktualneho = null;

                while (aktualny != null) {
                        if (aktualny.hodnota == hodnota)
                                break;

                        // Ako rodicia aktualneho si pre dalsiu iteraciu while-cyklu
                        // poznacime aktualny uzol (o chvilu sa totiz ideme posunut
                        // k jednemu z jeho synov)
                        rodicAktualneho = aktualny;

                        // Na zaklade hodnoty v aktualnom uzle a hladanej hodnoty
                        // sa navigujeme ku jednemu zo synov (vid. vlastnosti BVS)
                        if (hodnota < aktualny.hodnota)
                                aktualny = aktualny.lavy;

                        if (aktualny.hodnota < hodnota)
                                aktualny = aktualny.pravy;
                }

                // Ak while skoncil preto, ze sme dosli na neexistujuci uzol, tak
                // odstranovana hodnota v strome nie je (t.j. mozeme skoncit)
                if (aktualny == null)
                        return;

                int pocetDetiAktualneho = 0;
                if (aktualny.lavy != null)
                        pocetDetiAktualneho++;
                if (aktualny.pravy != null)
                        pocetDetiAktualneho++;

                // Osetrime situaciu, kedy ma odstranovany uzol 0 synov. Vtedy
                // jednoducho odstranime uzol zo stromu (nastavime jeho rodicovi
                // ako syna null - popri tom si davame pozor na pripad, ked odstranovany
                // uzol je koren - on nema rodica)
                if (pocetDetiAktualneho == 0) {
                        if (rodicAktualneho == null)
                                koren = null;
                        else {
                                if (rodicAktualneho.lavy == aktualny)
                                        rodicAktualneho.lavy = null;
                                else
                                        rodicAktualneho.pravy = null;
                        }
                }

                // Osetrime situaciu, kedy odstranovany uzol ma prave jedno dieta
                if (pocetDetiAktualneho == 1) {
                        // Vyberieme prave jeho dieta aktualneho uzla
                        Uzol dietaAktualneho = null;
                        if (aktualny.lavy != null)
                                dietaAktualneho = aktualny.lavy;
                        else
                                dietaAktualneho = aktualny.pravy;

                        if (rodicAktualneho == null)
                                koren = dietaAktualneho;
                        else {
                                if (rodicAktualneho.lavy == aktualny)
                                        rodicAktualneho.lavy = dietaAktualneho;
                                else
                                        rodicAktualneho.pravy = dietaAktualneho;
                        }
                }


                // Osetrime situaciu, kedy odstranovany uzol ma obe deti
                if (pocetDetiAktualneho == 2) {
                        // Najdeme maximum v lavom podstrome (stale ideme doprava)
                        Uzol rodicMaxima = aktualny;
                        Uzol maximum = aktualny.lavy;
                        while (maximum.pravy != null) {
                                rodicMaxima = maximum;
                                maximum = maximum.pravy;
                        }

                        // Hodnotu z maxima presunieme do odstranovaneho uzla
                        // (ale uz ho neideme odstranovat, namiesto neho odstranime uzol,
                        // v ktorom bola maximalna hodnota laveho podstromu - tento uzol ma
                        // nanajvys jedno dieta a to dieta lave)
                        aktualny.hodnota = maximum.hodnota;

                        // Odstranime uzol, ktory uchovaval maximalnu hodnotu
                        if (rodicMaxima.lavy == maximum)
                                rodicMaxima.lavy = maximum.lavy;
                        else
                                rodicMaxima.pravy = maximum.lavy;
                }
        }

        /**
         * Privatna metoda na vypis stromu s korenom v zadanom uzle
         * @param koren uzol, ktory je korenom vypisovaneho stromu
         */
        private void vypisStrom(Uzol koren) {
                if (koren == null)
                        return;

                vypisStrom(koren.lavy);
                System.out.println(koren.hodnota);
                vypisStrom(koren.pravy);
        }

        /**
         * Vypise hodnoty v strome v inorder prechode
         */
        public void vypis() {
                vypisStrom(koren);
        }

        public int vratMin(){
                Uzol aktualny = koren;
                while (aktualny.lavy !=null){
                        aktualny = aktualny.lavy;
                }
                return aktualny.hodnota ;
        }
        /**
         * @param args
         */
        public static void main(String[] args) {
                BVS bvs = new BVS();
                int[] hodnoty = {4, 5, 6, 2, 7, 1, 5, 7, 2};
                for (int i=0; i<hodnoty.length; i++)
                        bvs.add(hodnoty[i]);

               // bvs.vypis();
               // System.out.println("odstranujem 7");
               // bvs.remove(7);
               // System.out.println("odstranujem 4");
               // bvs.remove(4);
              //  bvs.vypis();
                System.out.println(bvs.vratMin());

        }
}

/**
 * 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 pocetZatvoriek = 0;
                int indexZaciatkuKorena = 0;
                int indexKoncaKorena = 0;
                int hodnotaKorena = 0;

                opisStromu.trim();

                if (opisStromu.length() == 0)
                        return null;

                if (opisStromu.charAt(0) == '(') {

                        for (int i = 0; i < opisStromu.length(); i++) {
                                if (opisStromu.charAt(i) == '(') {
                                        pocetZatvoriek++;
                                }
                                if (opisStromu.charAt(i) == ')') {
                                        pocetZatvoriek--;
                                }
                                if (pocetZatvoriek == 0) {
                                        indexZaciatkuKorena = i + 1;
                                        break;
                                }
                        }
                } else {
                        indexKoncaKorena = 0;
                }

                indexKoncaKorena = opisStromu.indexOf(' ', indexZaciatkuKorena + 1);

                if (indexKoncaKorena == -1)
                        indexKoncaKorena = opisStromu.length() - 1;

                System.out.println(indexZaciatkuKorena + "::" + (indexKoncaKorena + 1));
                hodnotaKorena = Integer.parseInt(opisStromu.substring(
                                indexZaciatkuKorena, indexKoncaKorena + 1).trim());

                String lavyPodstrom = "";
                String pravyPodstrom = "";

                if (indexZaciatkuKorena > 0)
                        lavyPodstrom = opisStromu.substring(1, indexZaciatkuKorena - 1);
                if (indexKoncaKorena != opisStromu.length() - 1)
                        pravyPodstrom = opisStromu.substring(indexKoncaKorena + 2,
                                        opisStromu.length() - 1);
                return new Uzol(hodnotaKorena, stromZRetazca(lavyPodstrom),
                                stromZRetazca(pravyPodstrom));
        }

        public int minimum() {
                int vysledok = hodnota;

                if(lavy!=null)
                        vysledok = Math.min(vysledok, lavy.minimum());

                if(pravy!=null)
                        vysledok = Math.min(vysledok, pravy.minimum());

                return vysledok;
        }

        public int pocetUzlov(){
                int pocet = 0;

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

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

                return pocet + 1 ;
        }

        public int pocetUrovni(){
                int pocet=0;
                if(lavy!=null)
                        pocet =Math.max( pocet , lavy.pocetUrovni());

                if(pravy!=null)
                        pocet =Math.max( pocet , pravy.pocetUrovni());
                return pocet+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());

                Uzol koren2 = stromZRetazca("((2) 7 ((5) 6 (11))) 2 (5 ((4) 9))");
//              Uzol koren2 = stromZRetazca("5 ((4) 9)");
//              Uzol koren2 = stromZRetazca("2");
                koren2.vypis();
//                System.out.println(koren2.maximum());
//                System.out.println(koren2.minimum());
                System.out.println(koren2.pocetUzlov());
                System.out.println(koren2.pocetUrovni());
        }
}