我有一个列表,看起来像 (A (B (C D)) (E (F))) 代表这棵树:
A
/ \
B E
/ \ /
C D F
如何将其打印为 (A B E C D F)?
这是我所能做到的:
((lambda(tree) (loop for ele in tree do (print ele))) my-list)
但它打印:
A
(B (C D))
(E (F))
NIL
我是 Common LISP 的新手,所以可能有些函数我应该用过。如果是这样的话,请启发我。
谢谢。
从表面上看你的问题,你想以“广度优先”的顺序打印出节点,而不是使用标准的深度优先顺序之一:“按顺序”或“预顺序”或'后订单'。
- 按顺序:C B D A E F
- 预订:A B C D E F
后序:C D B F E A
请求顺序:A B E C D F
在您的树结构中,每个元素可以是一个原子,或者是一个包含一个元素的列表,或者是一个包含两个元素的列表。列表的第一个元素始终是一个原子。
我认为伪代码需要看起来大概是这样的:
Given a list 'remains-of-tree':
Create empty 'next-level' list
Foreach item in `remains-of-tree`
Print the CAR of `remains-of-tree`
If the CDR of `remains-of-tree` is not empty
CONS the first item onto 'next-level'
If there is a second item, CONS that onto `next-level`
Recurse, passing `next-level` as argument.
我 100% 确定它可以被清理(这看起来像是微不足道的尾递归,除此之外)。但是,我认为它有效。
Start: (A (B (C D)) (E (F)))
Level 1:
Print CAR: A
Add (B (C D)) to next-level: ((B (C D)))
Add (E (F)) to next-level: ((B (C D)) (E (F)))
Pass ((B (C D) (E (F))) to level 2:
Level 2:
Item 1 is (B (C D))
Print CAR: B
Push C to next-level: (C)
Push D to next-level: (C D)
Item 2 is (E (F))
Print CAR: E
Push F to next-level: (C D F)
Pass (C D F) to level 3:
Level 3:
Item 1 is C
Print CAR: C
Item 2 is D
Print CAR: D
Item 3 is F
Print CAR: F
我是一名优秀的程序员,十分优秀!