BSTインサートの最後にリターンが必要なのはなぜですか？

Question

「リターンノード」がここに必要な理由はわかりません。スタックからの起動レコードを一番上にポップしていますか？

struct node* insert(struct node* node, int key) 
{ 
    if (node == NULL) return newNode(key); 

    /* Otherwise, recur down the tree */ 
    if (key < node->key) 
     node->left = insert(node->left, key); 
    else if (key > node->key) 
     node->right = insert(node->right, key); 

    /* return the (unchanged) node pointer */ 
    return node; 
} 

Answer 1

はい、それは言うことができます。しかし、より一般的には、あなたのプログラムが適切な位置にノードを作成してツリーにそれ自身を添付する必要があるときはいつでも、このようなことを言うことができます。これを行うには、新しいノードについて知る必要があります。これがリターンが助けになる場所です。

今や、そうするためには、struct node*を返さなければならないと思います。あなたはそれを宣言しました。 しかし、論理的には、新しく作成されたノードについて知っておく必要があり、ツリーに追加して追加する必要がない場合にのみ論理的に気づいたことがあります。しかし何？あなたはstruct node*を返すと言いました。あなたはそれを返すのです。あなた自身はこれを/* return the (unchanged) node pointer */とコメントしました。

スタックからのものなのか、それとも..？関数呼び出しの実装に集中するのではなく、一番上のフレームから戻ってきたことを安全に考えることができ、呼び出された関数インスタンスはその値を取得します。新しいノードでも、古いノードでも再割り当てできます。

Answer 2

このコードセクションは、挿入関数が再帰的に呼び出されるときにBST .returnノードにノードを挿入するためのものです。ノードが正しい位置になるとnewNodeが呼び出されます。その時点でnewNodeが作成されます値が挿入されますが、その後にそのnewNodeのアドレスをいくつかのnode-nextに戻す必要があります。