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

这是迭代插入元素的代码。由于要插入的新元素已经 created/allocated，因此没有必要在创建元素后立即初始化结构的 left/right 字段。

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

Answer 2

prev 的（未）使用表示意识到递归结果需要修补。其他人已经给出了解决方案，这里是 "ideal" 解决方案，使用指针别名。

   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;

current会在终点指向root，或者left/right的一个节点；为空。

请注意，别名的这种用法在某些其他语言中不存在，例如 java。 C.

为数不多的优点之一

& 前缀运算符获取变量的地址。

没有递归的二叉搜索树插入 C

Binary Search Tree Insertion C without recursion

c

iteration

binary-tree

insert

binary-search-tree