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/

for information about the MLJ compiler and to download the free release.

-- 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  
 
 [ 3 post ] 

 Relevant Pages 

1. Self-Adjusting Binary Search Trees (Splay Trees)

2. Self-Adjusting Binary Search Trees (Splay Trees)

3. Binary Search Trees

4. binary search tree

5. BST (yes, that's binary search tree)

6. Breadth first print procedure for binary search trees

7. need code for red-black binary search tree

8. Pls Help! Need binary search tree module

9. binary search tree

10. Binary Search Trees

11. binary search tree

12. binary search trees using classes

 

 
Powered by phpBB® Forum Software