| www.r-krell.de |
| Webangebot für Schule und Unterricht, Software, Fotovoltaik und mehr |
Willkommen/Übersicht > Informatik > Informatik mit Java -Seite f) > Quelltext Sortierbaum
Java-Quelltext für einen binären Sortierbaum
(Auszüge)
Die auf meiner Seite „Informatik mit Java", Teil f) als Gerüst vorgestellte Klasse F_Sortierbaum kann beispielsweise wie folgt implementiert werden (wobei hier nicht alle Methoden angegeben werden):
// Java-Baum-Programm, für IF12M -- Krell, 12.7.04, 10.8.04 -- www.r-krell.de
import java.io.*;
public class F_Sortierbaum extends F_UrBaum
{
F_Knoten wurzel; // "Zeiger" auf den obersten Knoten im Baum
char sortKrit; // Sortierkriterium, nach dem der Baum aufgebaut wird
//----------------------------------------------------------------
public F_Sortierbaum (char sortierKriterium)
// Konstruktor: legt neuen leeren Baum an
{
wurzel = null;
sortKrit = sortierKriterium;
}
public boolean istLeer()
{
return (wurzel == null);
}
public void sortRein (F_ObjektMitOrdnung neu)
{
wurzel = rekSortRein (neu, wurzel);
}
private F_Knoten rekSortRein (F_ObjektMitOrdnung neu, F_Knoten knoten)
{
if (knoten == null) // hier steht noch nichts: passende Stelle gefunden...
{
knoten = new F_Knoten (neu); // .. fürs neue Element in neuem Knoten („Blatt")
}
else
{
if (neu.vergleicheMit (knoten.inhalt, sortKrit) < 0) // Sortierung beachten!
{
knoten.li = rekSortRein (neu, knoten.li); // neues Element muss in den linken Teilbaum
}
else
{
knoten.re = rekSortRein (neu, knoten.re); // neues Element muss in den rechten Teilbaum
}
}
return (knoten); // die aufruf. Instanz erhält (den Zeiger auf den neuen) Knoten, ..
} // .. um damit die Verknüpfung im Baum herstellen zu können
//----------------------------------------------------------------
public F_ObjektMitOrdnung zeigeGesucht (F_ObjektMitOrdnung gesucht)
{
return (rekZeige (gesucht, wurzel));
}
private F_ObjektMitOrdnung rekZeige (F_ObjektMitOrdnung gesucht, F_Knoten knoten)
{
if (knoten == null) // schon unten aus dem Baum raus?
{
return (null); // gesuchtes Element nicht gefunden
}
else
{
if (gesucht.vergleicheMit (knoten.inhalt, sortKrit) == 0) // Übereinstimmung!
{
return (knoten.inhalt); // gefundes Element zurück geben
}
else
{
if (gesucht.vergleicheMit (knoten.inhalt, sortKrit) < 0)
{
return (rekZeige (gesucht, knoten.li)); // im linken Teilbaum suchen
}
else
{
return (rekZeige (gesucht, knoten.re)); // im rechten Teilbaum suchen
}
}
}
}
//----------------------------------------------------------------
public F_ObjektMitOrdnung löscheGesucht (F_ObjektMitOrdnung löschElement)
{
F_ObjektMitOrdnung weg = zeigeGesucht (löschElement);
if (weg != null)
{
wurzel = rekRaus (löschElement, wurzel);
}
return (weg);
}
private F_Knoten rekRaus (F_ObjektMitOrdnung löschEl, F_Knoten knoten)
{
if (knoten != null)
{
// Während das Löschen von Blättern (ohne Nachfolger) bzw. von Knoten mit
// nur höchstens einem Nachfolger recht leicht ist, gibt es noch den schwierigen Fall,
// dass ein Knoten mit zwei Nachfolgern raus soll. Eine geschickte Implementierung
// achtet darauf, dass nicht nur die Sortierung des Baums erhalten bleibt,
// sondern dieser keinesfalls mehr Ebenen bekommt als vorher!
// - Implementation als Übung --
}
return (knoten);
}
//----------------------------------------------------------------
public int knotenZahl ()
{
return (rekKnoten (wurzel));
}
private int rekKnoten (F_Knoten knoten)
{
if (knoten == null)
{
return (0);
}
else
{
return (rekKnoten(knoten.li) + rekKnoten(knoten.re) + 1);
}
}
//----------------------------------------------------------------
public String lwrAusgabe ()
{
return (rekLWR (wurzel, ""));
}
private String rekLWR (F_Knoten knoten, String aus)
{
if (knoten != null)
{
aus = rekLWR (knoten.li, aus); // L
aus = aus + " " + knoten.inhalt.zeigeObjekt(); // W
aus = rekLWR (knoten.re, aus); // R
}
return (aus);
}
public String aufDisk1 (String dateiName)
{
String meldung = "Der Baum wurde in '"+dateiName+"' gespeichert (WLR)!";
try
{
ObjectOutputStream datei = new ObjectOutputStream (new FileOutputStream (dateiName));
datei.writeObject (""+sortKrit); // notiert Sortierkriterium als String(-Object)
datei.writeObject (new Integer(knotenZahl())); // nur drin zur Kompatibilität mit aufDisk2
rekAufDisk1 (wurzel, datei);
datei.close();
}
catch (Exception fehler)
{
meldung = "Fehler beim Speichern von '"+dateiName+"': "+fehler;
}
return (meldung);
}
private void rekAufDisk1 (F_Knoten knoten, ObjectOutputStream aus) throws Exception
{
if (knoten != null)
{
aus.writeObject (knoten.inhalt); // W
rekAufDisk1 (knoten.li, aus); // L
rekAufDisk1 (knoten.re, aus); // R
}
}
//----------------------------------------------------------------
public String vonDisk1 (String dateiName)
{
String meldung = "Alle Elemente aus '"+dateiName+"' wurden eingefügt!";
try
{
ObjectInputStream datei = new ObjectInputStream (new FileInputStream (dateiName));
wurzel = null; // löscht evtl. schon vorhandene Elemente aus dem Baum
sortKrit = ((String) datei.readObject()).charAt(0); // holt Sortierkriterium
try // holt Elemente und sortiert sie in den Baum
{
Object vergissEs = datei.readObject(); // liest und vergisst die nicht benötigte Knotenzahl
while (true)
{
sortRein ((F_ObjektMitOrdnung)datei.readObject()); // das normale sortRein!
}
}
catch (EOFException eof) // Dateiende
{
datei.close();
}
}
catch (Exception fehler)
{
meldung = "Fehler beim Öffnen von '"+dateiName+"': "+fehler;
}
return (meldung);
}
zurück zur Seite „Informatik mit Java, Teil f)"