B4

package sk.upjs.paz.cvicenie04;

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() {
        // hodnota -1 aby sme nemuseli mat specialny if ak nema deti
        // ak nema deti tak return 0
        // ak ma deti tak maxGen bude urcite aspon 0
        int maxGen = -1;

        for (Osoba dieta : deti) {
            maxGen = Math.max(maxGen, dieta.pocetGeneracii());
        }

        return maxGen + 1;
    }

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

    @Override
    public String toString() {
        return "Osoba{" +
                "meno='" + meno + '\'' +
                ", pocetDeti=" + deti.size() +
                '}';
    }

    /**
     * Main s vytvorenim stromu potomkov pre Janka
     */
    public static void main(String[] args) {
        Osoba a = new Osoba("A");
        Osoba b = new Osoba("B");
        Osoba c = new Osoba("C");
        Osoba d = new Osoba("D");
        Osoba e = new Osoba("E");
        Osoba f = new Osoba("F");
        Osoba g = new Osoba("G");
        Osoba h = new Osoba("H");
        Osoba i = new Osoba("I");
        Osoba j = new Osoba("J");
        a.pridajDieta(b);
        a.pridajDieta(c);
        a.pridajDieta(d);
        b.pridajDieta(e);
        b.pridajDieta(f);
        c.pridajDieta(g);
        g.pridajDieta(h);
        g.pridajDieta(i);
        g.pridajDieta(j);
        a.vypisRodostrom();
        System.out.println(a.pocetGeneracii());

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

package sk.upjs.paz.cvicenie04;

/**
 * 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;
    }

    private static int indexKorena(String opisStromu) {
        return 0;
    }

    private static String odstranitMedzery(String s) {
        return s;
    }

    public static Uzol stromZRetazca(String opisStromu) {
        opisStromu = odstranitMedzery(opisStromu);
        // 1. najst index korena
        int indexKorena = indexKorena(opisStromu);

        // 2. vytvorim uzol
        // uzol.hodnota - precitat zo stringu od indexu korena
        int indexZatvorkyZaKorenom = opisStromu.indexOf('(', indexKorena);
        if (indexZatvorkyZaKorenom == -1) {
            indexZatvorkyZaKorenom = opisStromu.length();
        }
        String koren = opisStromu.substring(indexKorena, indexZatvorkyZaKorenom);
        int hodnota = Integer.parseInt(koren);
        //zapis v jednom riadku - int hodnota = Integer.parseInt(opisStromu.substring(indexKorena, opisStromu.indexOf('(', indexKorena)));
        // uzol.lavy - stromZRetazca(opisStromu.substring(vlavo))
        Uzol lavy = null;
        // podmienka moze byt aj ina, napr. indexKorena != 0
        if (opisStromu.charAt(0) == '(') {
            lavy = stromZRetazca(opisStromu.substring(1, indexKorena - 1));
        }
        // uzol.pravy - stromZRetazca(substring vpravo)
        Uzol pravy = null;

        // nezabudnut
        // pri substringoch vynechat krajne zatvorky
        // vyriesit listy pripadne uzol.lavy=null

        // 3. vratim uzol
        return new Uzol(hodnota, lavy, pravy);
    }


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

package sk.upjs.paz.cvicenie04;

/**
 * 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;
    }

    private static int indexKorena(String opisStromu) {
        if (opisStromu.charAt(0) != '(') {
            return 0;
        }
        int pocitadlo = 0;
        for (int i = 0; i < opisStromu.length(); i++) {
            if (opisStromu.charAt(i) == '(') {
                pocitadlo++;
            } else if (opisStromu.charAt(i) == ')') {
                pocitadlo--;
            }
            if (pocitadlo == 0) {
                return i + 1;
            }
        }
        return 0;
    }

    private static String odstranitMedzery(String s) {
//        StringBuilder sb = new StringBuilder();
//        for (int i = 0; i < s.length(); i++) {
//            if (s.charAt(i) != ' ') {
//                sb.append(s.charAt(i));
//            }
//        }
//        return sb.toString();
        return s.replaceAll(" ", "");
    }

    // ((2) 7 ((5) 6 (11))) 2 (5 ((4) 9))
    public static Uzol stromZRetazca(String opisStromu) {
        opisStromu = odstranitMedzery(opisStromu);
        // 1. najst index korena
        int indexKorena = indexKorena(opisStromu);

        // 2. vytvorim uzol
        // uzol.hodnota - precitat zo stringu od indexu korena
        int indexZatvorkyZaKorenom = opisStromu.indexOf('(', indexKorena);
        if (indexZatvorkyZaKorenom == -1) {
            indexZatvorkyZaKorenom = opisStromu.length();
        }
        String koren = opisStromu.substring(indexKorena, indexZatvorkyZaKorenom);
        System.out.println("Koren je: \"" + koren+ "\"");
        int hodnota = Integer.parseInt(koren);
        //zapis v jednom riadku - int hodnota = Integer.parseInt(opisStromu.substring(indexKorena, opisStromu.indexOf('(', indexKorena)));
        // uzol.lavy - stromZRetazca(opisStromu.substring(vlavo))
        Uzol lavy = null;
        // podmienka moze byt aj ina, napr. indexKorena != 0
        if (opisStromu.charAt(0) == '(') {
            lavy = stromZRetazca(opisStromu.substring(1, indexKorena - 1));
        }
        // uzol.pravy - stromZRetazca(substring vpravo)
        Uzol pravy = null;
        if (opisStromu.charAt(opisStromu.length() - 1) == ')') {
            pravy = stromZRetazca(opisStromu.substring(indexZatvorkyZaKorenom + 1, opisStromu.length() - 1));
        }

        // nezabudnut
        // pri substringoch vynechat krajne zatvorky
        // vyriesit listy pripadne uzol.lavy=null

        // 3. vratim uzol
        return new Uzol(hodnota, lavy, pravy);
    }


    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());
        String s = "((2) 7 ((5) 6 (11))) 2 (5 ((4) 9))";
        Uzol u = stromZRetazca(s);
        System.out.println();
    }
}