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的列表。它们与列表的 CAR
和 CDR
相同,但出于语义原因,您可以从为它们定义别名开始:
(defun name (tree) (car tree))
(defun children (tree) (cdr tree))
这些抽象了如何实现树的细节。然后,给定一棵树,你想做两件事:
用 parents 的名字和 child 的名字在每个 child 上打印一行。可以这样做:
(dolist (child (children tree))
(format t "~&~a > ~a" (name tree) (name child)))
以同样的方式打印每个 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
我试图在 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的列表。它们与列表的 CAR
和 CDR
相同,但出于语义原因,您可以从为它们定义别名开始:
(defun name (tree) (car tree))
(defun children (tree) (cdr tree))
这些抽象了如何实现树的细节。然后,给定一棵树,你想做两件事:
用 parents 的名字和 child 的名字在每个 child 上打印一行。可以这样做:
(dolist (child (children tree)) (format t "~&~a > ~a" (name tree) (name child)))
以同样的方式打印每个 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