Hallo,
für eine Hausaufgabe soll ich einen generischen binären Suchbaum erstellen. Das funktioniert auch schon so weit, bloß mit dem Löschen eines Objekts habe ich noch Probleme. Erstmal der Code:
Könnt ihr mir helfen a) das Element in Zeile 167 tatsächlich zu kopieren und
<s>b) herauszufinden, woher die NullPointerException kommt, die zurzeit geworfen wird?</s>
Edit zu b): Ich verstehe, woher die Exception kommt: dadurch, dass ich die Wurzel des Baumes verändere, verändert sich auch der Teilbaum, der eigentlich leer sein sollte - und ein nicht-leerer Knoten, dessen Kinder null sind, führt zu NullPointerExceptions 🙂
Vielen Dank im Vorraus!
Neele</quest></quest></t></t></t></t></t></t></t></t></t></t></t>
für eine Hausaufgabe soll ich einen generischen binären Suchbaum erstellen. Das funktioniert auch schon so weit, bloß mit dem Löschen eines Objekts habe ich noch Probleme. Erstmal der Code:
Java:
/**
* Yet another AVL tree implementation done in Java
* This one contains recursion to do its job
*
* @param <t> java generic wildcard
*/
public class GenericBinaryTree<t extends="" comparable<t="">> {
/**
* Das aktuelle T
*/
private T item;
/**
* Der linke Teilbaum
*/
private GenericBinaryTree<t> left;
/**
*Der rechte Teilbaum
*/
private GenericBinaryTree<t> right;
/**
* Konstruktor, erzeugt leere Liste
*/
public GenericBinaryTree() {
this.item = null;
this.left = null;
this.right = null;
}
/**
* Ueberprueft ob der Baum leer ist
*
* @return true, Baum ist leer
*/
public boolean isEmpty() {
return this.left == null && this.right == null;
}
/**
* Gibt die Anzahl der Elemente im Baum zurück
*
* @return die Groesse
*/
public int length() {
if (this.isEmpty()) {
return 0;
} else {
return (this.left.length() + this.right.length() + 1);
}
}
/**
* Prueft ob ein T in der Liste ist
*
* @param x das T
* @return true, x ist in der Liste enthalten
*/
public boolean isInList(T x) {
if (this.isEmpty()) {
return false;
} else if (this.item.equals(x)) {
return true;
} else {
return (this.left.isInList(x) || this.right.isInList(x));
}
}
/**
* Gibt das i-te T der Liste zurueck
*
* @param i der Index
* @return das i-te T
* @throws IndexOutOfBoundsException wenn i < 0 oder i >= length()
*/
public T getItem(int i) throws IndexOutOfBoundsException {
if (i < 0 || i >= this.length()) {
throw new IndexOutOfBoundsException();
} else if (i < this.left.length()) {
return this.left.getItem(i);
} else if (i > this.left.length()) {
return this.right.getItem(i - this.left.length() - 1);
} else {
return this.item;
}
}
/**
* Gets height of tree
*
* @return height
*/
public int height() {
if (this.isEmpty()) {
return 0;
} else {
int a = this.left.height();
int b = this.right.height();
return a < b ? b + 1 : a + 1;
}
}
/**
* Fuegt ein Element sortiert in den Baum ein
*
* @param x das Element
* @return der geaenderte Baum
*/
public GenericBinaryTree<t> insert(T x) {
if (x.equals(null)) {
return this;
}
if (this.isEmpty()) {
GenericBinaryTree<t> tmpleft = new GenericBinaryTree<t>();
GenericBinaryTree<t> tmpright = new GenericBinaryTree<t>();
this.left = tmpleft;
this.right = tmpright;
this.item = x;
return this;
} else if (this.item.compareTo(x) <= 0){
return this.right.insert(x);
} else {
return this.left.insert(x);
}
}
/**
* Loescht das erste vorkommen des Ts x
*
* @param x das T
* @return die geanderte Liste
*/
public GenericBinaryTree<t> delete(T x) {
if (!this.isInList(x)){
return this;
} else if (this.item.equals(x)) {
return this.delete();
} else if (this.item.compareTo(x) <= 0) {
return this.right.delete(x);
} else {
return this.left.delete(x);
}
}
/**
* Loescht die Wurzel des Baums
*
* @return die geanderte Liste
*/
public GenericBinaryTree<t> delete() {
if (this.isEmpty()) {
return this;
} else if (this.left.isEmpty()) {
this.item = this.right.item;
this.left = this.right.left;
this.right = this.right.right;
return this;
} else if (this.right.isEmpty()) {
this.item = this.left.item;
this.left = this.left.left;
this.right = this.left.right;
return this;
} else {
//TODO
T x = this.right.getItem(0); //this should be copied instead
this.left.delete(x);
this.item = x;
return this;
}
}
/**
*macht aus der Liste nen kurzen String
*(gezählte Elemente)
*
*@return String
*/
public String toShortString() {
String s = "";
int k = 0;
if (this.isEmpty()) {
s = "-empty- \n";
} else {
int j = 1;
for (int i = 0; i < this.length(); i++) {
if (i + 1 < this.length() && this.getItem(i).equals(this.getItem(i + 1))) {
j++;
} else {
s = s + k + " - " + this.getItem(i).toString() + " (" + j + "x)\n";
j = 1;
k++;
}
}
}
return s;
};
public String toString2(String str) {
String newstr = str + " -> " + this.item + "\n";
if (this.left != null) {
newstr += this.left.toString2(str + "l");
}
if (this.right != null) {
newstr += this.right.toString2(str + "r");
}
return newstr;
}
/**
*macht aus der Liste nen String
*
*@return String
*/
public String toString() {
String s = "";
if (this.isEmpty()) {
System.out.print( "-empty- \n");
} else {
for (int i = 0; i < this.length(); i++) {
System.out.print(s + i + " - " + this.getItem(i).toString() + "\n");
}
}
return s;
}
/**
* main method for testing purposes
*
* @param args commandline arguments
*/
public static void main(String[] args) {
GenericBinaryTree<quest> l = new GenericBinaryTree<quest>();
int[] a = {3, 2, 0, 1, 5, 4, 6};
int citm = a.length;
Quest[] itm = new Quest[citm];
System.out.println("Empty: (true) " + l.isEmpty());
System.out.println("Height: (0) " + l.height());
System.out.println("Length: (0) " + l.length());
System.out.println("Items to add...");
for (int i = 0; i < citm; i++) {
itm[i] = new Quest("Quest " + a[i], "Prequest " + i, "Item " + i, i+2);
//itm[i].setName("Item No. " + ((int) (Math.random() * 100)) );
System.out.println(i + ". " + itm[i]);
}
System.out.println("\nList stuff...");
for (int i = 0; i < citm; i++) {
l.insert(itm[i]);
System.out.println("length: " + l.length());
System.out.println(l);
}
System.out.println("== GET FIRST ITEM");
System.out.println(l.getItem(0));
System.out.println("== GET ITEM BY INDEX");
for (int i = 0; i < citm; i++) {
System.out.println("getItem(" + i + ") -> " + l.getItem(i));
}
System.out.println(l.toString2(""));
System.out.println("== DELETE FIRST");
l.delete();
System.out.println("deleted");
System.out.println(l);
System.out.println(l.toString2(""));
System.out.println("== CHECK IF IN LIST");
for (int i = 0; i < citm; i++) {
if (l.isInList(itm[i])) {
System.out.println(" found \"" + itm[i] + "\"");
} else {
System.out.println("not found \"" + itm[i] + "\"");
}
}
System.out.println("== DELETE ALL");
for (int i = 0; i < citm; i++) {
System.out.println("delete(" + itm[i] + ")");
l.delete(itm[i]);
System.out.println("deleted");
System.out.println(l);
}
System.out.println("== END OF TEST");
}
}Könnt ihr mir helfen a) das Element in Zeile 167 tatsächlich zu kopieren und
<s>b) herauszufinden, woher die NullPointerException kommt, die zurzeit geworfen wird?</s>
Edit zu b): Ich verstehe, woher die Exception kommt: dadurch, dass ich die Wurzel des Baumes verändere, verändert sich auch der Teilbaum, der eigentlich leer sein sollte - und ein nicht-leerer Knoten, dessen Kinder null sind, führt zu NullPointerExceptions 🙂
Vielen Dank im Vorraus!
Neele</quest></quest></t></t></t></t></t></t></t></t></t></t></t>
Zuletzt bearbeitet:
