Baum.java

package algorithmen;

import java.io.*;

public class Baum {
  
  public BaumKnoten wurzel;
  
  public Baum() {
    // Konstruktor erzeugt leeren Baum
    wurzel = null;
  }
  
  public void einfügen(BaumKnoten neu) {
    // fügt Knoten neu an die richtige Stelle ein
    
    // 1. Fall: Baum ist noch leer
    if (wurzel == null) {
      wurzel = neu;
    } else {
      // sonst rekursiv durch
      einfügen(wurzel, neu);
    }
  }
  
  private void einfügen(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
        einfügen(spitze.links, neu);
      }
    } else {
      // rechts einfügen
      if (spitze.rechts == null) {
        // neu einfach anhängen
        spitze.rechts = neu;
      } else {
        // neu im rechten Unterbaum unterbringen
        einfügen(spitze.rechts, neu);
      }
    }
  }
  
  public String toString() {
    if (wurzel != null) {
      return toString(wurzel);
    } else {
      return "<leerer Baum>";
    }
  }
  
  private String toString(BaumKnoten b) {
    // Ausdrucken des Teilbaums ab b, Reihenfolge inorder
    String s = "";
    
    if (b.links != null) {
      s += toString(b.links);
    }
    s += b.daten + "\n";
    if (b.rechts != null) {
      s += toString(b.rechts);
    }
    
    return s;
  }
  
  // Testprogramm mit Zufallszahlen
  public static void main(String[] args) throws IOException {
    
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    
    // Anzahl der Werte abfragen
    System.out.println("Anzahl der Listenelemente eingeben:");
    String s = in.readLine();
    int anzahl = Integer.parseInt(s);
    
    // starte mit leerem Baum
    Baum sortierBaum = new Baum();
    
    // fülle den Baum
    for (int i = 0; i < anzahl; i++) {
      double wert = Math.random();
      BaumKnoten neu = new BaumKnoten(wert);
      sortierBaum.einfügen(neu);
    }
    
    // gib den Baum aus
    System.out.println(sortierBaum);
  }
}