Hi,
Ich hab mit meinem BinearTree ein wenig Probleme mit der LöschMehtode, ich versuche jeden Fall durchzuspielen, aber es schleichen sich dauernt neue Fehler ein. Wenn viel. mal jemand sich das anschauen könnte, was ich da falsch mache, ich sitzte jetzt schon 2 Wochen dran und die Zeit wird knapp;(
Vielen Dank
Mein BinearTree mit einer Testklasse:
Ich hab mit meinem BinearTree ein wenig Probleme mit der LöschMehtode, ich versuche jeden Fall durchzuspielen, aber es schleichen sich dauernt neue Fehler ein. Wenn viel. mal jemand sich das anschauen könnte, was ich da falsch mache, ich sitzte jetzt schon 2 Wochen dran und die Zeit wird knapp;(
Vielen Dank
Mein BinearTree mit einer Testklasse:
Java:
import java.io.*;
import java.util.*;
import de.htw.saarland.stl.Stdin;
/**
* Test der Personenverwaltung
*/
public class BinearTreeTest {
private final int ANHAENGEN = 1;
private final int ENTFERNEN = 2;
private final int TREEAUSGABE = 3;
private final int KNOTENFIND = 4;
private final int LADEN = 5;
private final int ENDE = 99;
private PrintStream out = System.out;
private String uebergabe;
public BinearTreeTest() {
}
public void start() {
int menueAuswahl = -1;
BinaerTree binearTree = new BinaerTree();
do {
try {
menueAuswahl = auswaehlen();
out.println("Binärtree\n");
switch (menueAuswahl) {
case ANHAENGEN:
uebergabe = new String(Stdin.readlnString("Uebergabe :"));
binearTree.add(uebergabe);
break;
case ENTFERNEN:
uebergabe = new String(Stdin.readlnString("Uebergabe :"));
binearTree.del(uebergabe);
break;
case TREEAUSGABE:
System.out.println(binearTree.toStringBaum());
break;
case ENDE:
break;
default:
throw new DialogException();
}
} catch (NoSuchElementException e) {
out.println(e);
} catch (Exception e) {
e.printStackTrace();
}
} while (menueAuswahl != ENDE);
}
public int auswaehlen() {
out.print(
+ANHAENGEN + ": Knoten anhaengen \n" + ENTFERNEN
+ ": Knoten entfernen \n" + TREEAUSGABE + ": Tree ausgeben \n"
+ ENDE+ ": beenden -> \n");
return Stdin.readlnInt("Bitte waehlen: ");
}
public static void main(String[] args) {
try {
BinearTreeTest testlauf = new BinearTreeTest();
testlauf.start();
} catch (Exception e) {
e.printStackTrace();
}
}
}
Java:
/**
* Ein sortiertet Binaerbaum
*/
public class BinaerTree {
private Knoten root;
private StringComperator comperator = new StringComperator();
private int anzahlKnoten;
private Knoten gefundenerKnoten;
private int gesamtEtagen;
private int aktuelleEtage;
private Knoten knotenGanzRechts;
private Knoten knotenGanzLinks;
/**
* Hinzuefuegen von Objekten
*
* @param uebergabeObjekt
* Das uebergeben Object
*/
public void add(Object uebergabeObjekt) {
Knoten knoten = new Knoten(null, null, null, uebergabeObjekt);
aktuelleEtage = 0;
if (root == null) {
root = knoten;
anzahlKnoten++;
} else
addAbBestimmtenKnoten(root, knoten);
}
/**
* Add Methode aber ab bestimmten Knoten
*
* @param ausgewaehlterKnoten
* der aktuelle Knoten
* @param uebergabeKnoten
* der Knoten ab wo er anfangen soll
*/
public void addAbBestimmtenKnoten(Knoten ausgewaehlterKnoten,
Knoten uebergabeKnoten) {
aktuelleEtage++;
if (aktuelleEtage > gesamtEtagen)
gesamtEtagen++;
String ausgewaehlterKnotenString = (ausgewaehlterKnoten.toString());
String uebergabeKnotenString = (uebergabeKnoten.toString());
if (comperator
.compare(ausgewaehlterKnotenString, uebergabeKnotenString) > 0)
{
if (ausgewaehlterKnoten.hatLinkenSohn()) {
addAbBestimmtenKnoten(ausgewaehlterKnoten.getLinkerSohn(),
uebergabeKnoten);
}
if (!ausgewaehlterKnoten.hatLinkenSohn()) {
uebergabeKnoten.setVater(ausgewaehlterKnoten);
ausgewaehlterKnoten.setLinkerSohn(uebergabeKnoten);
anzahlKnoten++;
}
}
if (comperator
.compare(ausgewaehlterKnotenString, uebergabeKnotenString) < 0)
{
if (ausgewaehlterKnoten.hatRechtenSohn()) {
addAbBestimmtenKnoten(ausgewaehlterKnoten.getRechterSohn(),
uebergabeKnoten);
}
if (!ausgewaehlterKnoten.hatRechtenSohn()) {
uebergabeKnoten.setVater(ausgewaehlterKnoten);
ausgewaehlterKnoten.setRechterSohn(uebergabeKnoten);
anzahlKnoten++;
}
}
}
/**
* ToString in Baumform
*
* @return der Baum
*/
public String toStringBaum() {
StringBuffer sb = new StringBuffer();
toStringBaum(sb, root, " ");
return sb.toString();
}
/**
* ToString in Baumform
*
* @param stringBuffer
* @param knoten
* der uebergeben Knoten
* @param string
* Die Ausgabe
*/
private void toStringBaum(StringBuffer stringBuffer, Knoten knoten,
String string) {
if (knoten != null) {
toStringBaum(stringBuffer, knoten.getRechterSohn(), string + "| ");
stringBuffer.append(string).append("+--")
.append(knoten.getInhalt()).append("\n");
toStringBaum(stringBuffer, knoten.getLinkerSohn(), string + "| ");
}
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
public String toString() {
if (root != null) {
return toString(root);
} else {
return "<leerer Baum>";
}
}
/**
* ToString Methode mit Uebergabe
*
* @param uebergabeKnoten
* Die Knoten die ausgeben werden sollen
* @return die Elemente als String
*/
private String toString(Knoten uebergabeKnoten) {
// Ausdrucken des Teilbaums ab uebergabeKnoten, Reihenfolge inorder
String string = "";
if (uebergabeKnoten.hatLinkenSohn()) {
string += toString(uebergabeKnoten.getLinkerSohn());
}
string += uebergabeKnoten.getInhalt() + "\n";
if (uebergabeKnoten.hatRechtenSohn()) {
string += toString(uebergabeKnoten.getRechterSohn());
}
return string;
}
/**
* @return the anzahlKnoten
*
*/
public int getAnzahlKnoten() {
return anzahlKnoten;
}
/**
* @return the root
*/
public Knoten getRoot() {
return root;
}
/**
* Ruft die Funktion findKnotenAbBestimmtenKnoten mit dem Knoten root auf,
* falls dieser nicht null ist
*
* @param inhalt
* der Inhalt
* @return der Knoten
*/
public Knoten findKnoten(Knoten knoten) {
gefundenerKnoten = null;
if (root == null)
throw new DialogException("Baum ist leer!");
if (findKnotenAbBestimmtenKnoten(root, knoten) == null)
throw new DialogException("Knoten " + knoten + " gibt es nicht!");
return findKnotenAbBestimmtenKnoten(root, knoten);
}
/**
* Sucht einen Knoten mit einem bestimmten Inhalt
*
* @param zeigerKnoten
* der aktuelle Knoten
* @param gesuchterKnoten
* der Inhalt
* @return der Knoten
*/
public Knoten findKnotenAbBestimmtenKnoten(Knoten zeigerKnoten,
Knoten gesuchterKnoten) {
if (comperator.compare(zeigerKnoten, gesuchterKnoten) == 0) {
gefundenerKnoten = zeigerKnoten;
}
if (comperator.compare(zeigerKnoten, gesuchterKnoten) > 0) {
if (zeigerKnoten.hatLinkenSohn())
findKnotenAbBestimmtenKnoten(zeigerKnoten.getLinkerSohn(),
gesuchterKnoten);
}
if (comperator.compare(zeigerKnoten, gesuchterKnoten) < 0) {
if (zeigerKnoten.hatRechtenSohn())
findKnotenAbBestimmtenKnoten(zeigerKnoten.getRechterSohn(),
gesuchterKnoten);
}
return gefundenerKnoten;
}
/**
* Loescht ein uebergebenes Object
*
* @param uebergabe
* Das yu loeschende Object
*/
public void del(Object uebergabe) {
Knoten knoten = new Knoten(null, null, null, uebergabe);
this.del(findKnoten(knoten));
}
/**
* Loescht einen uebergebenen Knoten
*
* @param uebergabe
* der Inhalt eines Knotens
*/
private void del(Knoten knoten) {
//Knoten ist root
if (knoten==root) {
setRootNeu(root);
}
// Keine Soehne, also Blatt
else if (!knoten.hatLinkenSohn() && !knoten.hatRechtenSohn()) {
if (knoten.getVater().getLinkerSohn() == knoten) {
knoten.getVater().setLinkerSohn(null);
knoten = null;
} else if (knoten.getVater().getRechterSohn() == knoten) {
knoten.getVater().setRechterSohn(null);
knoten = null;
}
}
// nur linker Sohn
else if (knoten.hatLinkenSohn() && !knoten.hatRechtenSohn()) {
if (knoten.getVater().getLinkerSohn() == knoten) {
knoten.getVater().setLinkerSohn(knoten.getLinkerSohn());
knoten.getLinkerSohn().setVater(knoten.getVater());
knoten = null;
} else if (knoten.getVater().getRechterSohn() == knoten) {
knoten.getVater().setRechterSohn(knoten.getRechterSohn());
knoten.getRechterSohn().setVater(knoten.getVater());
knoten = null;
}
}
// nur rechter Sohn
else if (!knoten.hatLinkenSohn() && knoten.hatRechtenSohn()) {
if (knoten.getVater().getLinkerSohn() == knoten) {
knoten.getVater().setLinkerSohn(knoten.getLinkerSohn());
knoten = null;
}
else if (knoten.getVater().getRechterSohn() == knoten) {
knoten.getVater().setRechterSohn(knoten.getRechterSohn());
knoten = null;
}
}
// rechter und linker Sohn
else if (knoten.hatLinkenSohn() && knoten.hatRechtenSohn()) {
if (knoten.getVater().getLinkerSohn() == knoten) {
knoten.getVater().setLinkerSohn(knoten.getLinkerSohn());
knoten.getLinkerSohn().setVater(knoten.getVater());
knoten.getVater().getLinkerSohn().setRechterSohn(knoten.getRechterSohn());
knoten.getRechterSohn().setVater(knoten.getVater().getLinkerSohn());
knoten = null;
}
else if (knoten.getVater().getRechterSohn() == knoten) {
knoten.getVater().setRechterSohn(knoten.getRechterSohn());
knoten.getVater().getRechterSohn().setLinkerSohn(knoten.getLinkerSohn());
knoten = null;
}
}
}
/**
* @return the gesamtEtagen
*/
public int getGesamtEtagen() {
return gesamtEtagen;
}
/**
* Setzt den Root neu, falls
* dieser geloescht werden sollte
* @param knoten der zu uebegeben Root Knoten
*/
public void setRootNeu(Knoten knoten)
{
Knoten neuerRoot = null;
//Hat Root einen linken Sohn, so wird das rechteste Blatt vom linken Sohn, der neue Root
if (knoten.hatLinkenSohn())
{
neuerRoot= getKnotenGanzRechts(knoten.getLinkerSohn());
if(knoten.getLinkerSohn()==neuerRoot)
{
neuerRoot.setLinkerSohn(null);
}
else
{
//Vater wird zu Blatt
neuerRoot.getVater().setRechterSohn(null);
}
if(neuerRoot.hatLinkenSohn())
{
neuerRoot.getVater().setRechterSohn(neuerRoot.getLinkerSohn());
neuerRoot.getLinkerSohn().setVater(neuerRoot.getVater());
}
if(root.hatLinkenSohn()&&root.getLinkerSohn()!=neuerRoot)
{
neuerRoot.setLinkerSohn(root.getLinkerSohn());
neuerRoot.getLinkerSohn().setVater(neuerRoot);
}
if(neuerRoot.hatLinkenSohn())
neuerRoot.getLinkerSohn().setVater(neuerRoot);
if(root.hatRechtenSohn())
{
neuerRoot.setRechterSohn(root.getRechterSohn());
neuerRoot.getRechterSohn().setVater(neuerRoot);
}
neuerRoot.setVater(null);
root=neuerRoot;
}
//Hat Root einen rechten Sohn, so wird das linkeste Blatt vom rechten Sohn, der neue Root
else if (knoten.hatRechtenSohn())
{
neuerRoot=getKnotenGanzLinks(knoten.getRechterSohn());
if(root.getRechterSohn()==neuerRoot)
{
neuerRoot.getVater().setRechterSohn(null);
}
else
{
neuerRoot.getVater().setLinkerSohn(null);
}
if(neuerRoot.getRechterSohn()!=neuerRoot)
{
if(neuerRoot.hatRechtenSohn())
{
neuerRoot.getVater().setLinkerSohn(neuerRoot.getRechterSohn());
neuerRoot.getRechterSohn().setVater(neuerRoot.getVater());
}
if(root.hatRechtenSohn())
{
neuerRoot.setRechterSohn(root.getRechterSohn());
neuerRoot.getRechterSohn().setVater(neuerRoot);
}
}
if(root.hatLinkenSohn())
{
neuerRoot.setLinkerSohn(root.getLinkerSohn());
neuerRoot.getLinkerSohn().setVater(neuerRoot);
}
}
if(root!=neuerRoot)
{
root=neuerRoot;
}
root.setVater(null);
}
/**
* Geh so lange links bis der Knoten keinen linken Sohn mehr hat
* @param knoten Der uebergebene Knoten
* @return der linkeste Sohn
*/
public Knoten getKnotenGanzLinks(Knoten knoten)
{
if(knoten.hatLinkenSohn())
{
getKnotenGanzLinks(knoten.getLinkerSohn());
}
else
{
knotenGanzLinks=knoten;
}
return knotenGanzLinks;
}
/**
* Geh so lange rechts bis der Knoten keinen rechten Sohn mehr hat
* @param knoten Der uebergebene Knoten
* @return der rechteste Sohn
*/
public Knoten getKnotenGanzRechts(Knoten knoten)
{
if(knoten.hatRechtenSohn())
{
getKnotenGanzRechts(knoten.getRechterSohn());
}
else
{
knotenGanzRechts= knoten;
}
return knotenGanzRechts;
}
}
Java:
/**
*
*/
*
*/
public class Knoten {
private Knoten linkerSohn;
private Knoten rechterSohn;
private Knoten vater;
private Object UebergabeObjekt;
public Knoten(Knoten linkerSohn, Knoten rechterSohn,Knoten vater, Object UebergabeObjekt) {
this.setLinkerSohn(linkerSohn);
this.setRechterSohn(rechterSohn);
this.vater=vater;
this.setInhalt(UebergabeObjekt);
}
public void setLinkerSohn(Knoten linkerSohn) {
this.linkerSohn = linkerSohn;
}
public Knoten getLinkerSohn() {
return linkerSohn;
}
public void setRechterSohn(Knoten rechterSohn) {
this.rechterSohn = rechterSohn;
}
public Knoten getRechterSohn() {
return rechterSohn;
}
/**
* @return the UebergabeObjekt
*/
public Object getInhalt() {
return UebergabeObjekt;
}
/**
* @param UebergabeObjekt
* the UebergabeObjekt to set
*/
public void setInhalt(Object UebergabeObjekt) {
this.UebergabeObjekt = UebergabeObjekt;
}
public boolean hatLinkenSohn() {
return linkerSohn!= null;
}
public boolean hatRechtenSohn() {
return rechterSohn != null;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return UebergabeObjekt.toString();
}
/**
* @return the vater
*/
public Knoten getVater() {
return vater;
}
/**
* @param vater the vater to set
*/
public void setVater(Knoten vater) {
this.vater = vater;
}
}
Java:
/**
*
*
* Faengt Fehler beim Dialog ab
*/
public class DialogException extends RuntimeException {
public DialogException() {
}
public DialogException(String arg0) {
super(arg0);
}
public DialogException(Throwable arg0) {
super(arg0);
}
public DialogException(String arg0, Throwable arg1) {
super(arg0, arg1);
}
}
Java:
/**
*
*/
import java.util.Comparator;
/*
*
*/
public class StringComperator implements Comparator<Object> {
/* (non-Javadoc)
* @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
*/
@Override
public int compare(Object uebergabeEins, Object uebergabeZwei) {
if(uebergabeEins.toString()==null && uebergabeZwei.toString()==null)
return 0;
if(uebergabeEins.toString()==null)
return 1;
if (uebergabeZwei.toString()==null)
return -1;
return uebergabeEins.toString().compareTo(uebergabeZwei.toString());
}
}
, aber wie komme ich auf den Vater ohne dieses Attribut?
