1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:

/** Binaerer Baum fuer Daten vom Typ INHALT */
public class BinaerBaum<INHALT> {
  /** Wurzel des Baumes */
  Knoten<INHALT> wurzel;

  /** Konstruktor fuer den Baum */
  public BinaerBaum(Knoten<INHALT> wurzel) {
    this.wurzel = wurzel;
  };

  /** Anzahl der Knoten zaehlen */
  public int anzahlKnoten() {
    // TODO: Implementieren
  }

  /** Hoehe berechnen */
  public int hoehe() {
    return hoehe(wurzel);
  }

  /** Rekursive Hoehe */
  private int hoehe(Knoten k) {
    if (k == null) {
      return 0;
    } else {
      return 1 + Math.max(hoehe(k.links), hoehe(k.rechts));
    }
  }

  /** Klasse, die einen Knoten des Baumes speichert */
  protected static class Knoten<INHALT> {
    /** Gespeichterte Daten */
    protected INHALT daten;

    /** Linker und rechter Sohn */
    protected Knoten<INHALT> links, rechts;

    /** Konstruktor fuer Knoten */
    public Knoten(INHALT daten, Knoten<INHALT> links, Knoten<INHALT> rechts) {
      this.daten = daten;
      this.links = links;
      this.rechts = rechts;
    }
  }

  /** Methode zum Testen der Implementierung - besser: JUnit Test */
  public static void main(String[] args) {
    Knoten<Integer> links = new Knoten<Integer>(1, null,
        new Knoten<Integer>(2, null, null));
    Knoten<Integer> rechts = new Knoten<Integer>(5,
        new Knoten<Integer>(4, null, null),
        new Knoten<Integer>(6, null,
          new Knoten<Integer>(7, null, null)));
    Knoten<Integer> wurzel = new Knoten<Integer>(3, links, rechts);
    BinaerBaum<Integer> baum = new BinaerBaum<Integer>(wurzel);
    System.out.println("Hat der Baum die Hoehe 4? " + baum.hoehe());
    BinaerBaum<Integer> leer = new BinaerBaum<Integer>(null);
    System.out.println("Hat der leere Baum die Hoehe 0? " + leer.hoehe());
    System.out.println("Hat der Baum 7 Knoten? " + baum.anzahlKnoten());
    System.out.println("Hat der leere Baum 0 Knoten? " + leer.anzahlKnoten());
  }
}

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

	Knoten<INHALT> links;
	Knoten<INHALT> rechts;

	/** Anzahl der Knoten zaehlen */
	public int anzahlKnoten() {
		int anzahl = 1;
		if (links != null)
			anzahl += links.anzahlKnoten();

		if (rechts != null)
			anzahl += rechts.anzahlKnoten();

		return anzahl;
	}

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

public int anzahlKnoten() {
	return anzahlKnoten(wurzel);
}

public int anzahlKnoten(Knoten<INHALT> knoten) {
	int anzahl = 1;
	if (knoten.links != null)
		anzahl += anzahlKnoten(knoten.links);

	if (knoten.rechts != null)
		anzahl += anzahlKnoten(knoten.rechts);

	return anzahl;
}