二进制树堆溢出

Question

我根据Alex Allain的例子找到了一个二叉树.在向其添加约5000-6000个元素后,它会引发堆栈溢出异常.知道如何防止堆栈溢出？原因是Insert()呼叫本身是递归的.

2013年3月6日更新

这是我如何重构代码以避免堆栈溢出:

void Insert(Key_T key, Value_T val, QuickMapNode<Key_T, Value_T> *leaf)
{
    while (true)
        if(key < leaf->key)
        {
            if(leaf->left) leaf = leaf->left;
            else
            {
                leaf->left = new QuickMapNode<Key_T, Value_T>;
                leaf->left->key = key;
                leaf->left->val = val;
                leaf->left->parent = leaf;
                leaf->left->left = NULL;    // Sets the left child of the child node to null
                leaf->left->right = NULL;   // Sets the right child of the child node to null
                break;
            }  
        }
        else if (key >= leaf->key)
        {
            if(leaf->right) leaf = leaf->right;
            else
            {
                leaf->right = new QuickMapNode<Key_T, Value_T>;
                leaf->right->key = key;
                leaf->right->val = val;
                leaf->right->parent = leaf;
                leaf->right->left = NULL;  // Sets the left child of the child node to null
                leaf->right->right = NULL; // Sets the right child of the child node to null
                break;
            }
        }
}

Answer 1

就像ÖöTiib所说,你应该改变insert为不是递归的.通过将存储在堆栈中的数据存储在某些其他数据结构中,可以将每个递归函数转换为非递归函数.这样你可以使用堆来处理这些数据,并且没有堆栈上的函数调用开销(返回地址等).你经常可以使用像堆栈一样使用的向量或列表:take(和pop)back()获取当前参数的向量,并且在当前代码将递归调用自身的位置,push_back()您将传递给递归函数调用.

以下是insert()链接中作为迭代版本的方法:

void btree::insert(int key, node *leaf)
{
  std::list<node*> leafs;
  leafs.push_back(leaf);

  while (leafs.size() > 0)
  {
    leaf = leafs.back();
    leafs.pop_back();
    if(key < leaf->key_value)
    {
      if(leaf->left!=NULL)
        leafs.push_back(leaf->left);
      else
      {
        leaf->left=new node;
        leaf->left->key_value=key;
        leaf->left->left=NULL;    //Sets the left child of the child node to null
        leaf->left->right=NULL;   //Sets the right child of the child node to null
      }  
    }
    else if(key>=leaf->key_value)
    {
      if(leaf->right!=NULL)
        leafs.push_back(leaf->right);
      else
      {
        leaf->right=new node;
        leaf->right->key_value=key;
        leaf->right->left=NULL;  //Sets the left child of the child node to null
        leaf->right->right=NULL; //Sets the right child of the child node to null
      }
    }
  }
}

我运行代码,它似乎工作.它比递归版本要慢得多,不知道为什么会这样......两个版本的10000和更多元素都可以正常工作,所以你的实现可能还有其他错误......

实际上,当像我们这样遍历二叉树时,不需要存储任何先前的信息,因为我们不进行任何回溯.一旦找到新元素的位置,我们就完成了.所以我们可以完全摆脱列表/向量:

void btree::insert(int key, node *leaf)
{
  while (leaf != NULL)
  {
    if(key < leaf->key_value)
    {
      if(leaf->left!=NULL)
        leaf = leaf->left;
      else
      {
        leaf->left=new node;
        leaf->left->key_value=key;
        leaf->left->left=NULL;    //Sets the left child of the child node to null
        leaf->left->right=NULL;   //Sets the right child of the child node to null
        return;
      }  
    }
    else if(key>=leaf->key_value)
    {
      if(leaf->right!=NULL)
        leaf = leaf->right;
      else
      {
        leaf->right=new node;
        leaf->right->key_value=key;
        leaf->right->left=NULL;  //Sets the left child of the child node to null
        leaf->right->right=NULL; //Sets the right child of the child node to null
        return;
      }
    }
  }
}