在二叉树中插入节点时异常堆栈溢出 [英] Unusual stack overflow when inserting nodes in binary tree

问题描述

CLISP版本:2.49

CLISP Version: 2.49

叶节点

(value (NIL) (NIL))

非叶​​子节点

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

代码(格式"仅用于调试)

Code ("format" for debug only)

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

似乎程序在执行后就死了

It seems the program died after executing

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

谢谢....

[更新]

在(setf(cdr根目录)'(((NIL)(NIL))))之前，根目录"为(5)

Before (setf (cdr root) '((NIL) (NIL))), the "root" is (5)

另一项测试

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

推荐答案

此问题已在CLISP常见问题解答如何避免堆栈溢出?

This question has been answered in the CLISP FAQ How do I avoid stack overflow?

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

In your case the very first suggestion works: after

(setq *print-circle* t)

我们得到

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

即，您错误地创建了圆形结构.

i.e., you are mistakenly creating a circular structure.

PS.您现在欠我 10 zorkmids :-)

PS. You now owe me 10 zorkmids :-)

这篇关于在二叉树中插入节点时异常堆栈溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！