public class BTrees
{
// Konstanten für 'Dummy-Schlüssel'
private static final int minInt = Integer.MIN_VALUE;
private static final int maxInt = Integer.MAX_VALUE;;
// Durchläuft den B-Baum in Inorder-Reihenfolge, gibt also
// bei bzgl. der Sortierung korrekt aufgebautem B-Baum die
// gespeicherten Schlüssel in aufsteigend sortierter Reihenfolge aus.
// Diese Methodenimplementierung soll Ihnen als Beispiel dienen.
public static void traverseInOrder(BNode node)
{
if (node != null)
for (int i = 0; i < node.getChildCount(); i++)
{
Child c = node.getChild(i);
traverseInOrder(c.leftChild);
if (i < 4)
System.out.print(c.right+" ");
}
}
// Gibt die Höhe des Baums zurück, wenn sich alle Blätter
// auf demselben Niveau befinden, ansonsten -1.
// Das Kriterium eines B-Baums, dass alle Blätter
// denselben Abstand zur Wurzel haben sollen ist also
// erfüllt, wenn ein Wert >= 0 zurückgegeben wird.
public static int levelsOK(BNode node)
{
// ToDo
}
// Prüft, ob der B-Baum den Sortierkriterien genügt, d.h., ob
// die folgenden zwei Kriterien erfüllt sind
// 1) Die Schlüssel innerhalb eines Knotens sind aufsteigend sortiert.
// 2) Für jeden Schlüssel s innerhalb eines Knotens gilt, dass
// alle Schlüssel im Teilbaum seines linken Nachfolgers kleiner
// sind als s und alle Schlüssel im Teilbaum seines rechten
// Nachfolgers größer sind als s.
// ACHTUNG: Zur Realisierung dürfen Sie die Methode 'traverseInOrder'
// NICHT verwenden!
public static boolean isSorted(BNode node, int left, int right)
{
// ToDo
}
public static void main(String[] args)
{
BNode trees[] = new BNode[4];
// Baum 0 aufbauen
// Anlegen der Blätter
BNode tmp01 = new BNode(minInt);
tmp01.addNode(null, 1);
tmp01.addNode(null, 3);
BNode tmp02 = new BNode(4);
tmp02.addNode(null, 5);
BNode tmp03 = new BNode(9);
tmp03.addNode(null, 11);
tmp03.addNode(null, 12);
BNode tmp04 = new BNode(13);
tmp04.addNode(null, 14);
tmp04.addNode(null, 15);
tmp04.addNode(null, 16);
BNode tmp05 = new BNode(17);
tmp05.addNode(null, 20);
tmp05.addNode(null, 22);
tmp05.addNode(null, 30);
tmp05.addNode(null, 59);
// Wurzel erzeugen und Schlüssel mit Nachfolgern
// hinzufügen
trees[0] = new BNode(minInt);
trees[0].addNode(tmp01, 4);
trees[0].addNode(tmp02, 9);
trees[0].addNode(tmp03, 13);
trees[0].addNode(tmp04, 17);
// addNode(tmp05, maxInt) speichert den rechten Nachfolger
// des letzten Nutzschlüssels 17. Da für addNode immer auch
// ein Schlüsselwert übergeben werden muss, wird hier der
// 'Dummy-Schlüssel' maxInt übergeben.
trees[0].addNode(tmp05, maxInt);
// Baum 1 (s.o.)
BNode tmp11 = new BNode(minInt);
tmp11.addNode(null, 1);
tmp11.addNode(null, 3);
tmp11.addNode(null, 7);
BNode tmp12 = new BNode(9);
tmp12.addNode(null, 11);
tmp12.addNode(null, 12);
tmp12.addNode(null, 14);
BNode tmp13 = new BNode(minInt);
tmp13.addNode(tmp11, 9);
tmp13.addNode(tmp12, 15);
BNode tmp14 = new BNode(25);
tmp14.addNode(null, 30);
trees[1] = new BNode(minInt);
trees[1].addNode(tmp13, 25);
trees[1].addNode(tmp14, maxInt);
// Baum 2
BNode tmp21 = new BNode(minInt);
tmp21.addNode(null, 1);
tmp21.addNode(null, 3);
tmp21.addNode(null, 5);
BNode tmp22 = new BNode(4);
tmp22.addNode(null, 5);
tmp22.addNode(null, 8);
BNode tmp23 = new BNode(9);
tmp23.addNode(null, 11);
tmp23.addNode(null, 12);
BNode tmp24 = new BNode(13);
tmp24.addNode(null, 14);
tmp24.addNode(null, 16);
trees[2] = new BNode(minInt);
trees[2].addNode(tmp21, 4);
trees[2].addNode(tmp22, 9);
trees[2].addNode(tmp23, 13);
trees[2].addNode(tmp24, maxInt);
// trees[3] ist ein leerer B-Baum
// Beispiel
System.out.println("Beispielausgabe Traversierung:");
traverseInOrder(trees[0]);
System.out.println("\n");
// Tests
System.out.println("Baum Nr.\tAlle Blätter auf einem Niveau?\tSortierung ok?");
for (int i = 0; i < trees.length; i++)
System.out.println(i + "\t\t\t\t\t" + (levelsOK(trees[i])==-1 ? "nein" : "ja ") +
"\t\t\t\t\t" + (isSorted(trees[i], minInt, maxInt) ? "ja" : "nein"));
}
}