lisp中的树遍历

tree traversal in lisp

我试图在 lisp 中遍历一棵树并打印出所有 parent-child 关系。 这是我的输入: (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 
)));

问题是我的输出有时只打印 parent(而且它没有遍历整个树)。有什么想法吗?

我也有这个可以通过整棵树,但甚至没有尝试跟踪 parents:

(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)))


)));

树中的每个列表由两部分组成,一个名字和一个children的列表。它们与列表的 CARCDR 相同,但出于语义原因,您可以从为它们定义别名开始:

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

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

  1. 用 parents 的名字和 child 的名字在每个 child 上打印一行。可以这样做:

    (dolist (child (children tree))
      (format t "~&~a > ~a" (name tree) (name child)))
    
  2. 以同样的方式打印每个 child。这是通过对它们递归调用函数来完成的:

    (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

有一个问题:它适用于给定的输入,但这只是因为每个 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