LISP逐级显示二叉树 | 码农俱乐部 - Golang中国

Go语言中文社区 · · 22 次点击 · · 开始浏览    

我有一个看起来像(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.

我百分之百确定这是可以清除的(这看起来像是微不足道的尾部递归,除此之外)不过,我认为这是可行的。
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

本文来自:Go语言中文社区

感谢作者:Go语言中文社区

查看原文:LISP逐级显示二叉树 | 码农俱乐部 - Golang中国

22 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传