Warum funktioniert der in eine BST einzufügende Code nicht?

Question

Ich codiere die Einfügung in eine BST in C. Wenn ich den Baum durchquere, scheint der erste Ausschnitt unwirksam zu sein. Ich kann nicht verstehen, warum es nicht funktioniert. Dies funktioniert nicht:

void insert(Node* temp, int data) 
{ 
    if(temp==NULL) 
    temp=Newnode(data); 
    else if(data<temp->data) 
     insert(temp->left,data); 
    else if(data>temp->data) 
     insert(temp->right,data); 

} 

Dies funktioniert:

Node* insert(Node* temp, int data) 
{ 
    if(data<temp->data) 
     if(temp->left!=NULL) insert(temp->left,data); 
     else temp->left= Newnode(data); 
    else if(data>temp->data) 
     if(temp->right!=NULL) insert(temp->right,data); 
     else temp->right= Newnode(data); 
} 

HINWEIS: Ich #define Knoten struct Knoten verwendet haben. Newnode() weist einen neuen Knoten zu und funktioniert perfekt.

Answer 1

haben Sie einen Blick auf, was passiert, wenn man in NULL als Root-Wert übergeben:

temp eine neue Knoteninstanz zugeordnet ist. Die Zuweisung ist jedoch nur lokal zu insert(), so dass nach dem Aufruf die Zuordnung "gegangen" ist.

, Sie möchten die Insert-Methode Signatur
void insert(Node **temp, data)
und *temp = Newnode(data);
, um es, wie zu erwarten scheinen zu verwenden, zu ändern, zu arbeiten.

Answer 2

Streng genommen ist der zweite Weg auch nicht korrekt. Für die zwei Wege, die Sie gepostet haben:

1. Es gibt ein Problem mit Rekursion Ende Bedingung. Wenn temp NULL ist, erstellt der Code einen neuen Knoten. Es gibt jedoch keine Möglichkeit, dass der neu erstellte Knoten in BST an den übergeordneten Knoten angehängt werden kann.
2. Die Funktion Rückgabetyp ist Node *, aber es gibt keinen expliziten Code für die Rückgabe. Obwohl C standardmäßig die Rückgabe von Newnode als Rückgabewert für Insert verwendet, ist es nicht korrekt.

Hier sind zwei Versionen:

void insert(node **curr, int val) { 
    if(!(*curr)) { 
     *curr = Newnode(val); 
     return; 
    } 

    if(val < (*curr)->data) { 
     insert(&(*curr)->left, val); 
    } else if(val > (*curr)->data) { 
     insert(&(*curr)->right, val); 
    } 
} 

insert(&root, val); 

Dieser übergibt Doppelzeiger das oben erwähnte Problem zu lösen.

Node* insert(node *curr, int val) { 
    if(!curr) { 
     return Newnode(val); 
    } 

    if(val < curr->data) { 
     curr->left = insert(curr->left, val); 
    } else if(val > curr->data) { 
     curr->right = insert(curr->right, val); 
    } 

    return curr; 
} 

root = insert(root, val); 

Dieser verwendet die Rückgabewert-Zuweisung als Lösung.