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

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 pocetPotomkov() {
                int pocetPotomkovDeti = 0;
                for (Osoba dieta : deti)
                        pocetPotomkovDeti += dieta.pocetPotomkov();

                return pocetPotomkovDeti + deti.size();
        }

        public void vypisRodostrom() {
                System.out.println(meno);
                for (Osoba dieta : deti)
                        dieta.vypisRodostrom();
        }

        public int pocetGeneracii() {

                int pocetGeneracii = 1;
                for (Osoba dieta : deti) {
                        pocetGeneracii = Math.max(1 + dieta.pocetGeneracii(),
                                        pocetGeneracii);
                }
                return pocetGeneracii;
        }

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

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

public class Uzol {
        public static final int PREORDER = 0;
        public static final int INORDER = 1;
        public static final int POSTORDER = 2;

        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 void vypis() {
                System.out.println(hodnota);

                if (lavy != null)
                        lavy.vypis();
                if (pravy != null)
                        pravy.vypis();
        }

        public void vytvorPrechod(List<Integer> list, int sposob) {
                if (sposob == PREORDER)
                        list.add(hodnota);
                if (lavy != null)
                        lavy.vytvorPrechod(list, sposob);

                if (sposob == INORDER)
                        list.add(hodnota);
                if (pravy != null)
                        pravy.vytvorPrechod(list, sposob);

                if (sposob == POSTORDER)
                        list.add(hodnota);
        }

        public int maximum() {
                int vysledok = hodnota;

                if (lavy != null)
                        vysledok = Math.max(vysledok, lavy.maximum());
                if (pravy != null)
                        vysledok = Math.max(vysledok, pravy.maximum());

                return vysledok;
        }

        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 = 1;
                if (lavy != null)
                        pocet += lavy.pocetUzlov();
                if (pravy != null)
                        pocet += pravy.pocetUzlov();

                return pocet;
        }

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

                return vyska;
        }

        public boolean obsahuje(int hladany) {
                if (hodnota == hladany)
                        return true;

                if (lavy != null)
                        if (lavy.obsahuje(hladany))
                                return true;

                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) {

                opisStromu = opisStromu.trim();
                Uzol lavy = null, pravy = null;
                int lavyIdx = 0, pravyIdx = opisStromu.length(), poc = 0;

                if (opisStromu.charAt(0) == '(') {      // mame lavu cast, tak ju spracujme
                        lavyIdx = 1; poc = 1;
                        for (; lavyIdx < opisStromu.length() - 1; lavyIdx++) {
                                if (opisStromu.charAt(lavyIdx) == '(')
                                        poc++;
                                if (opisStromu.charAt(lavyIdx) == ')')
                                        poc--;
                                if (poc == 0)
                                        break;
                        }
                        lavy = stromZRetazca(opisStromu.substring(1, lavyIdx++));
                }
                if (opisStromu.charAt(opisStromu.length() - 1) == ')') {        // mame pravu cast, tak ju spracujme
                        pravyIdx = opisStromu.length() - 2; poc = -1;
                        for (; pravyIdx >= 0; pravyIdx--) {
                                if (opisStromu.charAt(pravyIdx) == '(')
                                        poc++;
                                if (opisStromu.charAt(pravyIdx) == ')')
                                        poc--;
                                if (poc == 0)
                                        break;
                        }
                        pravy = stromZRetazca(opisStromu.substring(pravyIdx + 1, opisStromu.length() - 1));
                }


                int hodnota = Integer.parseInt(opisStromu.substring(lavyIdx, pravyIdx).trim());
                return new Uzol(hodnota, lavy, pravy);
        }

        public static Uzol generateNodeFromStrings(String preorder, String postorder) {
                // Osetrenie vstupov
                if (preorder == null || postorder == null)
                        return null;
                preorder = preorder.trim();
                postorder = postorder.trim();
                if (preorder.length() == 0 || postorder.length() == 0
                                || preorder.length() != postorder.length()) {
                        return null;
                }

                // Zistenie hodnoty korena
                int i = 0;
                while (i < preorder.length() && preorder.charAt(i) != ' ')
                        i++;
                final int value = Integer.parseInt(preorder.substring(0, i).trim());

                if (i == preorder.length())
                        return new Uzol(value, null, null);

                // Odstránenie hodnoty korena zo stringov
                postorder = postorder.substring(0, postorder.length() - i - 1);
                preorder = preorder.substring(i + 1);

                // Hladanie pravého syna v postorder zápise
                i = postorder.length() - 1;
                while (i > 0 && postorder.charAt(i) != ' ')
                        i--;
                final int newValue = Integer.parseInt(postorder.substring(i).trim());

                // Hladanie pravého syna v preorder zápise
                int Idx = 0;
                for (int j = 0; j < preorder.length(); j++) {
                        if (preorder.charAt(j) == ' ') {
                                if (Integer.parseInt(preorder.substring(Idx, j).trim()) == newValue)
                                        // V premennej Idx je index zaciatku pravého podstromu v
                                        // preorderi
                                        break;
                                Idx = j;
                        }
                }

                // Vytvorenie preorderov pre potreby rekurzívneho volania
                String preorderLeft = preorder.substring(0, Idx);
                String preorderRight = preorder.substring(Idx).trim();
                if (preorderRight.equals(preorder))
                        return new Uzol(value, null, generateNodeFromStrings(preorder,
                                        postorder));

                // Zistovanie všetkých hodnot pravého podstromu z preorderu
                List<Integer> rightSubtree = new ArrayList<Integer>();
                for (int j = Idx + 1; j < preorder.length(); j++) {
                        if (preorder.charAt(j) == ' ') {
                                rightSubtree.add(Integer.parseInt(preorder.substring(Idx, j)
                                                .trim()));
                                Idx = j;
                        }
                }
                rightSubtree.add(Integer.parseInt(preorder.substring(Idx,
                                preorder.length()).trim()));

                // Hladanie zaciatku pravého podstromu v postorder zápise
                Idx = postorder.length();
                for (int j = postorder.length() - 1; j > 0; j--) {
                        if (postorder.charAt(j) == ' ') {
                                if (!rightSubtree.contains(Integer.parseInt(postorder
                                                .substring(j + 1, Idx))))
                                        // V premennej Idx je index zaciatku pravého podstromu v
                                        // postorderi
                                        break;
                                Idx = j;
                        }
                }

                // Vytvorenie postorderov pre potreby rekurzívneho volania
                String postorderLeft = postorder.substring(0, Idx);
                String postorderRight = postorder.substring(Idx + 1);

                // The end.
                return new Uzol(value, generateNodeFromStrings(preorderLeft,
                                postorderLeft), generateNodeFromStrings(preorderRight,
                                postorderRight));
        }

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