LISP Displaying binary tree level by level

Question

I have a list that looks like (A (B (C D)) (E (F))) which represents this tree:

      A
    /  \
  B      E
 / \    /
C   D  F

How do I print it as (A B E C D F) ?

This is as far as I managed:

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

But it prints:

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

I'm pretty new to Common LISP so there may be functions that I should've used. If that's the case then enlight me.

Thanks.

Answer 1

Taking your question at face value, you want to print out the nodes in 'breadth-first' order, rather than using one of the standard, depth-first orderings: 'in-order' or 'pre-order' or 'post-order'.

• in-order: C B D A E F
• pre-order: A B C D E F

• post-order: C D B F E A

• requested order: A B E C D F

In your tree structure, each element can be either an atom, or a list with one element, or a list with two elements. The first element of a list is always an atom.

What I think the pseudo-code needs to look like is approximately:

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.

I'm 100% sure that can be cleaned up (that looks like trivial tail recursion, all else apart). However, I think it works.

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

It seems that the way you represent your list is inconsistent. For your example, I imagine it should be: (A ((B (C D)) (E (F)))). This way, a node is consistently either a leaf or a list where the car is the leaf and the cadr is the children nodes.

Because of this mistake, I am assuming this is not a homework. Here is a recursive solution.

(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 takes a list of nodes and collects values of the top-level nodes, and recursively find the next children to use as the next nodes.

Now,

(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)

I hope that makes sense.

Answer 3

My Lisp is a little rusty, but as Jonathan suggested, a breadth-first tree walk should do it - something along these lines

Edit: I guess I read the problem a little too quickly before. What You have is basically a syntax tree of function applications, so here is the revised code. I assume from your description of the problem that if C and D are children of B then you meant to write (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))
  )

This is the history:

         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