LISP Отображение уровня двоичного дерева по уровню

Question

У меня есть список, который выглядит как (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, поэтому могут быть функции, которые мне следовало бы использовать. Если это так, то просвети меня.

Спасибо.

Answer 1

Принимая ваш вопрос по номиналу, вы хотите распечатать узлы в порядке «по ширине», а не использовать один из стандартных порядков по глубине: «по порядку» или «предзаказ» или 'пост-заказ'.

• по порядку: 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

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

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

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