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