* Dokumentation der Klasse Binaerbaum
* Author: Robert Hoehndorf
* Licence: GNU Public License
* Letze Aenderung: 2.12.1999 19:15 Uhr
*
* JDK 1.1.7B Linux
* Editor: Midnight Commander
*
* Die Klasse binaryTree implementiert die Datenstruktur Binaerbaum in JAVA.
* Der hier implementierte Binaerbaum speichert Objekte jeder Art. Als
* Sortierkriterium kann jedoch nur ein primitive Datentyp sein, zur Zeit
* nur ein Integer (int).
*
* Die Funktion insert benoetigt als erstes Argument den Sortierschluessel
* und als zweites einen NICHT-primitiven Datentyp (IRGENDEIN Object),
* der gespeichert wird.
* Die Funktion insert liefert bei Erfolg true zurueck, und wenn ein
* Objekt mit dem jeweiligen Sortierschluessel bereits existiert, false.
*
* Die Funktion delete benoetigt als Argument lediglich den Sortierschluessel
* und loescht das Objekt mit diesem Schluessel. Wurde der Eintrag nicht
* gefunden, wird false zurueckgeliefert, bei Erfolg true.
*
* Die Funktion find benoetigt als Argument einen Suchschluessel.
* Diese Funktion liefert das gesamte gefundene Datenobjekt zurueck oder
* ein null Objekt, wenn der Suchschluessel nicht gefunden wurde.
*
*/
import java.io.*;
import java.util.*;
public class binaryTree {
public element root;
public binaryTree () {
element root=null;
}
// Am Anfang ist der Baum leer, und die Wurzel somit NULL!
// Die Funktion insert fuegt ein neues Element in den Baum ein
// Als Schluessel des Baums wird vorerst ein INTEGER benutzt.
public boolean insert(int key, Object d) {
element x,current,parent; // wir brauchen drei Objekte
parent=null; // bzw. Elemente
// Parent initialisieren, weil Java zu bloed
current=root; // wir fangen bei der Wurzel an
// Diese Schleife bricht ab, wenn entweder herausgefunden wurde,
// das das Element bereits vorhanden ist, oder wenn (Variable) parent
// auf das letzte nicht-leere Element des Baumes gesetzt wurde, und
// current somit null ist, und damit das neue Element!
while(current!=null) { // solange wir nicht am
// Ende des Baumes angekommen sind ...
if (key==current.searchkey) return false; // Wenn der Schluesses
// schon vorhanden ist, wird einfach abgebrochen.
// An dieser Stelle wird die gesamte FUNKTION
// beendet und false returned!
parent=current; // Dann wird parent auf current gesetzt.
if (key<current.searchkey) // und links oder rechts weiter
current=current.left;
else
current=current.right;
}
x=new element(); // neues Element erstellen und initialisieren
x.parent=parent;
x.left=null;
x.right=null;
x.searchkey=key;
x.data=d;
if (parent!=null) // wenn x nicht die Wurzel ist, an die richtige
if(x.searchkey<parent.searchkey) // Stelle setzen
parent.left=x;
else
parent.right=x;
else
root=x;
return true;
} // Ende der Funktion INSERT
public boolean delete(int key) {
element x,y,z;
z=root;
/* Solange nicht am Ende des Baumes angelangt, suchen wir das Element.
* Wir brechen die Suche ab ( mit break) wenn wir das passende Element
* gefunden haben.
*/
while (z!=null) {
if (key==z.searchkey) // Wenn wir das Element gefunden haben,
break; // break
else
if (key<z.searchkey)
z=z.left;
else
z=z.right;
}
// Wenn z null, wurde das Element nicht gefunden,und wir brechen ab.
if (z==null) return false;
// Wenn das Element keine zwei Kinder hat...
if (z.left==null || z.right==null)
y=z;
else {
y=z.right;
while (y.left!=null) y=y.left;
}
if (y.left!=null)
x=y.left;
else
x=y.right;
if (x!=null) x.parent=y.parent;
if (y.parent!=null)
if (y==y.parent.left)
y.parent.left=x;
else
y.parent.right=x;
else
root=x;
if (y!=z) {
y.left=z.left;
if (y.left!=null) y.left.parent=y;
y.right=z.right;
if (y.right!=null) y.right.parent=y;
y.parent=z.parent;
if (z.parent!=null)
if (z==z.parent.left)
z.parent.left=y;
else
z.parent.right=y;
else
root=y;
}
return (true);
} // Ende von delete
public Object find(int key) {
int found=0;
element current=root;
while (current!=null) {
if (key==current.searchkey) {
found=current.searchkey;
return current.data;
} else {
if (key<current.searchkey)
current=current.left;
else
current=current.right;
}
}
return null;
} // Ende von find
} // Hier hoert die Klasse Binaerbaum auf