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 

Answer 2

有与jkiiski's answer一个问题：它可以在给定的输入，但仅仅是因为每个child都有自己的children。这个答案的变体在样本输入上具有相同的行为，但也适用于其他树。

(defun print-tree (tree) 
    (dolist (child (cdr tree)) 
    (format t "~&~a > ~a" (car tree) (if (consp child) 
             (car child) 
             child))) 
    (dolist (child (cdr tree)) 
    (if (consp child) 
     (print-tree child)))) 


(print-tree '(A (B (C 1 2 3) 4))) 
A > B 
B > C 
B > 4 
C > 1 
C > 2 
C > 3