Re: All paths through a tree

"Blaine" <Blaine.M.Nelson@xxxxxxxxx> 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.
.

Relevant Pages

  • Re: Extracting class data from a jar
    ... followed by code generation. ... Any idea how I could extract the relevant data? ... Didn't describe what this tree represents. ... NodeComponent nodes can only be dropped on leaf nodes, with 1 exception, ...
    (comp.lang.java)
  • Re: Would it matter if ZF was inconsistent?
    ... the infinite cartesian product to define the infinite case. ... a tree of level n. ... your leaf nodes are not leaf ... nodes of the complete binary tree but rather of certain ...
    (sci.logic)
  • Re: Would it matter if ZF was inconsistent?
    ... the infinite cartesian product to define the infinite case. ... at level n in the binary tree, ... we will call *leaf nodes* ... Extending the definitions to the transfinite, ...
    (sci.logic)
  • Re: infinity
    ... >>> if one were to consider an unending tree, each path through it would be ... >>> unending, so there would be some infinite number of branches, but there ... >>> would also be zero leaf nodes. ... >> root node corresponds to the digital point. ...
    (sci.math)
  • Re: ** says: Definition: sum{i in N} i = 0
    ... have leaf nodes must apply to paths not having leaf nodes also. ... Does WM deny that for every finite binary tree in which all paths are of ... when the tree becomes infinite, ...
    (sci.math)