/**
 * AlgoDat SS00, Aufgaben 52,53,54,55
 * Binaerer Suchbaum
 * Knoten des Baumes
 * 
 * @author Christian Semrau
 * <a href="mailto:gsemrau@cs.uni-magdeburg.de">gsemrau@cs.uni-magdeburg.de</a>
 */
class TreeNode {
    private TreeNode left, right;
    private Comparable element;

// dieser Konstruktor nimmt nur das Element
public TreeNode(Comparable obj) {
    this(obj, null, null);
}

// dieser Konstruktor nimmt das Element und die beiden Unterknoten
public TreeNode(Comparable obj, TreeNode left, TreeNode right) {
    element = obj;
    this.left = left;
    this.right = right;
}

// die Zugriffsmethoden
public Comparable getElement() { return element;}
public TreeNode getLeft() { return left;}
public TreeNode getRight() { return right;}
public void setElement(Comparable obj) { element = obj;}
public void setLeft(TreeNode left) { this.left = left;}
public void setRight(TreeNode right) { this.right = right;}

// Wenn der Knoten sich selbst darstellen soll,
// gibt er einfach die Stringdarstellung seines Datenelements
// zurueck.
public String toString() { 
    return element==null ? "null" : element.toString(); 
}

/** Fuegt das Objekt sortiert unterhalb dieses Knotens ein. 
 * Realisiert eine rekursive Version des insert. 
 * Liefert true, wenn das Objekt eingefuegt wurde. 
 */ 
public boolean insert(Comparable x) { 
    if (x.compareTo(getElement())==0){ 
        return false; 
    } 
    if (x.compareTo(getElement())<0){ 
        if (getLeft() == null){ 
            setLeft(new TreeNode(x, null, null)); 
            return true; 
        }else 
            return getLeft().insert(x); 
    }else{ 
        if (getRight() == null){ 
            setRight(new TreeNode(x, null, null)); 
            return true; 
        }else 
            return getRight().insert(x); 
    } 
} 
 
    // -------------------------------- 
    // -- WEITERE METHODEN DES BAUMS -- 
    // --------- Aufgabe 55 ----------- 
    // -------------------------------- 

/**
 * Liefert die Hoehe des Unterbaumes, ein Knoten ohne Kinder hat die Hoehe 1.
 */
public int getHeight() {
    int height = 0;
    if (left != null) height = Math.max(height, left.getHeight());
    if (right != null) height = Math.max(height, right.getHeight());
    return height+1;
}

/** Liefert die Anzahl der Unterknoten, sich selbst mitgezaehlt. */
public int getNrOfNodes() {
    int count = 0;
    if (left != null) count += left.getNrOfNodes();
    if (right != null) count += right.getNrOfNodes();
    return count+1;
}

/** true, wenn der Knoten balanciert ist. */
public boolean isBalanced() {
    int hleft = 0, hright = 0;
    if (left!=null) hleft = left.getHeight();
    if (right!=null) hright = right.getHeight();
    return Math.abs(hleft-hright) <= 1;
}

/** true, wenn dieser Knoten und alle Unterknoten balanciert sind. */
public boolean isCompleteBalanced() {
    // Diese Implementierung ist ineffizient, weil getHeight()
    // fuer jeden einzelnen Knoten aufgerufen wird, und getHeight()
    // seinerseits den kompletten Unterbaum abgrast.
    if (left!=null) if (!left.isCompleteBalanced()) return false;
    if (right!=null) if (!right.isCompleteBalanced()) return false;
    return isBalanced();
}

}
 // TreeNode