在lisp中的树遍历

Question

我正试图在lisp中遍历一棵树并打印出所有父子关系.这是我的输入:(5(3(4(1))(g)(9(6)))(n(8(0))(q)(7)(b(f(c(a))) )))我试图让它打印出以下内容:

5>3

5>n

3>4

3>g

3>9

4>1

9>6

n>8

n>q

n>7

n>b

8>0

b>f

f>c

c>a

我目前的代码如下:

(defun par-child-print (l)
    (print l)
    (cond ((not (null (caadr l))) 
    (print "start")
    (print (car l)) 
    (print ">") 
    (print (caadr l)) 
    (print "end")
    (cond ((not (atom (car l))) (when (not (eq (car l) NIL)) (par-child-print (car l)))));

    (when (not (eq (cdr l) NIL)) (par-child-print (cdr l)))

    )
(t 
)));

问题是我的输出有时只打印父级(并且它不会通过整个树).有任何想法吗？

我也有这个通过整个树,但甚至没有试图跟踪父母:

(defun atom-print (l)
(print l)
(cond ((atom l) (print l));
(t 
(when (not (eq (car l) NIL)) (atom-print (car l)))
(when (not (eq (cdr l) NIL)) (atom-print (cdr l)))


)));

Answer 1

树中的每个列表由两部分组成,一个名称和一个子列表.这些都是一样的CAR,并在CDR列表中,但语义的原因,你可以通过定义它们的别名开始:

(defun name (tree) (car tree))
(defun children (tree) (cdr tree))

这些抽象了树如何实现的细节.然后,给定一棵树,你想要做两件事:

1. 使用父项名称和子项名称为每个孩子打印一行.这可以这样做:

   (dolist (child (children tree))
     (format t "~&~a > ~a" (name tree) (name child)))
   

2. 以相同的方式打印每个孩子.这是通过递归调用函数来完成的:

   (dolist (child (children tree))
     (print-tree child))
   

所以整个函数看起来像这样:

(defun print-tree (tree)
  (dolist (child (children tree))
    (format t "~&~a > ~a" (name tree) (name child)))
  (dolist (child (children tree))
    (print-tree child)))

(print-tree '(5 (3 (4 (1)) (g) (9 (6))) (n (8 (0)) (q) (7) (b (f (c (a)))))))
; 5 > 3
; 5 > N
; 3 > 4
; 3 > G
; 3 > 9
; 4 > 1
; 9 > 6
; N > 8
; N > Q
; N > 7
; N > B
; 8 > 0
; B > F
; F > C
; C > A