From: ··············@hotmail.com
Subject: Help a Student....Please :)
Date:
Message-ID: <7f684s$10f@edrn.newsguy.com>
Hi Lisp People,
I'm taking a class on general programming languages. We have hit on Pascal, C,
C++, Java and now lisp. I must confess after having a brief introduction to the
language, I really hate it. I've been working on an assignment about a week now
and haven't gotten anywhere. I have hesitated to post here because I know you
get this all the time, but after buying two books and borrowing another I am
still no closer to my answer.
So here's the problem.
Write a function that takes a binary tree as an argument. eg. (1 (2 nil 3)(4 5))
1
/ \
2 4
/ \
3 5
The function should link each node to its parent, using properties, with the
root's parent being nill.
Here's what I know or atleast think I know.
I think it should be done using car/cdr recursion.
I know how to assign properties to the nodes.
I know how to traverse the tree.
I know after this class I'm staying away from AI.
What I don't know.
An algorithm that will allow me to traverse the tree while keeping track of the
parent nodes as I go along.
Any ideas/help will be greatly appreciated.
Keep in mind I have had only basic instruction in Lisp.
I know the basic functions.
Thanks,
Bruce
··············@hotmail.com writes:
> What I don't know.
> An algorithm that will allow me to traverse the tree while keeping track of the
> parent nodes as I go along.
Let's see if I can debug your thinking without giving away the whole
answer.
A tree traversal can allow you to visit every node in the tree. But it
cannot give you any information about how you got there. Now, when you are
at a node, you can see all the information about the node. In other words,
the traversal is simply the process that allows you to visit all the nodes
in the tree. What you do at each node is an entirely different issue.
Sunil
In article <··········@edrn.newsguy.com>,
··············@hotmail.com wrote:
> Hi Lisp People,
>
> I'm taking a class on general programming languages. We have hit on Pascal,
C,
> C++, Java and now lisp. I must confess after having a brief introduction to
the
> language, I really hate it. I've been working on an assignment about a week
now
> and haven't gotten anywhere. I have hesitated to post here because I know you
> get this all the time, but after buying two books and borrowing another I am
> still no closer to my answer.
>
> So here's the problem.
>
> Write a function that takes a binary tree as an argument. eg. (1 (2 nil 3)(4
5))
>
> 1
> / \
> 2 4
> / \
> 3 5
>
> The function should link each node to its parent, using properties, with the
> root's parent being nill.
>
> Here's what I know or atleast think I know.
> I think it should be done using car/cdr recursion.
> I know how to assign properties to the nodes.
> I know how to traverse the tree.
> I know after this class I'm staying away from AI.
>
> What I don't know.
> An algorithm that will allow me to traverse the tree while keeping track of
the
> parent nodes as I go along.
>
> Any ideas/help will be greatly appreciated.
>
> Keep in mind I have had only basic instruction in Lisp.
> I know the basic functions.
One way to do it is to write a function that takes a node and its parent as
arguments. Record the parent against the node, and then recurse down the two
branches....
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Bruce Phillip wrote:
> I'm taking a class on general programming languages. We have hit on
> Pascal, C, C++, Java and now lisp. I must confess after having a
> brief introduction to the language, I really hate it.
That's sad. Your teacher has probably told you that the only
data structures in Lisp are lists, and that the only way to
control iteration in Lisp is by recursion, and that Lisp is
slow because it's an interpreted language. All of these are
false.
(Of course, it's possible to hate Lisp after discovering what
it's really like, but there's a lot of misinformation going
about...)
> I've been
> working on an assignment about a week now and haven't gotten
> anywhere. I have hesitated to post here because I know you get this
> all the time,
Oh, how true that is. :-)
> but after buying two books and borrowing another I am
> still no closer to my answer.
>
> So here's the problem.
>
> Write a function that takes a binary tree as an argument.
> eg. (1 (2 nil 3)(4 5))
>
> 1
> / \
> 2 4
> / \
> 3 5
So your representation of a node is (value left right)? Shouldn't
the tree look like
.1.
/ \
2 4
\ /
3 5
in that case?
> The function should link each node to its parent, using properties, with the
> root's parent being nill.
I don't understand. "Properties"? Do you mean as in property lists of
symbols? (If so, I'm at a loss since there are no symbols in your example
apart from NIL.) Or something else that was defined in your class but
isn't a standard Lisp term?
> Here's what I know or atleast think I know.
> I think it should be done using car/cdr recursion.
> I know how to assign properties to the nodes.
> I know how to traverse the tree.
> I know after this class I'm staying away from AI.
>
> What I don't know.
> An algorithm that will allow me to traverse the tree while keeping
> track of the parent nodes as I go along.
Well, I can answer that bit even though I don't know what you
mean about "properties". Do it by recursion. Make one argument
to the recursive function you define the parent of the node you're
looking at.
(defun traverse-tree (node parent)
;; blah blah blah
(traverse-tree (car node) node)
;; blah blah blah blah
)
May I also make a stylistic suggestion? I've written CAR above,
which is bad for two reasons. Firstly, with your representation
of trees the CAR of a node isn't one of its children anyway :-).
Secondly, you might later want to use the same tree-traversal
function with a different representation of trees -- as structures
or CLOS classes. (If you didn't know Lisp has user-defined structures
with named fields, and a very sophisticated object system, then your
teacher has misled you.) So, I'd begin with something like
(defun tnode-value (node) (first node))
(defun tnode-left (node) (second node))
(defun tnode-right (node) (third node))
(defun make-tnode (value left right) (list value left right))
(defun tnode-absent? (node) (eq node nil))
and now you can define your tree-traversing stuff in a way that will
cope just fine if you change the representation of trees. If your
teacher complains that this will be inefficient, point out that
modern Lisps let you declare functions to be inline, so that if
performance turns out to be a problem you can do that to the accessor
functions above and not lose any efficiency at all.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
··············@hotmail.com wrote:
> Write a function that takes a binary tree as an argument.
> eg. (1 (2 nil 3)(4 5))
>
> 1
> / \
> 2 4
> / \
> 3 5
Here nodes are represented as 3-element lists, where the first element
is the value, the second element the right branch and the third element
the left branch, right? Then it would be wiser to write the tree above
as (1 (2 nil 3) (4 5 nil)).
We might as well formalize this representation by defining a few
functions:
make-node (value, left, right) = list (value,right,left)
make-leaf (value) = list (value, nil, nil)
value-of (node) = first (node)
left-branch (node) = third (node)
right-branch (node) = second (node)
is-leaf (node) = null (left-branch (node)) and
null (right-branch (node))
> I know how to traverse the tree.
Something like the following, right?
traverse (node) =
do-something-with (node)
if is-leaf (node)
return
else traverse (left-branch (node))
traverse (right-branch (node))
> What I don't know:
> An algorithm that will allow me to traverse the tree while keeping
> track of the parent nodes as I go along.
Just give the traverse function an extra parameter that says who's
calling it. Like:
traverse (node, parent) =
do-something-with (node, parent)
if is-leaf (node)
return
else traverse (left-branch (node), node)
traverse (right-branch (node), node)
> Keep in mind I have had only basic instruction in Lisp.
> I know the basic functions.
I used only LIST, FIRST, SECOND, THIRD and NULL.
If necessary, you could define FIRST, SECOND and THIRD in terms
of CAR and CDR.
> I know after this class I'm staying away from AI.
This problem has almost nothing to do with Lisp and even less with AI.
Good luck.
Arthur Lemmens
··············@hotmail.com writes:
> Hi Lisp People,
>
> I'm taking a class on general programming languages. We have hit on Pascal, C,
> C++, Java and now lisp. I must confess after having a brief introduction to the
> language, I really hate it. I've been working on an assignment about a week now
> and haven't gotten anywhere. I have hesitated to post here because I know you
> get this all the time, but after buying two books and borrowing another I am
> still no closer to my answer.
>
> So here's the problem.
>
> Write a function that takes a binary tree as an argument. eg. (1 (2 nil 3)(4 5))
>
> 1
> / \
> 2 4
> / \
> 3 5
>
> The function should link each node to its parent, using properties, with the
> root's parent being nill.
first, off, i'd not use conses. try this one on for size
(defstruct node (up left right datum))
now, build the tree with the parts pointing to the right places and
you're done. the structure will keep track of the things you need.
graham's book (i do not recall off hand which one) has a section on
doubly-linked lists. i'd borrow heavily from that. here's the
section (plus some of my own hacking and playing around). it's
without much comment, but perhaps it can be of help. pay particular
attention to dl-insert and list->dl. modify and use this for your
fully linked binary tree with data.
;;; dl-list.cl - doubly linked list
(in-package 'user)
(defstruct (dl (:print-function print-dl-1))
"double-linked list unit"
prev data next)
(defun print-dl (dl stream depth)
"print a double-linked list"
(declare (ignore depth))
(format stream "#<DL ~A>" (dl->list dl)))
(defun dl-head (dlst)
"grab head of the double-link list"
(if (and (dl-p dlst)
(dl-prev dlst))
(dl-head (dl-prev dlst))
dlst))
(defun dl-tail (dlst)
"grab tail of the double-link list"
(if (and (dl-p dlst)
(dl-next dlst))
(dl-tail (dl-next dlst))
dlst))
(defun dl-seek (dlst n)
"relative seek for double-link list"
(labels ((rec-n (dlst n)
(if (zerop n)
dlst
(if (dl-next dlst)
(rec-n (dl-next dlst) (- n 1))
nil)))
(rec-p (dlst n)
(if (zerop n)
dlst
(if (dl-prev dlst)
(rec-p (dl-prev dlst) (+ n 1))
nil))))
(if (dl-p dlst)
(if (< n 0)
(rec-p dlst n)
(rec-n dlst n))
nil)))
(defun dl-elt (dlst n)
"relative elt for double-link list"
(dl-data (dl-seek dlst n)))
(defun print-dl-1 (dlx stream depth)
"print a double-linked list"
(declare (ignore depth))
(format stream "#<DL (")
(labels ((rec (dl)
(if (eq dl dlx)
(format stream "[~A]" (dl-data dl))
(format stream "~A" (dl-data dl)))
(when (dl-next dl)
(format stream " ")
(rec (dl-next dl)))))
(rec (dl-head dlx)))
(format stream ")>"))
(defun dl->list (lst)
"convert double-linked list to ordinary list"
(if (dl-p lst)
(cons (dl-data lst) (dl->list (dl-next lst)))
lst))
(defun dl-r->list (lst)
"convert double-linked list to ordinary list by moving backwards"
(if (dl-p lst)
(cons (dl-data lst) (dl-r->list (dl-prev lst)))
lst))
(defun dl-nreverse (dlst)
(labels ((rec (dlst)
(prin1 (dl-data dlst)) (terpri)
(rotatef (dl-next dlst) (dl-prev dlst))
(when (dl-prev dlst) (rec (dl-prev dlst)))))
(rec (dl-head dlst)))
dlst)
(defun dl-insert (x lst)
(let ((elt (make-dl :data x :next lst)))
(when (dl-p lst)
(when (dl-prev lst)
(setf (dl-next (dl-prev lst)) elt
(dl-prev elt) (dl-prev lst)))
(setf (dl-prev lst) elt))
elt))
(defun list->dl (lst)
"convert ordinary list to double-linked list"
(reduce #'dl-insert lst
:from-end t :initial-value nil))
(defun dl-list (&rest args)
(reduce #'dl-insert args
:from-end t :initial-value nil))
(defun dl-remove (lst)
(when (dl-prev lst)
(setf (dl-next (dl-prev lst)) (dl-next lst)))
(when (dl-next lst)
(setf (dl-prev (dl-next lst)) (dl-prev lst)))
(dl-next lst))
> Here's what I know or atleast think I know.
> I think it should be done using car/cdr recursion.
> I know how to assign properties to the nodes.
> I know how to traverse the tree.
> I know after this class I'm staying away from AI.
> What I don't know. An algorithm that will allow me to traverse the
> tree while keeping track of the parent nodes as I go along.
> Any ideas/help will be greatly appreciated.
>
> Keep in mind I have had only basic instruction in Lisp.
> I know the basic functions.
>
> Thanks,
> Bruce
let us know how it goes.
--
johan kullstam