Insert Methode im Baum + Rekursion

[Gast]

Hi,

package util;
import courseadmin.Student;
public class BinaryTree {
BinaryNode root;

public BinaryTree()
{
root=new BinaryNode(null,null,new Student("Klaus","Westermann"));
}
public BinaryNode getRoot() {

return root;
}
public void insert(Object p ,BinaryNode pos)
{
if(pos==null)
{


pos=new BinaryNode(null,null,p);
Student s=(Student) pos.item;
System.out.println("Trage " +s.getForeName());
return;
}
if(root.isLess(p)==true)
{ System.out.println("Links");
insert(p,pos.left);
}
else
{
System.out.println("Right");
insert(p,pos.right);

}


}


Aus der Main:
BinaryTree t=new BinaryTree();
BinaryNode root=t.getRoot();
Student st=new Student("Theo","Test");
Student ts=new Student("Alfer","Alda");
Student test=new Student("Tim ","Lewen");

t.insert(st, root);
t.insert(ts, root);
t.insert(test, root);


Mich verwundert die Ausgabe nämlich:
Konstruktor
Right
Trage Theo
Links
Trage Alfer
Right
Trage Tim

Spätestens beim dritten Einträg hätte ich erwartet, dass zwei links oder rechts hintereinstehen hätte.

Wo liegt mein Gedankenfehler?

[Gast]

Du veränderst deinen Baum nirgends. Du gehst zwar (theoretisch) durch den Baum, bis du eine freie Stelle gefunden hast (pos ist null). Dann setzt du aber pos auf das Objekt, das du dort speichern willst. Das hat aber überhaupt keinen Sinn, denn deine lokale Variable pos hat gar nichts mit dem Node zu tun, unter dem du einen neuen Knoten einfügen willst (denn pos ist eine Kopie der Referenz, die den Wert null hat, nicht die im Objekt gespeicherte Referenz selber).

Warum verlagerst du die insert-Methode nicht in die Knoten-Klasse? Dann gehst du solange rekursiv durch die Knoten, bis du eine passende Stelle gefunden hast. Jetzt kannst du (ohne die Kapselung zu verletzen) die Objektvariable im Knoten setzen, die die Kinder des aktuellen Knoten speichert.

Ansonsten könntest du mit Referenzen arbeiten, das dürfte aber hässlich werden. Oder du musst schon vor dem Rekursieren (bei "if(root.isLess(p)==true)" irgendwo) überprüfen, ob die Referenz auf den entsprechenden Kind-Knoten null ist und ihn dort umsetzen (mit einer Setter-Methode o. ä.). Sobald du nämlich den nächsten Rekursionsschritt machst, vergisst du den Knoten, den du verändern willst.

[Gast]

Hi,
werden nicht nur primative Datentypen in java wie int per call by value übertragen? BinaryNode ist eine Klasse also sollte sie per call by reference übertragen werden und ich somit dürfte das das objekt manipulieren können.

Ansonsten werde ich deinen vorschlag mal umsetzen

[Sephiroth]

@Gast #2: Was soll die Insert-Methode in der Node-Klasse? o.0 Laß die beim Baum, da gehört sich auch rein.

if(root.isLess(p)==true)
da liegt der Fehler. root muß pos sein. man vergleicht den schlüssel des aktuellen knotens mit dem des neuen, einzufügenden knotens.

überleg dir auch mal was passiert, wenn du einen bereits vorhanden schlüssel eintragen willst.

[Gast]

@Sephiroth
Nach Aufgabenstellung soll der Baum nicht 100% sortiert sein, sondern es
soll, wenn der Studentenname vom lexikalischen Wert kleiner ist als der von der Wurzel,links von der Wurzel eingefügt werden,ansonsten rechts.Falls dort schon Einträge sind, sollen diese übersprungen werden.

[Gast]

übrigens mit

public BinaryNode insert(Object p,BinaryNode node)
{
if(node==null)
{

node=new BinaryNode(null,null,p);
Student s=(Student)runner.item;
System.out.println("Trage " +s.getForeName());
return node;
}
if(root.isLess(p)==true)
{ System.out.println("Links");
node.left=insert(p,node.left);
}
else
{
System.out.println("Right");
node.right=insert(p,node.right);

}
return node;


}

funktioniert es.