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))
I've been struggling with this for a few days now, and I just can't get
it to work. Does anyone have any ideas? Anywhere to look for code for
manipulating trees?
Thanks,
Blaine
Blaine wrote:
> Given a tree like:
>
> (77 (237 (228 (234 (231 266) 266)) (234 (231 266) 266)))
>
Can you explain what makes this a tree? (as opposed to a list of lists)
What is the single data structure that makes it a tree?( what is a node)
Is a node of the tree a tree itself?
Define these terms and you can design traversal algorithm.
> 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))
>
> I've been struggling with this for a few days now, and I just can't get
> it to work. Does anyone have any ideas? Anywhere to look for code for
> manipulating trees?
>
> Thanks,
> Blaine
>
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.
"Blaine" <···············@gmail.com> writes:
> Given a tree like:
>
> (77 (237 (228 (234 (231 266) 266)) (234 (231 266) 266)))
First, you should abstract a little.
(77 (237 (228 (234 (231 266) 266)) (234 (231 266) 266))) is not a
univoque tree representation. For example, here are only three
different trees that this s-expression might possibly represent.
(defstruct (tree-methods)
empty-p leaf-p label children
make-empty make-leaf make-tree)
(defparameter *labelless-binary-tree*
(make-tree-methods
:empty-p (function null)
:leaf-p (function atom)
:label (lambda (node) (if (atom node) (values node t) (values '|| nil)))
:children (lambda (node) (list (car node) (cdr node)))
:make-empty (constantly nil)
:make-leaf (function identity)
:make-tree (lambda (label children)
(if (!= 2 (length children))
(error "This is a binary tree, each non-leaf node ~
must have two children")
(cons (first children) (second children)))))
"An interpretation of S-expressions as binary trees of CONS pairs.
The non leaf nodes have no label, only two children, CAR and CDR.
Leaf nodes can be any atom. NIL is the empty tree.")
(defparameter *leaf-labelled-nary-tree*
(make-tree-methods
:empty-p (function null)
:leaf-p (function atom)
:label (lambda (node) (if (atom node) (values node t) (values '|| nil)))
:children (lambda (node) (if (atom node) '() node))
:make-empty (constantly nil)
:make-leaf (function identity)
:make-tree (lambda (label children) children))
"An interpretation of S-expressions as n-ary trees.
Non leaf nodes have no label.
They are represented the list of their children.
Leaf nodes can be any atom. NIL is the empty tree.")
(defparameter *labelled-nary-tree*
(make-tree-methods
:empty-p (function null)
:leaf-p (function atom)
:label (lambda (node) (if (atom node) (values node t) (values (car node) t)))
:children (lambda (node) (if (atom node) '() (cdr node)))
:make-empty (constantly nil)
:make-leaf (function identity)
:make-tree (function cons))
"An interpretation of S-expressions as n-ary trees.
Non leaf nodes are represented as a list containing the label in the first
position, and the children of the nodes in the rest.
Leaf nodes can be any atom. NIL is the empty tree.")
;; Of course, you can find a lot of ther interpretations of
;; S-expressions as tree.
;; (You can represent trees with S-expressions in a lot of different ways).
(defparameter *default-tree-interpretation* *labelled-nary-tree*)
(defmacro define-tree-function (name arguments)
`(defun ,name ,arguments
(funcall (,(intern (format nil "TREE-METHODS-~A"
(if (string= "TREE-" name :end2 5)
(subseq (string name) 5)
name)))
*default-tree-interpretation*) ,@arguments)))
(define-tree-function tree-empty-p (node))
(define-tree-function tree-leaf-p (node))
(define-tree-function tree-label (node))
(define-tree-function tree-children (node))
(define-tree-function tree-make-empty ())
(define-tree-function tree-make-leaf (label))
(define-tree-function tree-make-tree (label children))
(DEFUN TREE->TLEE (TREE)
"
TREE: Some kind of data representing some kind of tree. It is interpreted
by the functions in the *DEFAULT-TREE-INTERPRETATION* structure.
RETURN: A s-expression representing a tree according to *LABELLED-NARY-TREE*.
"
(COND
((tree-empty-p TREE)
(funcall (tree-methods-make-empty *labelled-nary-tree*)))
((tree-leaf-p TREE)
(funcall (tree-methods-make-leaf *labelled-nary-tree*) (tree-label tree)))
(t
(funcall (tree-methods-make-tree *labelled-nary-tree*)
(tree-label tree)
(mapcar (lambda (child) (tree->tlee child))
(tree-children tree))))))
(let ((data '(77 (237 (228 (234 (231 266) 266)) (234 (231 266) 266)))))
(map nil
(lambda (*DEFAULT-TREE-INTERPRETATION*)
(format t "~&;;~%")
(with-input-from-string
(in (COM.INFORMATIMAGO.COMMON-LISP.TREE-TO-ASCII:TREE-TO-ASCII
(tree->tlee data)
:format-fun (lambda (label) (format nil "~A" label))))
(loop :for line = (read-line in nil nil)
:while line :do (format t "~&;; ~A~%" line)))
(format t "~&;;~%"))
(list *labelless-binary-tree*
*leaf-labelled-nary-tree*
*labelled-nary-tree*))
(values))
;;
;; +--77
;; |
;; | +--237
;; | |
;; | | +--228
;; | | |
;; | | | +--234
;; | | | |
;; | | | | +--231
;; | | | | |
;; | | | | +----+ +--266
;; | | +----+ +----+ | +----+
;; | | | +----+ +----+ +--NIL
;; | | | | |
;; | | | | | +--266
;; | | | | +----+
;; | | | | +--NIL
;; --+ +----+ | |
;; +----+ +----+ +--NIL
;; | |
;; | | +--234
;; | | |
;; | | | +--231
;; | | | |
;; | | | +----+ +--266
;; | | +----+ | +----+
;; | +----+ +----+ +--NIL
;; | | |
;; | | | +--266
;; | | +----+
;; | | +--NIL
;; | |
;; | +--NIL
;; |
;; +--NIL
;;
;;
;; +--77
;; |
;; | +--237
;; | |
;; | | +--228
;; | | |
;; | | | +--234
;; | | | |
;; | +----+ | +--231
;; | | +----+----+
;; --+ | | +--266
;; +----+ |
;; | +--266
;; |
;; | +--234
;; | |
;; | | +--231
;; +----+----+
;; | +--266
;; |
;; +--266
;;
;;
;; +--231--266
;; +--228--234--+
;; | +--266
;; 77--237--+
;; | +--231--266
;; +--234--+
;; +--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))
>
> I've been struggling with this for a few days now, and I just can't get
> it to work. Does anyone have any ideas?
We only need to walk the tree, keeping the parent nodes in a stack.
When we reach a leaf, copy the stack to a resulting list.
> Anywhere to look for code for
> manipulating trees?
Instead of looking for code to manipulate trees, you should be looking
for a programming tutorial and a recursive programming tutorial.
Start by implementing REVERSE. Try to do it in at least three different ways.
Then write a prefix tree walker, an infix tree walker, a suffix tree walker.
Then you can write a tree walker that works for all three
cases, for example like:
(defun walk-tree (tree prefix infix suffix leaf)
"
TREE: Some kind of data representing some kind of tree. It is interpreted
by the functions in the *DEFAULT-TREE-INTERPRETATION* structure.
NOTE: The function PREFIX, INFIX and SUFFIX are only called when
the current tree is not a leaf.
PREFIX: A function of tree, called before walking the tree.
INFIX: A function of tree, called between walking each of the children.
(not called if less than two children are present).
SUFFIX: A function of tree, called after walking the tree.
LEAF: A function of tree, called when the tree is a leaf.
"
...)
(defparameter *my-tree*
(tree-make-tree
77
(list (tree-make-tree
237
(list (tree-make-tree
228
(list (tree-make-tree
234
(list (tree-make-tree
231
(list (tree-make-leaf 266)))
(tree-make-leaf 266)))))
(tree-make-tree
234
(list (tree-make-tree
231
(list (tree-make-leaf 266)))
(tree-make-leaf 266))))))))
*my-tree*
--> (77 (237 (228 (234 (231 266) 266)) (234 (231 266) 266)))
;; (assuming the *labelled-nary-tree* representation)
;; Prefix:
(walk-tree *my-tree*
(lambda (node) (princ " [") (princ (tree-label node)) (princ " "))
(lambda (node) (princ " "))
(lambda (node) (princ "]"))
(lambda (node) (princ (tree-label node))))
prints: [77 [237 [228 [234 [231 266] 266]] [234 [231 266] 266]]]
;; Suffix:
(walk-tree *my-tree*
(function identity)
(function identity)
(lambda (node) (princ " ") (princ (tree-label node)))
(lambda (node) (princ " ") (princ (tree-label node))))
prints: 266 231 266 234 228 266 231 266 234 237 77
;; Infix:
(walk-tree (tree-make-tree
'+
(list (tree-make-tree '*
(list (tree-make-leaf 3)
(tree-make-leaf 4)
(tree-make-leaf 5)))
(tree-make-tree '/
(list (tree-make-leaf 6)
(tree-make-leaf 7)))
(tree-make-leaf 8)))
(lambda (node) (princ "(")) ; prefix
(lambda (node) (princ (tree-label node))) ; infix
(lambda (node) (princ ")")) ; suffix
(lambda (node) (princ (tree-label node)))) ; leaf
prints: ((3*4*5)+(6/7)+8)
Then you can implement your function trivially:
(let ((result '())
(current-path '()))
(walk-tree *my-tree*
(lambda (node) (push (tree-label node) current-path))
(function identity)
(lambda (node) (pop current-path))
(lambda (node) (push (reverse current-path) result)))
result)
--> ((77 237 234) (77 237 234 231) (77 237 228 234) (77 237 228 234 231))
--
__Pascal Bourguignon__ http://www.informatimago.com/
ATTENTION: Despite any other listing of product contents found
herein, the consumer is advised that, in actuality, this product
consists of 99.9999999999% empty space.
Thanks, fellas.
Believe it or not, it's not homework. It's actual work work. I'm
trying to help a government organization that provides satellite
weather data design a ground system for processing the data. They make
300 or so data products. Many of the products take as inputs other
products. The numbers in the list are product ids so product 77, for
instance, depends on product 237. The issue is how best to schedule
the production of the products so as to meet data refresh and latency
requirements.
Since I'm not a programmer (perhaps too dumb) - just an analyst, I get
to use whatever language I want. I can't seem to code in any other
language....
Anyhow, it looks like I have homework now - that is, from Pascal (I
haven't forgotten the last one you assigned me). This one looks like
fun...
Thanks again,
Blaine
Pascal Bourguignon wrote:
> "Blaine" <···············@gmail.com> writes:
>
> > Given a tree like:
> >
> > (77 (237 (228 (234 (231 266) 266)) (234 (231 266) 266)))
>
> First, you should abstract a little.
>
> (77 (237 (228 (234 (231 266) 266)) (234 (231 266) 266))) is not a
> univoque tree representation. For example, here are only three
> different trees that this s-expression might possibly represent.
>
> (defstruct (tree-methods)
> empty-p leaf-p label children
> make-empty make-leaf make-tree)
>
> (defparameter *labelless-binary-tree*
> (make-tree-methods
> :empty-p (function null)
> :leaf-p (function atom)
> :label (lambda (node) (if (atom node) (values node t) (values '|| nil)))
> :children (lambda (node) (list (car node) (cdr node)))
> :make-empty (constantly nil)
> :make-leaf (function identity)
> :make-tree (lambda (label children)
> (if (!= 2 (length children))
> (error "This is a binary tree, each non-leaf node ~
> must have two children")
> (cons (first children) (second children)))))
> "An interpretation of S-expressions as binary trees of CONS pairs.
> The non leaf nodes have no label, only two children, CAR and CDR.
> Leaf nodes can be any atom. NIL is the empty tree.")
>
> (defparameter *leaf-labelled-nary-tree*
> (make-tree-methods
> :empty-p (function null)
> :leaf-p (function atom)
> :label (lambda (node) (if (atom node) (values node t) (values '|| nil)))
> :children (lambda (node) (if (atom node) '() node))
> :make-empty (constantly nil)
> :make-leaf (function identity)
> :make-tree (lambda (label children) children))
> "An interpretation of S-expressions as n-ary trees.
> Non leaf nodes have no label.
> They are represented the list of their children.
> Leaf nodes can be any atom. NIL is the empty tree.")
>
> (defparameter *labelled-nary-tree*
> (make-tree-methods
> :empty-p (function null)
> :leaf-p (function atom)
> :label (lambda (node) (if (atom node) (values node t) (values (car node) t)))
> :children (lambda (node) (if (atom node) '() (cdr node)))
> :make-empty (constantly nil)
> :make-leaf (function identity)
> :make-tree (function cons))
> "An interpretation of S-expressions as n-ary trees.
> Non leaf nodes are represented as a list containing the label in the first
> position, and the children of the nodes in the rest.
> Leaf nodes can be any atom. NIL is the empty tree.")
>
>
> ;; Of course, you can find a lot of ther interpretations of
> ;; S-expressions as tree.
> ;; (You can represent trees with S-expressions in a lot of different ways).
>
>
> (defparameter *default-tree-interpretation* *labelled-nary-tree*)
>
> (defmacro define-tree-function (name arguments)
> `(defun ,name ,arguments
> (funcall (,(intern (format nil "TREE-METHODS-~A"
> (if (string= "TREE-" name :end2 5)
> (subseq (string name) 5)
> name)))
> *default-tree-interpretation*) ,@arguments)))
>
> (define-tree-function tree-empty-p (node))
> (define-tree-function tree-leaf-p (node))
> (define-tree-function tree-label (node))
> (define-tree-function tree-children (node))
> (define-tree-function tree-make-empty ())
> (define-tree-function tree-make-leaf (label))
> (define-tree-function tree-make-tree (label children))
>
>
> (DEFUN TREE->TLEE (TREE)
> "
> TREE: Some kind of data representing some kind of tree. It is interpreted
> by the functions in the *DEFAULT-TREE-INTERPRETATION* structure.
> RETURN: A s-expression representing a tree according to *LABELLED-NARY-TREE*.
> "
> (COND
> ((tree-empty-p TREE)
> (funcall (tree-methods-make-empty *labelled-nary-tree*)))
> ((tree-leaf-p TREE)
> (funcall (tree-methods-make-leaf *labelled-nary-tree*) (tree-label tree)))
> (t
> (funcall (tree-methods-make-tree *labelled-nary-tree*)
> (tree-label tree)
> (mapcar (lambda (child) (tree->tlee child))
> (tree-children tree))))))
>
>
> (let ((data '(77 (237 (228 (234 (231 266) 266)) (234 (231 266) 266)))))
> (map nil
> (lambda (*DEFAULT-TREE-INTERPRETATION*)
> (format t "~&;;~%")
> (with-input-from-string
> (in (COM.INFORMATIMAGO.COMMON-LISP.TREE-TO-ASCII:TREE-TO-ASCII
> (tree->tlee data)
> :format-fun (lambda (label) (format nil "~A" label))))
> (loop :for line = (read-line in nil nil)
> :while line :do (format t "~&;; ~A~%" line)))
> (format t "~&;;~%"))
> (list *labelless-binary-tree*
> *leaf-labelled-nary-tree*
> *labelled-nary-tree*))
> (values))
>
> ;;
> ;; +--77
> ;; |
> ;; | +--237
> ;; | |
> ;; | | +--228
> ;; | | |
> ;; | | | +--234
> ;; | | | |
> ;; | | | | +--231
> ;; | | | | |
> ;; | | | | +----+ +--266
> ;; | | +----+ +----+ | +----+
> ;; | | | +----+ +----+ +--NIL
> ;; | | | | |
> ;; | | | | | +--266
> ;; | | | | +----+
> ;; | | | | +--NIL
> ;; --+ +----+ | |
> ;; +----+ +----+ +--NIL
> ;; | |
> ;; | | +--234
> ;; | | |
> ;; | | | +--231
> ;; | | | |
> ;; | | | +----+ +--266
> ;; | | +----+ | +----+
> ;; | +----+ +----+ +--NIL
> ;; | | |
> ;; | | | +--266
> ;; | | +----+
> ;; | | +--NIL
> ;; | |
> ;; | +--NIL
> ;; |
> ;; +--NIL
> ;;
> ;;
> ;; +--77
> ;; |
> ;; | +--237
> ;; | |
> ;; | | +--228
> ;; | | |
> ;; | | | +--234
> ;; | | | |
> ;; | +----+ | +--231
> ;; | | +----+----+
> ;; --+ | | +--266
> ;; +----+ |
> ;; | +--266
> ;; |
> ;; | +--234
> ;; | |
> ;; | | +--231
> ;; +----+----+
> ;; | +--266
> ;; |
> ;; +--266
> ;;
> ;;
> ;; +--231--266
> ;; +--228--234--+
> ;; | +--266
> ;; 77--237--+
> ;; | +--231--266
> ;; +--234--+
> ;; +--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))
> >
> > I've been struggling with this for a few days now, and I just can't get
> > it to work. Does anyone have any ideas?
>
> We only need to walk the tree, keeping the parent nodes in a stack.
> When we reach a leaf, copy the stack to a resulting list.
>
>
> > Anywhere to look for code for
> > manipulating trees?
>
> Instead of looking for code to manipulate trees, you should be looking
> for a programming tutorial and a recursive programming tutorial.
>
>
>
> Start by implementing REVERSE. Try to do it in at least three different ways.
>
> Then write a prefix tree walker, an infix tree walker, a suffix tree walker.
>
> Then you can write a tree walker that works for all three
> cases, for example like:
>
>
> (defun walk-tree (tree prefix infix suffix leaf)
> "
> TREE: Some kind of data representing some kind of tree. It is interpreted
> by the functions in the *DEFAULT-TREE-INTERPRETATION* structure.
> NOTE: The function PREFIX, INFIX and SUFFIX are only called when
> the current tree is not a leaf.
> PREFIX: A function of tree, called before walking the tree.
> INFIX: A function of tree, called between walking each of the children.
> (not called if less than two children are present).
> SUFFIX: A function of tree, called after walking the tree.
> LEAF: A function of tree, called when the tree is a leaf.
> "
> ...)
>
>
> (defparameter *my-tree*
> (tree-make-tree
> 77
> (list (tree-make-tree
> 237
> (list (tree-make-tree
> 228
> (list (tree-make-tree
> 234
> (list (tree-make-tree
> 231
> (list (tree-make-leaf 266)))
> (tree-make-leaf 266)))))
> (tree-make-tree
> 234
> (list (tree-make-tree
> 231
> (list (tree-make-leaf 266)))
> (tree-make-leaf 266))))))))
>
> *my-tree*
> --> (77 (237 (228 (234 (231 266) 266)) (234 (231 266) 266)))
> ;; (assuming the *labelled-nary-tree* representation)
>
>
>
> ;; Prefix:
> (walk-tree *my-tree*
> (lambda (node) (princ " [") (princ (tree-label node)) (princ " "))
> (lambda (node) (princ " "))
> (lambda (node) (princ "]"))
> (lambda (node) (princ (tree-label node))))
>
> prints: [77 [237 [228 [234 [231 266] 266]] [234 [231 266] 266]]]
>
>
> ;; Suffix:
> (walk-tree *my-tree*
> (function identity)
> (function identity)
> (lambda (node) (princ " ") (princ (tree-label node)))
> (lambda (node) (princ " ") (princ (tree-label node))))
>
> prints: 266 231 266 234 228 266 231 266 234 237 77
>
> ;; Infix:
> (walk-tree (tree-make-tree
> '+
> (list (tree-make-tree '*
> (list (tree-make-leaf 3)
> (tree-make-leaf 4)
> (tree-make-leaf 5)))
> (tree-make-tree '/
> (list (tree-make-leaf 6)
> (tree-make-leaf 7)))
> (tree-make-leaf 8)))
> (lambda (node) (princ "(")) ; prefix
> (lambda (node) (princ (tree-label node))) ; infix
> (lambda (node) (princ ")")) ; suffix
> (lambda (node) (princ (tree-label node)))) ; leaf
>
> prints: ((3*4*5)+(6/7)+8)
>
>
>
> Then you can implement your function trivially:
>
> (let ((result '())
> (current-path '()))
> (walk-tree *my-tree*
> (lambda (node) (push (tree-label node) current-path))
> (function identity)
> (lambda (node) (pop current-path))
> (lambda (node) (push (reverse current-path) result)))
> result)
> --> ((77 237 234) (77 237 234 231) (77 237 228 234) (77 237 228 234 231))
>
>
> --
> __Pascal Bourguignon__ http://www.informatimago.com/
>
> ATTENTION: Despite any other listing of product contents found
> herein, the consumer is advised that, in actuality, this product
> consists of 99.9999999999% empty space.
"Blaine" <···············@gmail.com> writes:
> Believe it or not, it's not homework. It's actual work work. I'm
> trying to help a government organization that provides satellite
> weather data design a ground system for processing the data. They make
> 300 or so data products. Many of the products take as inputs other
> products. The numbers in the list are product ids so product 77, for
> instance, depends on product 237. The issue is how best to schedule
> the production of the products so as to meet data refresh and latency
> requirements.
>
> Since I'm not a programmer (perhaps too dumb) - just an analyst, I get
> to use whatever language I want. I can't seem to code in any other
> language....
>
> Anyhow, it looks like I have homework now - that is, from Pascal (I
> haven't forgotten the last one you assigned me). This one looks like
> fun...
Ok, since it's not homework, one more hint.
When you must process a recusive data structure, or any kind of data
structure as it's often the case, the procedure has the same
'structure' as the data.
When you have a record, (a C struct, a lisp structure or object), the
procedure processing it will be the sequential processing of each
field:
(defstruct person name age sex)
(defun process-person (p)
(process-name (person-name p))
(process-age (person-age p))
(process-sex (person-sex p)))
When you have a vector, that is a repeatition of items of some kind,
the procedure processing it will be a repeating loop:
(defun process-vector (v)
(loop :for i :from 0 :below (length v)
:do (process-item (aref v i))))
And the same when you have a recursive structure:
;; list := nil | (cons first rest-list)
(defun process-list (list)
(if (null list)
(process-null)
(progn (process-first (first list))
(process-list (rest list)))))
;; bintree := nil | (make-tree label left-bintree right-bintree)
(defun process-bintree (bt)
(if (null bt)
(process-null)
(progn ;; Note here that a tree is firstly a structure
;; then we have sequence processing each field in turn.
;; Since some fields are recursive structures,
;; some of the processing will be recusive calls.
(process-label (tree-label bt))
(process-bintree (tree-left bt))
(process-bintree (tree-right bt)))))
Of course, the order in which you process the fields might be prefix
order, suffix order, infix order or some other random order ;-)
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Indentation! -- I will show you how to indent when I indent your skull!"
"Blaine" <···············@gmail.com> writes:
> Since I'm not a programmer (perhaps too dumb) - just an analyst, I get
> to use whatever language I want. I can't seem to code in any other
> language....
So people who aren't programmers are trusted to make technical decisions
about programming more than people who are programmers? wow. I knew I
was looking for the wrong jobs.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
On 27 Sep 2006 08:51:33 -0700, <···············@gmail.com> wrote:
> Given a tree like:
>
> (77 (237 (228 (234 (231 266) 266)) (234 (231 266) 266)))
This is a book problem someplace, quick scan of PAIP didn't show it.
Even the numbers look familiar.
--
Reply-To email is ignored.
--
Posted via a free Usenet account from http://www.teranews.com
Hi,
If I've got your notation right, here is a solution in Qi.
You can run it through the Qi compiler and dump
the output to get the corresponding Lisp solution.
(define tree-paths
[Root | Nodes]
-> (map (/. Path [Root | Path]) (mapcan tree-paths Nodes))
Node -> [[Node]])
(define mapcan
_ [] -> []
F [X | Y] -> (append (F X) (mapcan F Y)))
Tests:
(tree-paths [a [b c]])
[[a b c]]
(tree-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]]
(tree-paths [a [b c d] [e f [g h]]])
[[a b c] [a b d] [a e f] [a e g h]]
Mark
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))
>
> I've been struggling with this for a few days now, and I just can't get
> it to work. Does anyone have any ideas? Anywhere to look for code for
> manipulating trees?
>
> Thanks,
> Blaine
Mark Tarver wrote:
> Hi,
>
> If I've got your notation right, here is a solution in Qi.
> You can run it through the Qi compiler and dump
> the output to get the corresponding Lisp solution.
>
> (define tree-paths
> [Root | Nodes]
> -> (map (/. Path [Root | Path]) (mapcan tree-paths Nodes))
> Node -> [[Node]])
>
> (define mapcan
> _ [] -> []
> F [X | Y] -> (append (F X) (mapcan F Y)))
This appears to correspond to this logic:
(defun tree-paths (tree)
(if (atom tree)
`((,tree))
(destructuring-bind (root &rest nodes) tree
(mapcar #'(lambda (sub-path)
`(,root ,@sub-path))
(mapcan #'tree-paths nodes)))))
Neat.