二元搜索树插入C无递归

我是新来的页面，我真的坚持在我的大学的作业重新创建一个函数，插入节点到树没有递归。我已经给了递归方法，我需要将其转换为迭代。这是给定的递归代码：二元搜索树插入C无递归

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

它工作的第一要素，但它不保存其余的元素。任何想法？在此先感谢

来源

2016-04-22 Ilias Mentz

对于非根情况，您的代码永远不会将'newnode'指针指定为树中已有节点的子节点。 –

@Roux，虽然他可能打算这样做，但它不会解决他的问题，因为'temp'只是一个局部变量。 –

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.

&前缀运算符取其变量的地址的几个优点之一。

来源

2016-04-22 14:03:50

A **（**在你的代码的倒数第二行缺少 –

@GerardoZinno谢谢，更正 –

@JoopEggen这是工作完美非常感谢你的帮助！ –

这是迭代插入元素的代码。由于要插入的新元素已经被创建/分配，所以只要元素被创建，就没有必要不初始化结构的左/右字段。

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

来源

2016-04-22 13:56:27

非常感谢你！ –

二元搜索树插入C无递归

回答

相关问题