バイナリ検索ツリー再帰のない挿入C

Question

私はこのページの初心者です。大学の宿題で、再帰なしでノードをツリーに挿入する機能を再構築することに本当に悩まされています。私は再帰的方法を与えられており、反復に変換する必要があります。これは、与えられた再帰コード：

TreeNode *InsertTree(TreeNode *root, TreeNode *newnode) 
{ 
    if (!root) 
    { 
     root = newnode; 
     root->left = root->right=NULL; 
    } 
    else if (newnode->entry < root->entry) 
    { 
     root->left = InsertTree(root->left, newnode); 
    } 
    else 
    { 
     root->right = InsertTree(root->right, newnode); 
    } 
    return root; 
} 

と私はこの1つを作った：

TreeNode *InsertTree(TreeNode *root, TreeNode *newnode) 
{ 
    if (!root) 
    { 
     root = newnode; 
     root->left = root->right=NULL; 
    } 
    else 
    { 
     TreeNode * temp = root, *prev = NULL; 

     while(temp) 
     { 
     if (temp->entry < newnode->entry) 
      temp = temp->right; 
     else 
      temp = temp->left; 
     } 
     newnode; 
     temp->left = temp->right = NULL; 
    } 
    return root; 
} 

それは最初の要素のために動作しますが、それは、残りの要素を保存しません。 アイデア ありがとうございます

Answer 1

（UN）使用は、再帰的な結果にパッチを適用する必要があることを意識を示しています。既に他の人が解答を与えているように、ここではポインターエイリアスを使った "理想的な"解です。

TreeNode **current = &root; 
    while (*current) 
    { 
     if (newnode->entry < (*current)->entry) 
     { 
      current = &(*current)->left; 
     } 
     else 
     { 
      current = &(*current)->right; 
     } 
    } 
    *current = newnode; 
    newnode->left = newnode->right = NULL; 
    return root; 

現在はルートの終点で、ノードの左/右になります。ヌルです。

このような別名の使用は、javaなどの他の言語では存在しないことに注意してください。 Cのごくわずかな利点の1つprefixprefix-operatorは、変数のアドレスを取ります。

Answer 2

これは要素を繰り返し挿入するためのコードです。挿入される新しい要素は既に作成/割り当てされているので、要素が作成されるとすぐに構造体の左/右のフィールドを初期化しない点はありません。 prevの

TreeNode *InsertTree(TreeNode *root, TreeNode *newnode){ 

     //assuming newnode->left/right already == NULL 
     if(root==NULL){ 
      root = newnode; 
     } 
     else { 
      TreeNode * prev = NULL; 
      TreeNode * curr = root; 
      while(curr != NULL){ 
       prev = curr; 
       if(curr -> entry < newnode -> entry) curr = curr -> right; 
       else curr = curr -> left; 
      } 
      if (prev -> entry < newnode -> entry) prev -> right = newnode; 
      else prev -> left = newnode; 

     } 
     return root; 
    }