Suppose I have a tree of numbers. E.g. .
/ | \
3 1 4
/ | | | \
1 5 9 2 6
/
5
/ \
3 8
Call it U. I need to be able to enmerate the branches of the tree in a
left most search. For example, with the tree above, I should get
the following 6 branches:
3 1 5 3
3 1 5 8
3 5
1 9
4 2
4 6
This ought to be easy but I I am having trouble with it.
In my situation, a list might be given in the following form:
((4 (2 (3))) (5 (2 (4 (9))) (3 (5 (2 3 7))) (4 (2 (1)))) (3 (7)))
and I want to get from it the single list (assuming I didn't make any
mistakes by hand):
(
(4 2 3)
(5 2 4 9)
(5 3 5 2)
(5 3 5 3)
(5 3 5 7)
(5 4 2 1)
(3 7)
)
If you have code that does this in clisp or scm or Portable Standard
Lisp, please let me know. Something like this is probably almost
language independent.
Allan Adler
·····@pulsar.cs.wku.edu
Allen Adler wrote:
> Suppose I have a tree of numbers. E.g. .
> / | \
> 3 1 4
> / | | | \
> 1 5 9 2 6
> /
> 5
> / \
> 3 8
>
> Call it U. I need to be able to enmerate the branches of the tree in a
> left most search. For example, with the tree above, I should get
> the following 6 branches:
>
> 3 1 5 3
> 3 1 5 8
> 3 5
> 1 9
> 4 2
> 4 6
>
> This ought to be easy but I I am having trouble with it.
> In my situation, a list might be given in the following form:
>
> ((4 (2 (3))) (5 (2 (4 (9))) (3 (5 (2 3 7))) (4 (2 (1)))) (3 (7)))
There's something a bit odd about your notation. You're using
(5 (2 (4 (9)))
(3 (5 (2 3 7)))
(4 (2 (1))))
to denote 5 with three subtrees hanging off it, but you're also
using
(5 (2 3 7))
to denote 5 with three subtrees of a different kind hanging off it.
It's not entirely clear what the general principle here is.
So let's make a slight change and use a more consistent notation.
Let's represent a tree as a sequence of nodes, each of which is a
cons-cell (atom . subtree). With this convention, your thing with
4 at the top turns into
((4 (2 (3)))
(5 (2 (4 (9)))
(3 (5 (2) (3) (7)))
(4 (2 (1))))
(3 (7)))
and all we have to do is
(defun branches (tree)
(if tree
;; The branches of a nonempty tree are obtained by
;; taking each subtree and finding its branches (with
;; the appropriate node consed on the front), and then
;; appending (well, nconc-ing) them all together.
(mapcan #'(lambda (node)
(mapcar #'(lambda (branch) (cons (car node) branch))
(branches (cdr node))))
tree)
;; An empty tree has exactly one branch.
(list nil)))
This is Common Lisp. Doing it in Scheme is similar, except that you
don't get MAPCAN provided.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.