HELP! I just started working with Lisp and I have a problem. I have a
project in which I have to manipulate binary trees using Lisp. The tree
is just a tree of integer values. Each node will have its value and two
"pointers" to the left and right subtrees. For this project, I'm using
Lisp's property lists. My problem is in INSERTING into a tree (the
actual Lisp insertion, not the binary tree insertion algorithm). I've tried
numerous ways to create a new node and insert it into the tree, but the
global property of property lists in causing the problem. Also, for
this project I am not allowed to use any of the "destructive" function
calls of Lisp (i.e. replca, replcd).
CAN ANYONE HELP ME WITH THIS PROBLEM????????? If anyone has any
possible solutions to my problem, or a better way of representing binary
trees in Lisp for my purpose, PLEASE post it here. Thanks in advance!!!
...Charles Bayley...
(·······@eve.Wright.Edu)
In article <····@thor.wright.EDU> ·······@eve.UUCP (Charles Bayley) writes:
>HELP! I just started working with Lisp and I have a problem. I have a
>project in which I have to manipulate binary trees using Lisp. The tree
>is just a tree of integer values. Each node will have its value and two
>"pointers" to the left and right subtrees. For this project, I'm using
>Lisp's property lists.
Where are you storing the property lists? Integers don't have property
list cells. If you're using the property list of symbols then where are
you getting the symbols from?
> My problem is in INSERTING into a tree (the
>actual Lisp insertion, not the binary tree insertion algorithm). I've tried
>numerous ways to create a new node and insert it into the tree, but the
>global property of property lists in causing the problem. Also, for
>this project I am not allowed to use any of the "destructive" function
>calls of Lisp (i.e. replca, replcd).
Property list operations are destructive. The only way to do this without
any destructive operations is to use the functional programming style,
where the TREE-INSERT and TREE-DELETE functions return a copy of the
original tree with the appropriate changes made.
Why can't you use destructive operations? In any case, here's the
functional version:
;;; Represent a tree as a list of three objects:
;;; (value left-subtree right-subtree)
;;; An empty tree is NIL.
(defun tree-value (tree)
(first tree))
(defun tree-left (tree)
(second tree))
(defun tree-right (tree)
(third tree))
(defun make-tree (value left right)
(list value left right))
(defun tree-insert (new-value tree)
(if (null tree)
(make-tree new-value nil nil)
(let ((node-value (tree-value tree)))
(cond ((= node-value new-value)
tree)
((< new-value node-value)
(make-tree node-value (tree-insert new-value (tree-left tree))
(tree-right tree)))
(t (make-tree node-value (tree-left tree)
(tree-insert new-value (tree-right tree))))))))
(defun tree-delete (value tree)
(if (null tree)
nil
(let ((node-value (tree-value tree)))
(cond ((= node-value value)
(merge-trees (tree-left tree) (tree-right tree)))
((< value node-value)
(make-tree node-value (tree-delete value (tree-left tree))
(tree-right tree)))
((> value node-value)
(make-tree node-value (tree-left tree)
(tree-delete value (tree-right tree))))))))
(defun merge-trees (tree1 tree2)
(cond ((null tree1) tree2)
((null tree2) tree1)
(t (merge-trees (tree-left tree1)
(merge-trees (tree-right tree1)
(tree-insert (tree-value tree1)
tree2))))))
(defun tree-contains-value? (value tree)
(if (null tree) nil
(let ((node-value (tree-value tree)))
(cond ((= value node-value) t)
((< value node-value)
(tree-contains-value? value (tree-left tree)))
(t (tree-contains-value? value (tree-right tree)))))))
--
Barry Margolin, Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar