BSTに挿入するコードが機能しないのはなぜですか？

Question

私はCのBSTへの挿入をコーディングしています。ツリーをたどると、最初のスニペットは無効に見えます。私はなぜそれが動作しないのか理解できません。 これは動作しません：

は

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); 

} 

これは動作します：

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); 
} 

注：私はの#defineノード構造体のノードを使用していました。 Newnode（）は新しいノードを割り当て、完全に動作します。

Answer 1

はちょうどあなたがルート値としてNULLに渡すときに何が起こるかを見てみましょう：

tempは、新しいノードのインスタンスが割り当てられています。ただし、代入はのローカルのみであるため、呼び出しが返された後に代入が「不在」になります。

あなたは
void insert(Node **temp, data)
にあなたのinsertメソッドのシグネチャを変更し、あなたが期待するように見えるとして、それを動作させるために *temp = Newnode(data);
を使用する場合があります。

Answer 2

厳密に言えば、2番目の方法も正しくありません。あなたが投稿した2つの方法について：

1. 再帰終了条件に問題があります。 tempがNULLの場合、コードは新しいNodeを作成します。ただし、新しく作成したノードをBSTの親ノードに接続する方法はありません。
2. 関数の戻り値の型はNode *ですが、戻り値を返す明示的なコードはありません。デフォルトでは、CはInsertの戻り値としてNewnodeからの戻り値を取りますが、正しくありません。

   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); 
   

   この1つは、上述した問題を解決するための二重ポインタを渡す：

ここで二つのバージョンです。

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); 

これは解決策として返品割り当てを使用します。