LISP逐级显示二叉树

Question

我有一个看起来像(A(B(CD))(E(F)))的列表代表这个树:

      A
    /  \
  B      E
 / \    /
C   D  F

如何将其打印为(ABECDF)？

这是我管理的:

((lambda(tree) (loop for ele in tree do (print ele))) my-list)

但它打印:

A
(B (C D))
(E (F))
NIL

我对Common LISP很新,所以可能会有我应该使用的功能.如果是这样的话,那就让我开心吧.

谢谢.

Answer 1

以面值来表达您的问题,您希望以"广度优先"顺序打印出节点,而不是使用标准的深度优先排序之一:"按顺序"或"预订"或"后"订购'.

• 有序:CBDAEF
• 预订:ABCDEF

• 下订单:CDBFEA

• 要求订单:ABECDF

在树结构中,每个元素可以是原子,也可以是包含一个元素的列表,也可以是包含两个元素的列表.列表的第一个元素始终是原子.

我认为伪代码看起来像是近似的:

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