Ich kann keinen neuen Knoten in den Binärbaum einfügen

Question

Ich glaube, meine Einfügefunktion ist richtig, aber es sieht so aus, als ob der neue Knoten nicht in den Baum eingefügt wird. Ich konnte nicht herausfinden, wo der Fehler ist. Ich schätze jede Hilfe, danke.

Es ist die Deklaration von Knoten und Baum:

class Node{ 
    int key; 
    Node *right, *left; 
} 

class Tree{ 
public: 
     int init(); 
     Node *root; 
     Node *insert(int key, Node *p); 
}; 

gibt es die Funktionen:

int Tree::init(){ 
    this->root = NULL; return 1; 
} 

Node *Tree::insert(int key, Node *p){ 
    if(p == NULL){ 
    Node *novo = new Node(); 
    novo->key = key; 
    novo->left = NULL; 
    novo->right = NULL; 
    p = novo; 
    } 
    else if(key < p->key){ p->left = insert(key, p->left); } 
    else if(key > p->key){ p->right = insert(key, p->right); } 
    else{ cout << "Error: key already exist" << endl; } 

return p; 
} 

Wenn ich die Funktion im Haupt nennen, es sieht aus wie es nicht die neuen Anknüpfungspunkt node

Answer 1

In Ihrer Funktion insert(), wenn der Baum leer ist oder wenn Sie den letzten Knoten erreicht haben, crea te einen neuen Knoten:

if(p == NULL){ 
    Node *novo = new Node(); 
    novo->key = key; 
    novo->left = NULL; 
    novo->right = NULL; 
    p = novo;    // ouch !!!! 
    } 

Leider ist die Aussage p=novo nur aktualisiert die lokalen Parameter p Ihre Funktion. Ihr Wert wird verschwinden, sobald Sie von der Funktion zurückkehren. Der Zeiger, mit dem Sie Ihre Funktion aufgerufen haben, wird nicht aktualisiert. Die Wurzel Ihres Baumes bleibt also NULL (oder der linke/rechte Zeiger des letzten Knotens).

Um den Effekt zu erhalten, die Sie erwarten (dh Ihre p assigment aktualisiert den Wurzelzeiger oder den Zeiger/rechts des letzten Knotens nach links), müssen Sie die Signatur ändern:

Node *insert(int key, Node *& p); // p is passed by reference 

Dieser Wille übergeben Sie den Zeiger durch Verweis. Durch das Ändern von p wird der Zeiger geändert, mit dem Sie die Funktion aufgerufen haben, und der Effekt der Einfügung bleibt erhalten.