insert - 二叉树插入中的堆栈溢出

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;

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

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

Answer 1

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

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

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

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

无论如何，它应该与你的逻辑相同，即遍历树并寻找正确的位置。如果新值小于或大于任何叶子，则将其作为新节点插入，作为父节点的叶子，并在“t”中返回。如果已经存在具有相同值的节点，则返回该节点。

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

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

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;