-1

我试图返回按顺序访问的树（不一定是二叉树）的节点列表。

树表示为带有子列表的列表，例如： (a (b) (c (d) (e))), b - 左子树, (c (d) (e)) - 右子树, a -根。结果应该是：b,a,d,c,e

这是我的代码，但我似乎总是收到“堆栈溢出”错误。有人可以帮帮我吗？

;return left-subtree
(defun left-tree(tree)
  (cond
   ((null tree) NIL)
   ((not (listp tree)) NIL)
   (t (car (cdr tree)))
  )
)

;return right-tree
(defun right-tree(tree)
  (cond
   ((null tree) NIL)
   ((not (listp tree)) NIL)
   (t (cdr (cdr tree)))
  )
)

;perform inorder
(defun inorder(tree)
  (if (not (list-length tree)) 0
  (append
   (inorder (left-tree tree))
   (list (car tree))
   (inorder (right-tree tree))
  )
 )
)
4

1 回答 1

3

无限递归是由一个数字永远不会是假的这一事实引起的。
替换(not (list-length tree))为(null tree)。
（也就是说，在结构上递归，而不是在大小上。）

一旦你解决了这个问题，你会得到一个类型错误，因为你的基本情况导致inorder- 它应该是nil，而不是0.

一旦你解决了这个问题，你会发现另一个问题：

CL-USER> (inorder '(a (b) (c (d) (e))))
(B A (C (D) (E)))

这远非正确。

如果您查看 的结果right-tree，它实际上并不是您声称的结果：

CL-USER> (right-tree '(a (b) (c (d) (e))))
((C (D) (E)))

如您所见，这是一个包含右子树的单元素列表，而不是右子树。
（单独测试每个函数是个好主意，尤其是当您确定它们是正确的时。）

根是第一个列表项（ the car），左子树是第二个（-car的），右子树是第三个项目（-的），而不是从你写的第三项。 您需要提取子树：cdrcadrcarcdrcdrcaddr

(defun right-tree(tree)
  (cond
    ((null tree) NIL)
    ((not (listp tree)) NIL)
    (t (caddr tree))))

CL-USER> (inorder '(a (b) (c (d) (e))))
(B A D C E)
于 2015-12-09T10:16:36.533 回答