Zdrojový kód k 4. prednáške

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

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

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

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

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