Binäre Bäume: Tiefe und Anzahl der Knoten

Die Anzahl der Knoten eines binären Baumes lässt sich in Java sehr schön durch Rekursion berechnen. Gegeben ist die Klasse Baum mit folgenden Methoden:

• void empty(): true, wenn der Baum leer ist.
• Baum left(): Gibt den linken Teilbaum zurück.
• Baum right(): Gibt den rechten Teilbaum zurück.

Die Summe der Knoten eines Baumes lässt sich in die Berechnung der Summe der Knoten seines linken und rechten Teilbaumes plus seines eigenen Knotens (= 1)  aufsplitten. Das ist schon die Rekursion. Die Rekursion bricht ab, wenn der Teilbaum keinen Teilbaum mehr hat (empty() = true):

/**
   * Liefert die Anzahl der Knoten eines Baumes.
   * @param b: Der Baum, dessen Knotenzahl berechnet werden soll.
   * @return Anzahl der Knoten.
   */
  public static int anzahlKnoten(Baum b) {
    if(!b.empty())  // Jeder Baum hat einen Knoten plus die Knoten seiner linken und rechten
                            // Teilbäume.
        return 1 + anzahlKnoten(b.left()) + anzahlKnoten(b.right());
    return 0;          // Wenn der Baum keinen Teilbaum hat, hat er keine zusätzlichen Knoten.
  }

Genauso einfach lässt sich die Baumtiefe bestimmen. Die Tiefe des Baumes ist seine eigene Tiefe (= 1) plus die Tiefe seines linken oder rechten Teilbaums, je nachdem welcher größer ist:

/**
   * Liefert die Tiefe eines Baumes.
   * @param b: Der Baum, dessen Tiefe bestimmt werden soll.
   * @return die Tiefe des Baumes.
   */
  public static int baumTiefe(Baum b) {
    if(!b.empty())  // Jeder Baum mit Kindern hat die Tiefe 1 plus die Tiefe des linken oder
                            // rechten Teilbaums, je nachdem, welcher größer ist.
        return 1 + Math.max(baumTiefe(b.left()), baumTiefe(b.right()));
    return 0;          // Wenn der Baum leer ist, hat er die Tiefe 0.
  }