Обход дерева LISP

Question

Я пытаюсь вернуть список узлов дерева (не обязательно двоичного дерева), к которому обращались.

Дерево представляется в виде списка с подсписками, например: (a (b) (c (d) (e))), b - левое поддерево, (c (d) (e)) - правое поддерево, a -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

Бесконечная рекурсия вызвана тем фактом, что число никогда не бывает ложным.
замещать (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)))

Как видите, это одноэлементный список с правильным поддеревом, а не с правильным поддеревом.
(Тестирование каждой функции по отдельности - хорошая идея, особенно если вы уверены, что они верны.)

Корень - это первый элемент списка (car), левое поддерево является вторым (car из cdr - cadr), а правое поддерево - это третий элемент (car из cdr из cdr - 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)