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;
}
}