Einsetzen in einen Baum

Question

EDIT: richtige Lösung:

void add(Student s) 
{ 
    if(root == null) 
     root = new TreeNode(s); 
    else 
     insert(root,s);   
} 

void insert(TreeNode tn, Student s) 
{ 
    if(tn.sVal.compareTo(s) > 0) 
    { 
     if(tn.left != null) 
      insert(tn.left, s);    
     else 
     { 
      tn.left = new TreeNode(s); 
      tn.left.parent = tn; 
     } 
    } 
    else if(tn.sVal.compareTo(s) < 0) 
    { 
     if(tn.right != null) 
      insert(tn.right, s); 
     else 
     { 
      tn.right = new TreeNode(s); 
      tn.right.parent = tn; 
     } 
    } 
    balance(tn); 
} 

---

Ich versuche, in einen binären Baum Einfügen der folgenden Verfahren:

void add(Student s) 
    { 
     insert(root,s); 
    } 

private void insert(TreeNode t, Student s) 
{   
    if(t == null) 
     t = new TreeNode(s);   
    else if(t.sVal.compareTo(s) > 0) 
     insert(t.right, s); 
    else if(t.sVal.compareTo(s) < 0) 
     insert(t.left,s);     
} 

jedoch der Baum bleibt leer, und ich kann nicht herausfinden, warum. Ich hasse es, so vage zu sein, aber ich kann keinen Fehler in der Logik finden. Was vermisse ich?

Answer 1

Hier ist ein großer Tipp: Nehmen Sie diese Änderung zuerst, dann von dort debuggen:

if (t == null) 
    throw new IllegalArgumentException(); 

Und einen noch größeren Hinweis: Wenn Sie den neuen Knoten erstellen, müssen Sie auch einen Verweis auf seine Eltern, so dass Sie kann es zum Eltern hinzufügen.

Answer 2

Ihr Code zeigt ein grundlegendes Missverständnis von Java, und ich versuche Ihnen zu helfen, zu verstehen, wo Sie falsch liegen.

Wenn Sie insert(root,s) nennen, vorbei sind Sie ein Referenz auf den gleichen TreeNode Objekt-root von spitz. Wenn Sie dann t = new TreeNode(s) innerhalb der insert-Funktion zuweisen, weisen Sie eine neue Referenz zu t, NOT zu zu.

Java ist pass-by-value, und im Falle von Objekten bedeutet das, dass es den Wert der Referenz übergibt. Wenn Sie C kennen, können Sie es sich als Zeiger vorstellen. Es übergibt die Speicheradresse und nicht den Zeiger, der auf die Speicheradresse zeigt.

Answer 3

Es ist ein Zeigerproblem. Wenn Sie den Zeiger a mit dem Operator = neu definieren, gehen alle früheren Verweise auf a verloren. Um diese Verweise zu behalten, müssen Sie entweder das Objekt mithilfe von Elementfunktionen (Klassenmethoden in Java) ändern oder Code in direkt schreiben, um die Verweise zu korrigieren.

Einfach gesagt, wirkt sich die Neudefinition eines Zeigers nur auf diesen Zeiger aus. Alles, was bereits auf den Zeiger verweist, wird nicht aktualisiert werden.

Pseudocode Beispiel:

Node a = new Node("hello") 
Node b = a 
a = new Node("goodbye") 

print(a) // this prints "goodbye" 
print(b) // this prints "hello" 

Damit b auf die neue a zeigen, müssen Sie b = a schreiben.

Nachdem Sie das sortiert haben, müssen Sie Ihre insert() Methode neu schreiben. Da ein Baum rekursiv ist, sollte eine rekursive insert() Methode den Zweck erfüllen. Es gibt eine Vielzahl von Online-Ressourcen für rekursive Tree-Implementierungen, wenn Sie sie benötigen: Recursive Tree Java