12

例如，如果我们通过以下函数遍历一棵相当大的树，则可能会出现堆栈溢出。

void inorder(node* n)
{
  if(n == null) return;
  inorder(n->l);
  n->print();
  inorder(n->r); 
}

如何在函数中添加条件或其他内容以防止发生这种溢出？

4

7 回答 7

6

如果这确实是一个问题，请考虑迭代而不是递归。

http://en.wikipedia.org/wiki/Tree_traversal

看到那里的psedo代码迭代iterativeInorder iterativePreorder iterativePostorder

基本上在while循环中使用自己的列表作为栈数据结构，可以有效的替代函数递归。

于 2013-07-01T05:12:39.380 回答
2

除了用堆栈的显式管理（使用）替换递归之外，没有可移植的解决方案 std::vector<Node*>。不可移植，您可以使用静态变量跟踪深度；如果您知道最大堆栈大小，以及每次递归占用多少堆栈，那么您可以检查深度是否不超过该值。

许多系统，如 Linux 和 Solaris，您无法预先知道最大堆栈深度，因为堆栈是动态分配的。然而，至少在 Linux 和 Solaris 下，一旦内存被分配给堆栈，它将保持分配状态并继续影响堆栈。所以你可以在程序开始时进行相当深入的递归（可能会崩溃，但在做任何事情之前），然后稍后检查这个值：

static char const* lowerBound = nullptr;

//  At start-up...
void
preallocateStack( int currentCount ) {
{
    char dummyToTakeSpace[1000];
    -- currentCount;
    if ( currentCount <= 0 ) {
        lowerBound = dummyToTakeSpace;
    } else {
        preallocateStack( currentCount - 1 );
    }
}

void
checkStack()
{
    char dummyForAddress;
    if ( &dummyForAddress < lowerBound ) {
        throw std::bad_alloc();   //  Or something more specific.
    }
}

您会注意到，该代码中存在一些未定义/未指定行为的情况，但我已经成功使用过几次（在 Sparc 上的 Solaris 下，但 PC 上的 Linux 工作方式完全相同）看待）。事实上，它几乎可以在以下任何系统上工作： - 堆栈向下增长，并且 - 局部变量在堆栈上分配。因此，它也可以在 Windows 上运行，但如果它无法分配初始堆栈，您将不得不重新链接，而不是在盒子上的活动较少（或更改ulimits）时运行程序（因为堆栈Windows 上的大小在链接时是固定的）。

编辑：

关于使用显式堆栈的一条评论：某些系统（包括 Linux，默认情况下）过度使用，这意味着您在扩展std::vector<>;时无法可靠地得到内存不足错误。系统会告诉 std::vector<>它内存在那里，然后在程序尝试访问它时给它一个段冲突。

于 2013-07-01T09:42:14.133 回答
1

关于递归的事情是，你永远不能保证它永远不会溢出堆栈，除非你可以对内存的（最小）大小和输入的（最大）大小设置一些界限。但是，您可以做的是保证如果您有无限循环，它将溢出堆栈...

我看到你的“if() return;” 终止条件，因此只要树的每个分支都以空值结尾，就应该避免无限循环。因此，一种可能性是格式错误的输入，其中树的某些分支永远不会达到空值。（例如，如果您的树数据结构中有一个循环，就会发生这种情况。）

我看到的唯一另一种可能性是您的树数据结构对于可用的堆栈内存量来说太大了。（注意这是虚拟内存，可以使用交换空间，因此不一定是 RAM 不足的问题。）如果是这种情况，您可能需要提出其他一些非递归的算法方法。尽管您的函数占用的内存很小，但除非您省略了它所做的一些额外处理，否则您的树必须非常深才能成为问题。（注意这里的问题是最大深度，而不是节点总数。）

于 2013-07-01T04:59:24.730 回答
1

您可以增加操作系统的堆栈大小。ulimit如果您在类 Unix 环境中，这通常是通过配置的。

例如，在 Linux 上，您可以ulimit -s unlimited将堆栈的大小设置为“无限”，尽管 IIRC 存在硬限制，并且您不能将整个内存专用于一个进程（尽管下面链接中的答案之一提到了无限量） .

我的建议是运行ulimit -s它将为您提供堆栈的当前大小，如果您仍然遇到堆栈溢出，那么该限制将加倍，直到您满意为止。

看看这里、这里和这里，更详细地讨论堆栈的大小以及如何更新它。

于 2013-07-01T05:19:10.683 回答
1

如果您有一棵非常大的树，并且您遇到了使用递归遍历超出堆栈的问题，那么问题很可能是您没有平衡的树。那么第一个建议是尝试平衡二叉树，例如红黑树或 AVL 树，或者每个节点有 2 个以上子节点的树，例如 B+ 树。C++ 库提供std::map<>并且std::set<>通常使用平衡树来实现。

但是，避免递归中序遍历的一种简单方法是修改要线程化的树。即用叶子节点的右指针指示下一个节点。这样一棵树的遍历看起来像这样：

n = find_first(n);
while (! is_null(n)) {
    n->print();
    if (n->is_leaf()) n = n->r;
    else n = find_first(n->r);
}
于 2013-07-01T06:15:58.533 回答
0

您可以添加一个静态变量来跟踪调用函数的时间。如果它接近您认为会使系统崩溃的情况，请执行一些例程以通知用户该错误。

于 2013-07-01T04:40:04.553 回答
0

可以通过将另一个 int 变量与递归函数相关联来进行更改的小原型。您可以将变量作为参数传递给函数，默认情况下在根处从零值开始，并在您沿着树向下时递减它。 ..

缺点：此解决方案的代价是为每个节点分配一个 int 变量的开销。

void inorder(node* n,int counter)
{
 if(counter<limit) //limit specified as per system limit
 {
  if(n == null) return;
  inorder(n->l,counter-1);
  n->print();
  inorder(n->r,counter-1);
 }
 else
  n->print();
}

考虑进一步研究：虽然如果只考虑递归，问题可能不在于遍历。并且可以通过更好的树创建和更新来避免。如果尚未考虑，请检查平衡树的概念。

于 2013-07-01T06:54:57.047 回答