在二叉树中插入节点时异常堆栈溢出

Question

CLISP 版本：2.49

叶节点

(value (NIL) (NIL))

非叶节点

(value (value (NIL) (NIL)) (NIL))

代码（"format" 仅用于调试）

; (nil) means NULL
(defun binary-insert (root obj <) 
(if (null (cdr root))
    (progn 
        (format t "In Null [~A] => " root) 
        (setf (car root) obj) 
        (format t "mid [~A] => " root) 
        (setf (cdr root) '((nil) (nil))) 
        (format t "[~A]~%" root))
    (if (funcall < obj (car root))
        (progn 
            (format t "In Left [~A] => " root) 
            (binary-insert (nth 1 root) obj <) 
            (format t "[~A]~%" root)) ; Left
        (progn 
            (format t "In Right [~A] => " root) 
            (binary-insert (nth 2 root) obj <) 
            (format t "[~A]~%" root)) ; Right
        )
    )
)

测试

[1]> (load "binary_tree.lisp")
;; Loading file binary_tree.lisp ...
;; Loaded file binary_tree.lisp
T
[2]> (setf *glb-rt* '(NIL))
(NIL)
[3]> (binary-insert *glb-rt* 10 #'<)
In Null [(NIL)] => mid [(10)] => [(10 (NIL) (NIL))]
NIL
[4]> *glb-rt*
(10 (NIL) (NIL))
[5]> (binary-insert *glb-rt* 5 #'<)
In Left [(10 (NIL) (NIL))] => In Null [(NIL)] => mid [(5)] => [
*** - Lisp stack overflow. RESET

程序好像执行完就死了

(setf (cdr root) '((NIL) (NIL)))

谢谢....

[更新]

在(setf (cdr root) '((NIL) (NIL)))之前，"root"是(5)

另一个测试

[6]> (setf glb-ls '(5))
(5)
[7]> (setf (cdr glb-ls) '((NIL) (NIL)))
((NIL) (NIL))
[8]> glb-ls
(5 (NIL) (NIL))

Answer 1

此问题已在 CLISP FAQ 中得到解答 How do I avoid stack overflow?

在您的情况下，第一个建议有效：在

之后

(setq *print-circle* t)

我们得到

In Left [(10 (NIL) (NIL))] => In Null [(NIL)] => mid [(5)] => [#1=(5 #1#  (NIL))]

也就是说，您错误地创建了一个圆形结构。

PS。你现在欠我 10 zorkmids :-)

在二叉树中插入节点时异常堆栈溢出

Unusual stack overflow when inserting nodes in binary tree

stack-overflow

binary-tree

clisp

common-lisp