Re: All paths through a tree

Blaine wrote:
Given a tree like:

(77 (237 (228 (234 (231 266) 266)) (234 (231 266) 266)))

I would like to list all the paths from the source node to the terminal
nodes:

((77 237 228 234 231 266)
(77 237 228 234 266)
(77 237 234 231 266)
(77 237 234 266))

What do you mean by terminal nodes and paths? There is more than one
way in which structures of conses and atoms represent trees; it depends
on your convention. You don't suppose that this is important? Staring
into my crystal ball, I see that according to your definition,
something of the form

(X Y Z ...)

is a node labelled by X which is an atom. Y and Z are its children, and
they are nodes. A node can also be an atom, in which case it's a
terminal.

Thus in your above list, there are indeed four terminal nodes.

A path is simply a list of the names of the non-terminal nodes and the
terminal atom.

I've been struggling with this for a few days now, and I just can't get
it to work.

Hee hee. Here you go:

(defun paths (list)
(let (path-list)
(labels ((traverse (list stack)
(destructuring-bind (label &rest children) list
(push label stack)
(dolist (child children)
(cond
((atom child)
(push child stack)
(push (reverse stack) path-list)
(pop stack))
(t
(traverse child stack)))))))
(traverse list nil)
(nreverse path-list))))

Test case:

(paths '(77 (237 (228 (234 (231 266) 266)) (234 (231 266) 266))))

->

((77 237 228 234 231 266) (77 237 228 234 266) (77 237 234 231 266)
(77 237 234 266))

Do your own homework next time.

.

Relevant Pages

  • Re: All Controls On Form Without Using Recursion
    ... then remove them one at a time and push all it's child ... controls onto the stack. ... I would assume that complete means also the parent controls. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Questions on ATTACHXs ETXR exit routine
    ... From that I it appears that the IRB is sharing the stack ... the system requires the ETXR to restore the regs. ... I'm using the ETXR for cleanup and to inform the originating task ... that a child has terminated. ...
    (bit.listserv.ibm-main)
  • Re: A filter driver with bus enumeration capabilities: aka serenum.
    ... Since your filter is not the power policy owner for the stack, it cannot ensure that when the child is powered up that the parent stack is also powered up....BUT...for serial that does not really matter b/c once you send the create to the serial stack from the child stack, serial will stay powered on until it has been closed. ... mark yourself as a filter, ...
    (microsoft.public.development.device.drivers)
  • Re: Questions on ATTACHXs ETXR exit routine
    ... From that I it appears that the IRB is sharing the stack ... the system requires the ETXR to restore the regs. ... I'm using the ETXR for cleanup and to inform the originating task ... :>that a child has terminated. ...
    (bit.listserv.ibm-main)
  • Re: 2.6.12-rc3 OOPS in vanilla source (once more)
    ... > - Do we need to adjust that initial ... esp0 indicates the start of the stack and ... what will be copied onto the stack so it makes even more sense to make ... problem as the traced child is scheduled away before the parent ...
    (Linux-Kernel)