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