3

我根据此处找到的 Alex Alllain 的示例制作了一棵二叉树。在向其中添加大约 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;
            }
        }
}
4

4 回答 4

5

就像 Öö Tiib 所说，你应该改变insert为不递归。通过将要进入堆栈的数据存储在其他数据结构中，每个递归函数都可以变成非递归函数。这样，您可以将堆用于这些数据，并且没有堆栈上的函数调用开销（返回地址等）。您通常可以使用像堆栈一样使用的向量或列表：获取（并弹出）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;
      }
    }
  }
}
于 2013-03-05T19:59:33.280 回答
1

使算法insert不是递归的。您只需要搜索要插入的位置，因此您不需要为此调用堆栈。

于 2013-03-05T19:53:20.417 回答
1

由于缺乏提供的细节而进行猜测：假设最坏的情况，在 6000 次插入之后，堆栈深度全部为 6000 次递归调用。假设一个合理的堆栈帧大小可能为 20 字节 - 那么堆栈大小为 6000 * 20 = 120,000 字节。如果堆栈帧实际上是 160 字节（大 8 倍），则堆栈大小为 6000 * 160，略小于 1MB。我想知道......你的元素数量有限制吗？分配的堆栈大小是多少？
上面的评论告诉你如何实际解决问题（平衡树）。我可能会补充一点，几乎任何递归算法都可以转换为迭代算法——它没有那么优雅，需要努力才能让它正确，但是你不会填满堆栈。但是，如果确实存在（不仅仅是您认为存在）输入元素数量的限制，那么在我看来，您可以确定用于插入的堆栈框架的大小并使堆栈大小足够大以适合 #elements *堆栈帧大小，最坏的情况，加上堆栈上的任何额外内容。

于 2013-03-05T20:04:54.163 回答
0

如上所述，最可能的原因是由于递归插入调用过多导致堆栈溢出

以下是不同的选项

  1. 使用自平衡树http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

  2. 使用非递归树体面的算法。看这个例子使用 c++ 在二叉树中的非递归添加函数

于 2013-03-05T20:00:23.943 回答