tree traversal inorder LISP

Question

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

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

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