没有递归的二叉搜索树插入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;
}

我做了这个：

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

的（未使用）prev表示已意识到需要修补递归结果。正如其他人已经给出的解决方案一样，这里是使用指针别名的“理想”解决方案。

   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的极少数优点之一。

该&前缀运营商采取变量的地址。