Hallo Hallo erstmal =D. Habe mich nun endlich mal durchgerungen mich in diesem tollen Forum anzumelden. Scheinen ja schon versierte Leute unterwegs zu sein.
Ich habe folgendes Problem, und finde einfach nicht die Ursache......
Ich habe einen normalen Binärbaum implementiert. Die Knoten haben einen schlüssel und einen Inhalt. Beides sind alg. Objekte welche beim einfügen eines Knotens übergeben werden. Der Knackpunkt liegt darin, das als Knotenschlüssel kein primitiver Datentyp wie int verwendet werden soll, sondern Objekte (welche natürlich eine compareTo Methode haben damit man Sie vergleichen kann).
Zum testen habe ich als Schlüsselobjekt die Containerklasse Integer verwendet. Nun findet mein Code allerdings nur den Knoten mit dem gesuchten Inhalt wenn er die Wurzel des Baums ist.
Das Einfügen von Knoten und Ausgeben des Baumes klappt jedoch wunderbar.
Ich füge mal die 3 Klassen an ....
Ich hoffe das mir jemand die Antwort für mein Problem geben kann und bedanke mich bereits im Vorraus.
Grüsse =D
Ich habe folgendes Problem, und finde einfach nicht die Ursache......
Ich habe einen normalen Binärbaum implementiert. Die Knoten haben einen schlüssel und einen Inhalt. Beides sind alg. Objekte welche beim einfügen eines Knotens übergeben werden. Der Knackpunkt liegt darin, das als Knotenschlüssel kein primitiver Datentyp wie int verwendet werden soll, sondern Objekte (welche natürlich eine compareTo Methode haben damit man Sie vergleichen kann).
Zum testen habe ich als Schlüsselobjekt die Containerklasse Integer verwendet. Nun findet mein Code allerdings nur den Knoten mit dem gesuchten Inhalt wenn er die Wurzel des Baums ist.
Das Einfügen von Knoten und Ausgeben des Baumes klappt jedoch wunderbar.
Ich füge mal die 3 Klassen an ....
Java:
public class Node {
private Object key;
private Object data;
private Node left, right;
public Node(Object obj) throws Exception { // wenn Inhalt und Schlüssel gleich sind
this(obj, obj);
}
public Node(Object key, Object obj) throws Exception {
if (obj == null || key == null) {
throw new Exception("exc");
} else {
this.key = key;
this.data = obj;
}
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public Object getKey() {
return key;
}
public Object getData() {
return data;
}
public int compareTo(Object n) {
if (((Comparable) (this.getKey())).compareTo((Comparable) ( ((Node)n).getKey())) < 1)
return -1;
else if (((Comparable) (this.getKey())).compareTo((Comparable) ( ((Node)n).getKey())) > 1)
return 1;
else
return 0;
}
public String toString() {
return ("[" + key.toString() + ":(" + data.toString() + ")]-");
}
}
Java:
public class BinTree2 {
private Node root;
private Node comp; // wird beim suchen für insert() hinterlegt. Ist letzter besuchter Knoten.
private String temp;
public BinTree2() {
this.root = null;
}
public boolean insert(Node newNode) throws Exception {
if (newNode == null)
return false;
else {
if (root == null) // root leer
root = newNode;
else { // root schon vorhanden
if (searchKey(newNode.getKey()) == true) { // schon vorhanden;
// rechts anhaengen
newNode.setRight(comp.getRight());
comp.setRight(newNode);
} else { // noch nicht vorhanden; check groesser kleiner
if (newNode.compareTo(comp) < 0) // links einsetzen
comp.setLeft(newNode);
else
comp.setRight(newNode);
}
}
return true;
}
}
public boolean searchKey(Object k) throws Exception { // durchsucht KEYS
return searchKey(k, root);
}
private boolean searchKey(Object k, Node tempRoot) throws Exception { // durchsucht
// KEYS
comp = tempRoot; // wird gebraucht in insert !!!!!!!
if (comp.getKey() == k) // gefunden
return true;
else { // nicht gefunden
if (((Comparable) k).compareTo(((Comparable) (comp.getKey()))) < 0) { // k
// <
// tempRoot.key
if (comp.getLeft() != null)
searchKey(k, comp.getLeft());
} else { // k > tempRoot
if (comp.getRight() != null)
searchKey(k, comp.getRight());
}
}
return false;
}
public String toString() {
temp = "";
return (toString(root));
}
public String toString(Node tempRoot) {
if (tempRoot.getLeft() != null)
toString(tempRoot.getLeft());
temp += "\n" + tempRoot.toString();
if (tempRoot.getRight() != null)
toString(tempRoot.getRight());
return temp;
}
}
Java:
public class BinTreeTest {
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
BinTree2 bt = new BinTree2();
Node n;
Integer iii = new Integer(4111);
Artikel d = new Artikel(iii, "bier", 554);
n = new Node(iii, d);
bt.insert(n);
Integer jjj = new Integer(4211);
Artikel e = new Artikel(jjj, "holz", 900);
n = new Node(jjj, e);
bt.insert(n);
System.out.println("--> toString(): " + bt.toString());
System.out.println("--> Suche Art. 4211: " + bt.searchKey(jjj) );
}
}Ich hoffe das mir jemand die Antwort für mein Problem geben kann und bedanke mich bereits im Vorraus.
Grüsse =D
