G
Gast
Gast
ich bin gerade dabei, die Klasse BinarySearchTree um eine Methode toString zu erweitern, die eine Darstellung der einzelnen in dem Baum enthaltenen werte als String liefert (in inorder Reihenfolge).
ich hab hier jetzt mal das ganze programm reingetan, das auch funktioniert hat, bis ich meine toString Methode drangehängt hab... krieg die ganze zeit die fehlermeldung:
BinarySearchTree.java: cannot find symbol
symbol: method r()
location class BinarySearchTree.BSTNode
result = result + toString(root.r());
^
das gleich auch bei root.l...
wär super wenn mir jemand sagen könnte, was ich da falsch mach...
hab jetzt mal den ganzen Baum reingepostet, relevant sind aber nur die letzten paar zeilen...
ich hab hier jetzt mal das ganze programm reingetan, das auch funktioniert hat, bis ich meine toString Methode drangehängt hab... krieg die ganze zeit die fehlermeldung:
BinarySearchTree.java: cannot find symbol
symbol: method r()
location class BinarySearchTree.BSTNode
result = result + toString(root.r());
^
das gleich auch bei root.l...
wär super wenn mir jemand sagen könnte, was ich da falsch mach...
hab jetzt mal den ganzen Baum reingepostet, relevant sind aber nur die letzten paar zeilen...
Code:
public class BinarySearchTree {
protected class BSTNode {
protected Comparable value = null;
protected BSTNode left = null;
protected BSTNode right = null;
protected BSTNode(Comparable v, BSTNode l, BSTNode r) {
value = v;
left = l;
right = r;
}
protected boolean containsRecursive(Comparable o) {
// ist der angegebene Wert gleich dem Wert des aktuellen Knotens?
if (o.compareTo(this.value) == 0) {
// ja - wir haben den gesuchten Wert gefunden
return true;
} else {
// nein - wir müssen entweder im linken oder im rechten Unterbaum weitersuchen
if (o.compareTo(this.value) < 0) {
// der gesuchte Wert kann nur im linken Unterbaum sein
if (left == null) {
// es gibt keinen linken Nachfolger, der gesuchte Wert ist nicht enthalten
return false;
} else {
// im linken Unterbaum (rekursiv) weitersuchen
return left.containsRecursive(o);
}
} else {
// der gesuchte Wert kann nur im rechten Unterbaum sein
if (right == null) {
// es gibt keinen rechten Nachfolger, der gesuchte Wert ist nicht enthalten
return false;
} else {
// im rechten Unterbaum (rekursiv) weitersuchen
return right.containsRecursive(o);
}
}
}
}
protected boolean addRecursive(Comparable o) {
if (o.compareTo(this.value) == 0) {
return false;
} else {
if (o.compareTo(this.value) < 0) {
if (left == null) {
left = new BSTNode(o, null, null);
return true;
} else {
return left.addRecursive(o);
}
} else {
if (right == null) {
right = new BSTNode(o, null, null);
return true;
} else {
return right.addRecursive(o);
}
}
}
}
protected void print(int level) {
if (left != null) left.print(level + 1); // linken Unterbaum ausgeben
for (int i=0; i<level; i=i+1) System.out.print(" "); // Einrückung
System.out.println(this.value); // Knotenwert
if (right != null) right.print(level + 1); // rechten Unterbaum ausgeben
}
protected int size() {
int leftSize, rightSize;
if (left == null) {
leftSize = 0;
} else {
leftSize = left.size();
}
if (right == null) {
rightSize = 0;
} else {
rightSize = right.size();
}
return 1 + leftSize + rightSize;
}
protected int height() {
int leftHeight, rightHeight;
if (left == null) {
leftHeight = -1;
} else {
leftHeight = left.height();
}
if (right == null) {
rightHeight = -1;
} else {
rightHeight = right.height();
}
return 1 + Math.max(leftHeight, rightHeight);
}
}
protected BSTNode root = null;
public boolean containsRecursive(Comparable o) {
if (o == null) throw new IllegalArgumentException();
return (root != null) && root.containsRecursive(o);
}
public boolean contains(Comparable o) {
return this.containsRecursive(o);
}
public boolean containsIterative(Comparable o) {
if (o == null) throw new IllegalArgumentException();
BSTNode node = root;
while (node != null) {
// ist der angegebene Wert gleich dem Wert des aktuellen Knotens?
if (o.compareTo(node.value) == 0) {
// ja - wir haben den gesuchten Wert gefunden
return true;
} else {
// nein - wir müssen entweder im linken oder im rechten Unterbaum weitersuchen
if (o.compareTo(node.value) < 0) {
// der gesuchte Wert kann nur im linken Unterbaum sein
node = node.left;
} else {
// der gesuchte Wert kann nur im rechten Unterbaum sein
node = node.right;
}
}
}
// der gesuchte Wert ist nicht enthalten
return false;
}
public boolean addRecursive(Comparable o) {
if (o == null) throw new IllegalArgumentException();
if (root == null) {
root = new BSTNode(o, null, null);
return true;
} else {
return root.addRecursive(o);
}
}
public boolean add(Comparable o) {
return this.addRecursive(o);
}
public boolean addIterative(Comparable o) {
if (o == null) throw new IllegalArgumentException();
if (root == null) {
root = new BSTNode(o, null, null);
return true;
} else {
BSTNode node = root;
while (true) { // "Endlosschleife" wird durch return verlassen
if (o.compareTo(node.value) == 0) return false;
else if (o.compareTo(node.value) < 0) {
if (node.left == null) {
node.left = new BSTNode(o, null, null);
return true;
} else {
node = node.left;
}
} else {
if (node.right == null) {
node.right = new BSTNode(o, null, null);
return true;
} else {
node = node.right;
}
}
}
}
}
public void print() {
if (root != null) root.print(0);
}
public int size() {
if (root == null) return 0;
else return root.size();
}
public int height() {
if (root == null) return -1;
else return root.height();
}
public boolean isEmpty( )
{
return root == null;
}
public String toString(BSTNode root) {
String result = "";
if (root == null)
return result;
result = result + toString(root.l()) + " ";
result = result + root.toString() + " ";
result = result + toString(root.r());
return result;
}
}