树中序遍历 LISP

Question

我正在尝试返回按顺序访问的树(不一定是二叉树)的节点列表。

树表示为带有子列表的列表，例如:(a (b) (c (d) (e)))，b - 左子树，(c (d) (e)) - 右-子树，一个 -root。 结果应该是: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))
  )
 )
)

Answer 1

无限递归是由于一个数永远不会为 false-y 而造成的。
将 (not (list-length tree)) 替换为 (null tr​​ee)。
(也就是说，递归结构，而不是大小。)

修复此问题后，您将收到类型错误，因为您的基本情况结果为 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)))

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

根是第一个列表项(car)，左子树是第二个(cdr 的car - cadr),右子树为第3个item(cdr的carcdr - caddr)，而不是您所写的从第三项开始的其余列表。
您需要提取子树:

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