c++ - 二叉树栈溢出

Question

我根据 Alex Allain 的 example found here 制作了一个二叉树.它在向其中添加大约 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 更改为非递归的。通过将要进入堆栈的数据存储在其他数据结构中，每个递归函数都可以变成非递归函数。通过这种方式，您可以将堆用于这些数据，并且不会在堆栈上产生函数调用的开销(返回地址等)。您通常可以使用像堆栈一样使用的 vector 或列表:获取(并弹出) vector 的 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 和更多元素，所以你的实现中可能还有其他问题......

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

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