Please help me with a problem I've been tackling all day but couldn't come
up with a good solution for:
I want to have a function (is-in-tree tree element) that does the following:
(setq tree (((1 2) (3 4))((5 6) (7 8))))
(is-in-tree tree 4)
returns: (0 1 1) - a list of whether I have to go left (0) or right (1) at
each branch in turn to reach the element 4
(is-in-tree tree 9)
returns: NIL
The problem is how to build up the list of "directions". Any help would be
much appreciated.
--
Thanks, Gunther. (remove 'xxx.' from address to reply)
Gunther Schmidl wrote:
> Please help me with a problem I've been tackling all day but couldn't come
> up with a good solution for:
>
> I want to have a function (is-in-tree tree element) that does the following:
>
> (setq tree (((1 2) (3 4))((5 6) (7 8))))
>
> (is-in-tree tree 4)
> returns: (0 1 1) - a list of whether I have to go left (0) or right (1) at
> each branch in turn to reach the element 4
>
> (is-in-tree tree 9)
> returns: NIL
>
> The problem is how to build up the list of "directions". Any help would be
> much appreciated.
>
> --
> Thanks, Gunther. (remove 'xxx.' from address to reply)
Find the value, then create a list of backwards directions from the element.
When this is done, reverse the list, and you will have a list to get to the
element.
Chris
Chris Croft-White wrote:
[someone else wanted a function doing this:]
>> (setq tree (((1 2) (3 4))((5 6) (7 8))))
>>
>> (is-in-tree tree 4)
>> returns: (0 1 1) - a list of whether I have to go left (0) or right (1) at
>> each branch in turn to reach the element 4
>>
>> (is-in-tree tree 9)
>> returns: NIL
>>
>> The problem is how to build up the list of "directions". Any help would be
>> much appreciated.
...
> Find the value, then create a list of backwards directions from the element.
> When this is done, reverse the list, and you will have a list to get to the
> element.
I prefer a recursive solution that doesn't require any reversing.
Look for the element in the left subtree. If you succeed, cons 0
onto the result. Otherwise, look in the right subtree. If you
succeed, cons 1 onto the result. In both fail, return NIL. You
need to be a little careful because the most natural way to handle
the base case is to consider '4 to be an acceptable tree, but then
both success and failure ought to return NIL. The neatest way to
fix this is probably with multiple values, but I suspect this is
a homework problem and most people setting this kind of homework
don't want to work with multiple values. So, instead, you probably
need to test for bottoming out at the previous level of recursion.
This would be much easier to explain just by writing out the code,
but -- as I say -- it looks like a homework problem, and I don't like
giving code in response to homework problems. Especially when it's
not made clear that it is a homework problem...
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.