Binary Search Trees
Author Message
Binary Search Trees

Hi, I was wondering if somebody could help me with a problem I'm having.
I'm trying to write a procedure that will draw me a binary search tree on
the screen when the values are sorted in preorder. The tree is already
built, I just can't figure out how to draw it from the top middle of the
screen and down as far as it will go. I'm also trying to figure out how to
verify that a certain sequence of numbers is the actual representation of
a postorder traversal of a binary tree. This program has to be written in
Turing(unfortunately) but if anybody could at least give me some sort of
pseudocode or idea of how this program is written, it would be much
appreciated. Thanks alot.

Sincerely,

Jake Jakubek

Fri, 12 Jan 2001 03:00:00 GMT
Binary Search Trees

Quote:

> Hi, I was wondering if somebody could help me with a problem I'm having.
> I'm trying to write a procedure that will draw me a binary search tree on
> the screen when the values are sorted in preorder.

Let me generalize. When you give up the notion of doing this in onepass it
become easier.

1. Traverse the structure to figure out how much space it needs and
how much space sub sections need. That is if A points to B and C
in your tree example than B and C point to more stuff. You can
calculate how much height and width are required by the B and C
subsections. This is a very recursive notion.

2. At this point you know how much space every subsection needs
and where it goes so traverse again putting everything down.

Sun, 14 Jan 2001 03:00:00 GMT
Binary Search Trees

Quote:

> I'm trying to write a procedure that will draw me a binary search tree on
> the screen when the values are sorted in preorder.

There have been a number of articles published on drawing (binary and
general) trees `nicely'. My own contribution to this collection is a
functional language implementation, appearing in the "Functional Pearls"
column of the Journal of Functional Programming. Since it was written I
have expanded it into an applet written using Persimmon IT's MLJ
compiler. To see the demo, the code, and the article (which cites
previous articles on the subject), see

http://research.persimmon.co.uk/mlj/demos/trees/

See

http://research.persimmon.co.uk/mlj/

-- Andrew.
----------------------------------------------------------------------
Dr Andrew Kennedy, Research Scientist | fax:   +44 1223 322501
Persimmon IT, 1st floor, Block C      | phone: +44 1223 578770

Cambridge, CB4 1YG, UK                |

Fri, 19 Jan 2001 03:00:00 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages