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 

Answer 2

看來你代表你的列表的方式是不一致的。對於你的例子，我想它應該是：(A ((B (C D)) (E (F))))。這樣，節點一直是葉子或列表，其中汽車是葉子，而cadr是子節點。

由於這個錯誤，我認爲這不是一項功課。這是一個遞歸解決方案。

(defun by-levels (ts) 
    (if (null ts) 
     '() 
     (append 
     (mapcar #'(lambda (x) (if (listp x) (car x) x)) ts) 
     (by-levels (mapcan #'(lambda (x) (if (listp x) (cadr x) '())) ts))))) 

by-levels採用節點列表，並收集了頂級節點的值，並遞歸尋找下一個孩子作爲下一個節點使用。

現在，

(defun leafs-of-tree-by-levels (tree) 
    (by-levels (list tree))) 

(leafs-of-tree-by-levels '(a ((b (c d)) (e (f))))) 
; (A B E C D F) 

我希望是有道理的。

Answer 3

我Lisp是有點生疏，但喬納森建議，廣度優先遍歷樹應該這樣做 - 這是沿着這些線路

編輯我想我之前太快速閱讀問題一點點。你所擁有的基本上是函數應用程序的語法樹，所以這裏是修改後的代碼。我從你的問題的說明認爲，如果C和d是B的孩子，那麼你的意思是寫（B（C）（d））

; q is a queue of function calls to print 
(setq q (list the-original-expression)) 
; for each function call 
(while q 
    ; dequeue the first one 
    (setq a (car q) q (cdr q)) 
    ; print the name of the function 
    (print (car a)) 
    ; append its arguments to the queue to be printed 
    (setq q (append q)(cdr a)) 
) 

這是歷史：

  q: ((A (B (C)(D))(E (F)))) 
print: A 
     q: ((B (C)(D))(E (F))) 
print: B 
     q: ((E (F))(C)(D)) 
print: E 
     q: ((C)(D)(F)) 
print: C 
     q: ((D)(F)) 
print: D 
     q: ((F)) 
print: F 
     q: nil