Lisp print a tree level by level-CodePudding

I have in LISP a tree represented as list as follows: (A 2 B 0 C 2 D 0 E 0)

That means A have 2 childrens (B and C), B have 0, and so on...

My task is to write each level of the tree.

I know about this post:

CodePudding user response：

One obvious approach is to first decode this flat-but-unweildy representation into a more obvious tree, and then print that tree, which I assume you know how to do. One trick to doing this is to have a function which decodes a node from the representation and returns both the decoded node and the unconsumed tail of the representation. Here is something which does that.

(defun decode-one-child (from)
  (destructuring-bind (head nchilds . children/more) from
    (iterate decode ((c nchilds)
                     (cm children/more)
                     (childs '()))
      (cond
       ((zerop c)
        (values (make-node head (nreverse childs))
                cm))
       ((null cm)
        (error "ran out of children to eat"))
       (t
        (multiple-value-bind (node remaining) (decode-one-child cm)
          (decode (1- c) remaining (cons node childs))))))))

(defun decode-tree (from)
  (multiple-value-bind (decoded tail) (decode-one-child from)
    (unless (null tail)
      (error "ran out of appetite before consuming all children"))
    decoded))

Note that this intentionally is not a complete answer, because I suspect this may well be homework. You will need to write both make-node, and understand what iterate (not part of standard CL) does. For the second, have a look at named let in Scheme, or consider that

(iterate name ((var val) ...)
  ...)

Can be translated as

(labels ((name (var ...)
           ...))
  (name val ...))

CodePudding user response：

Someone, under a different account, fairly recently asked a question about this representation of lists, using the same example. I wrote an answer using TXR Lisp to parse that representation and convert to an ordinary nested list.

When multiple people ask questions about a very specific academic programming problem with identical inputs or other details, that is strong evidence that this is homework.

The parsing code from my original answer:

(defun parse (syntax)
  (labels ((rec (parsym n)
             (cons parsym
                   (collect-each ((i 0..n))
                     (match-case syntax
                       ((@sym 0 . @rest)
                        (set syntax rest)
                        (list sym))
                       ((@sym @(integerp @m) . @rest)
                        (set syntax rest)
                        (rec sym m))
                       (() (error "abrupt end in syntax"))
                       (@else (error "unhandled syntax: ~s" syntax)))))))
    (cadr (rec :root 1))))

Calculates like this:

1> (parse '(A 2 B 0 C 2 D 0 E 0))
(A (B) (C (D) (E)))

To print each level of the resulting, like, say:

A
B C
D E

and in various other ways, we need a breadth-first search. The easy depth-first search traversal won't do; that's what the ordinary printed representation is already doing.

The TXR Lisp manual, under the documentation of the build macro, gives an example breadth-first-search traversal in a few lines of code:

(defun bf-map (tree visit-fn)
  (buildn
    (add tree)
    (whilet ((item (del)))
      (if (atom item)
        [visit-fn item]
        (each ((el item))
          (add el))))))

That doesn't quite do what we want: it visits the atoms:

7> [bf-map (parse '(A 2 B 0 C 2 D 0 E 0)) prinl]
A
B
C
D
E

so we are certainly getting the names in level order, but we don't see the divisions between the levels.

We need to modify this function to recognize the special syntax of the tree which is (<name> [<tree>*]) and for each level, print just the name(s) on that level.

Maybe like this:

(defun bf-map (tree visit-fn)
  (buildn
    (add (cons 0 tree))
    (whilet ((item (del)))
      (tree-bind (level name . children) item
        [visit-fn level name]
        (each ((ch children))
          (add (cons (succ level) ch)))))))

The items in the BFS queue are now agumented (level . tree) cons pairs, and since a tree is (name . children), the queue items are therefore (level name . children). We prime the queue by pushing such (level . tree) item into it, calculating that item as (cons 0 tree).

We also modify the protocol so that the callback function is invoked with two arguments: the level number, and the node name.

We might this function like so to print something directly:

11> (let ((oldlevel nil))
      [bf-map (parse '(A 2 B 0 C 2 D 0 E 0))
              (lambda (level name)
                (when (neql oldlevel level)
                  (put-line `\nlevel@level:`))
                (print name)
                (put-string " ")
                (set oldlevel level))]
      (put-line))

level0:
A 
level1:
B C 
level2:
D E

Or get the levels as a vector indexed on zero-based level:

13> (let ((level-vector (vec))
          (nlevels 0))
      [bf-map (parse '(A 2 B 0 C 2 D 0 E 0))
              (lambda (level name)
                (when (>= level nlevels)
                  (vec-push level-vector nil)
                  (upd [level-vector (pinc nlevels)] nreverse))
                (push name [level-vector level]))]
      level-vector)
#((A) (C B) (E D))