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

Мой Лисп немного ржавый, но, как предложил Джонатан, широта-первых дерево прогулка должна сделать это - что-то вдоль этих линий

Edit: Я предполагаю, что я читал эту проблему немного слишком быстро, прежде чем ,У вас есть в основном синтаксическое дерево функциональных приложений, поэтому здесь приведен переработанный код. Я предполагаю, что из вашего описания проблемы, если С и 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