/*
    Aufgabe 4) Bäume

    In der Klasse IntTree haben Sie eine Baumimplementierung gegeben, die einen
    sortierten Binärbaum abbildet. Jede Veränderung des Baumes durch eine
    Methode muss gewährleisten, dass dieser sortiert bleibt. Dazu sollen Sie
    folgende zusätzliche Methoden implementieren:

    - add:              Fügt einen Knoten in den Baum ein. Werden folgende
    (bereits gegeben)   Elemente {12,4,6,15,1,13,5,14} nacheinander in den Baum
                        eingefügt, wird folgender Baum aufgebaut:
                                                 12
                                              /      \
                                            4         15
                                          /   \      /
                                         1     6   13
                                              /      \
                                             5        14
    - countNodes:       Liefert die Anzahl aller Knoten im Baum zurück. Wird
                        ohne Parameter aufgerufen.
    - countLeaves:      Liefert die Anzahl der Blattknoten zurück. Wird ohne
                        Parameter aufgerufen.
    - height:           Liefert die Höhe des Baumes zurück. Der leere Baum hat
                        die Höhe 0. Hat der Baum nur einen Knoten (Wurzel), dann
                        hat er die Höhe 1. Mit jeder zusätzlichen Stufe von
                        Nachfolgern erhöht sich die Höhe um 1. Der oben gezeigte
                        Baum hat die Höhe 4.
    - printLeaves:      Diese Methode gibt die Elemente der Blätterknoten aus,
                        wobei das linke Blatt immer vor dem rechten Blatt
                        ausgegeben wird. Verwenden Sie an entsprechender Stelle
                        für die Ausgabe -> System.out.println(this.elem);
    - printInOrderUp:   Diese Methode gibt alle Elemente in aufsteigender
                        Reihenfolge aus.
                        Verwenden Sie an entsprechender Stelle für die
                        Ausgabe -> System.out.println(this.elem);
    - printInOrderUpSub:Diese Methode gibt alle Elemente eines Teilbaums in
                        aufsteigender Reihenfolge aus. Dazu wird der Methode ein
                        Element übergeben, welches dem Wurzelknoten des
                        Teilbaums entspricht. Nun wird der komplette Teilbaum
                        inklusive Wurzel ausgegben. Verwenden Sie an
                        entsprechender Stelle für die
                        Ausgabe -> System.out.println(this.elem);
    - printPostOrder:   Diese Methode gibt alle Elemente in der sogenannten
                        Post-Order aus. Die Post-Order für den oben abgebildeten
                        Baum ergibt folgende Reihenfolge (1,5,6,4,14,13,15,12).
                        Verwenden Sie an entsprechender Stelle für die
                        Ausgabe -> System.out.println(this.elem);
    - printPreOrder:    Diese Methode gibt alle Elemente in der sogenannten
                        Pre-Order aus. Die Pre-Order für den oben abgebildeten
                        Baum ergibt folgende Reihenfolge (12,4,1,6,5,15,13,14).
                        Verwenden Sie an entsprechender Stelle für die
                        Ausgabe -> System.out.println(this.elem);

    Zusatzfragen:
    1. Wie könnte man vorgehen, wenn man einen Knoten in den Baum einfügen
       möchte. Reicht es, den Knoten einzuhängen, oder müssen zusätzliche
       Operationen durchgeführt werden?

*/
public class Aufgabe4 {

    public static void main(String[] args) {
        IntTree tree = new IntTree();
        tree.add(12);
        tree.add(18);
        tree.add(11);
        tree.add(9);
        tree.add(4);
        tree.add(6);
        tree.add(2);
        tree.add(19);
        System.out.println("Should be 3");
        System.out.println(tree.countLeaves());
        System.out.println("should be 8");
        System.out.println(tree.countNodes());
    }
}

class IntTree {

    private class Node {
        int elem;
        Node left = null;
        Node right = null;

        Node(int elem) {
            this.elem = elem;
        }

        void add(int elem) {
            if (elem < this.elem) {
                if (this.left == null) {
                    this.left = new Node(elem);
                } else {
                    this.left.add(elem);
                }
            } else {
                if (this.right == null) {
                    this.right = new Node(elem);
                } else {
                    this.right.add(elem);
                }
            }
        }

        int countNodes() {
            if (this.left == null && this.right == null) { return 1; }

            if (this.left == null) { return 1 + this.right.countNodes(); }
            if (this.right == null) { return 1 + this.left.countNodes(); }

            return 1 + this.left.countNodes() + this.right.countNodes();
        }

        int countLeaves() {
            if (this.left == null && this.right == null) { return 1; }

            return (this.left == null ? 0 : this.left.countLeaves()) + (this.right == null ? 0 : this.right.countLeaves());
        }

        int height() {
            if (this.left == null && this.right == null) { return 1; }

            if (this.left == null) { return 1 + this.right.height(); }
            if (this.right == null) { return 1 + this.left.height(); }

            return 1 + Math.max(this.left.height(), this.right.height());
        }

        void printLeaves() {
            if (this.left == null && this.right == null) {
                System.out.println(this.elem);
            }
            if (this.left != null) {
                this.left.printLeaves();
            }
            if (this.right != null) {
                this.right.printLeaves();
            }
        }

        void printInOrderUp() {
            if (this.left != null) {
                this.left.printInOrderUp();
            }
            System.out.println(this.elem);
            if (this.right != null) {
                this.right.printInOrderUp();
            }
        }

        void printInOrderUpSub(int elem) {
            if (elem == this.elem) {
                this.printInOrderUp();
            } else if (elem > this.elem) {
                this.right.printInOrderUpSub(elem);
            } else {
                this.left.printInOrderUpSub(elem);
            }

        }

        void printPostOrder() {
            if (this.left != null) {
                this.left.printPostOrder();
            }
            if (this.right != null) {
                this.right.printPostOrder();
            }
            System.out.println(this.elem);
        }

        void printPreOrder() {
            System.out.println(this.elem);
            if (this.left != null) {
                this.left.printPreOrder();
            }
            if (this.right != null) {
                this.right.printPreOrder();
            }
        }
    }

    private Node root = null;

    public void add(int elem) {
        if (empty()) {
            this.root = new Node(elem);
        } else {
            this.root.add(elem);
        }
    }

    public boolean empty() {
        return this.root == null;
    }

    public int countNodes() {
        return this.empty() ? 0 : this.root.countNodes();
    }

    public int countLeaves() {
        return this.root == null ? 0 : this.root.countLeaves();
    }

    public int height() {
        return this.root == null ? 0 : this.root.height();
    }

    public void printLeaves() {
        if (this.root != null) {
            this.root.printLeaves();
        }
    }

    public void printInOrderUp() {
        if (this.root != null) {
            this.root.printInOrderUp();
        }
    }

    public void printInOrderUpSub(int elem) {
        if (this.root != null) {
            this.root.printInOrderUpSub(elem);
        }
    }

    public void printPostOrder(){
        if (this.root != null) {
            this.root.printPostOrder();
        }
    }

    public void printPreOrder(){
        if (this.root != null) {
            this.root.printPreOrder();
        }
    }

    public static void main(String[] args) {
        // Aufgabe4.main(new String[0]);
    }
}