二叉树插入中的堆栈溢出

Question

PROCEDURE CreateNode (info: CHAR): BST;
VAR   
    bst : BST;
BEGIN
    NEW(bst);
    bst^.elem := info;
    bst^.left := NIL;
    bst^.right := NIL;
    RETURN bst;  
END CreateNode;



PROCEDURE Insert (info: CHAR; VAR t: BST);
BEGIN
    IF t = NIL THEN  
         t := CreateNode(info);  
    ELSIF Compare(info, t^.elem) = greater THEN  
         Insert(info, t^.right);  
    ELSIF Compare(info, t^.elem) = less THEN  
         Insert(info, t^.left);  
END;
END Insert;

当使用从 1 到非常高的值 (20k) 的 FOR 时，这会导致堆栈溢出。

在溢出之前它只达到了一个相对较低的数字 (~900)。

Answer 1

看到这似乎是 Pascal，问题的原因很可能是递归本身。您正在使用的 Pascal 版本很可能无法（或不会）针对尾递归优化此函数。

Answer 2

你在 Stack Overflow 上搜索过吗？ :p 开玩笑。

问题可能是递归调用。函数调用使用堆栈来存储寄存器值，只有在被调用函数结束并且控制权 returned 到调用函数时才会从那里删除这些值。对于递归调用，所有这些嵌套调用都保留在堆栈中，直到递归被破坏。最终堆栈不够大，你会得到这个错误。

您应该可以通过使用循环消除递归来解决此问题。这样，您就可以进行跳转到下一个节点的迭代，而无需函数调用的所有开销。

要做到这一点可能很难。有时递归似乎是显而易见的方法，您必须做一些工作才能在循环中修复它。

反正和你的逻辑应该是一样的，就是遍历树，找对的地方。如果新值小于或大于任何叶子，则将其作为新节点插入，作为父节点的叶子，并 returned in 't'。如果已经有一个具有相同值的节点，则该节点是 returned.

为了消除过多的代码重复，下面的代码片段引入了一个新函数 TryCreateNode。它测试 p（父节点的左叶或右叶）是否为 nil，如果是，则为其分配一个新节点。它 returns p（现有叶子）或新节点作为输出参数，returns true 如果创建了新节点。 return 值在主函数中用于中断循环。

我不确定您使用的是哪种 Pascal 方言，所以我只是猜测了一下。也许您需要将其视为伪代码并首先修复语法。 ;)

FUNCTION TryCreateNode(Info: CHAR; VAR p: BST; VAR t: BST): Boolean;
BEGIN
  TryCreateNode := False;
  IF p = nil THEN 
  BEGIN
    p := CreateNode(info);
    TryCreateNode := True;
  END;
  t := p;
END;

PROCEDURE Insert (info: CHAR; VAR t: BST);
BEGIN
  WHILE t <> nil DO
  BEGIN
    IF Compare(info, t^.elem) = greater THEN
      IF TryCreateNode(info, t^.right, t) THEN
        BREAK;
    IF Compare(info, t^.elem) = less THEN
      IF TryCreateNode(info, t^.left, t) THEN
        BREAK;
  END;

END Insert;

二叉树插入中的堆栈溢出

Stack Overflow in binary tree insertion

stack-overflow

insert

binary-search-tree