Baum.java

import java.io.*;

public class Baum {
  
  public BaumKnoten wurzel;
  
  public Baum() {
    // Konstruktor erzeugt leeren Baum
    wurzel = null;
  }
  
  public void einfuegen(double wert) {
    // fügt Knoten neu an die richtige Stelle ein
    BaumKnoten neu = new BaumKnoten(wert);
    
    // 1. Fall: Baum ist noch leer
    if (wurzel == null) {
      wurzel = neu;
    } else {
      // sonst rekursiv durch
      einfuegen(wurzel, neu);
    }
  }
  
  public int hoehe() {
    // gibt Höhe des Baums zurück
    return hoehe(wurzel);
  }
  
  public int hoehe(BaumKnoten spitze) {
    // gibt Höhe des Baums unter spitze zurück
    if (spitze == null) {
      return 0;
    } else {
      int h = Math.max(hoehe(spitze.links), hoehe(spitze.rechts));
      return h + 1;
    }
  }
  
  private void einfuegen(BaumKnoten spitze, BaumKnoten neu) {
    // fügt Knoten neu an die richtige Stelle unter Teilbaum spitze ein
    
    if (spitze.daten > neu.daten) {
      // links einfügen
      if (spitze.links == null) {
        // neu einfach anhängen
        spitze.links = neu;
      } else {
        // neu im linken Unterbaum unterbringen
        einfuegen(spitze.links, neu);
      }
    } else {
      // rechts einfügen
      if (spitze.rechts == null) {
        // neu einfach anhängen
        spitze.rechts = neu;
      } else {
        // neu im rechten Unterbaum unterbringen
        einfuegen(spitze.rechts, neu);
      }
    }
  }
  
  public String toString() {
    if (wurzel != null) {
      return toString(wurzel, 0);
    } else {
      return "<leerer Baum>";
    }
  }
  
  private static int indentPrint = 4;  // Einrückung beim Ausdrucken
  
  private String toString(BaumKnoten b, int pos) {
    // Ausdrucken des Teilbaums ab b, Reihenfolge inorder
    String s = "";
    
    // pos Leerzeichen für die weitere Ausgabe
    String margin = "";
    for (int i=0; i<pos; i++) {
      margin += " ";
    }
    
    if (b == null) {
      s += margin + "<null>"+ "\n";
    } else {
      s += toString(b.rechts, pos + indentPrint);
      s += margin + b.daten + "\n";
      s += toString(b.links, pos + indentPrint);
    }
    
    return s;
  }
}