Board index » delphi » binary search tree

binary search tree

Hi all,

Does anybody know if there is a way to traverse the BST in such a way that
the printout looks exactly like the tree itself(, i.e. not in sequential
order in a row) and if yes, would care to show me an example of it?

Regards,
K.

 

Re:binary search tree


Kislany schreef:

Quote

> Hi all,

> Does anybody know if there is a way to traverse the BST in such a way that
> the printout looks exactly like the tree itself(, i.e. not in sequential
> order in a row) and if yes, would care to show me an example of it?

> Regards,
> K.

Hope this helps:

If you want to display the BST as a tree, not just as a row of
numbers, you have to traverse it in-order. That is:
Traverse-left, process_node, traverse-right.

1. You could display for each process_node:
- the level of the node
- if it's a left or a right node (of the parent-node)
- the value

If 1. works correctly, try:

2. Something like this:
Think of your screen as a 80 x 20 grid of characters.
Display the value of your root-node at line 1 column 40.
For each traverse to the left divide the remaining space
to the left by 2 {left_x:=left_x div 2} and display the
value of the next node there. That is: on the next line.
The same for the right { right_x:= middle_column +
((right_x - middle_column) div 2) }.

For each level down you could display a '/' for going to the
left at about 3/4 of the remaining space at the left side,
and a '\' for going right at 1/4 of the remaining space at the
right side. Obviously you have to increase the line-counter
accordingly.

In a primitive way you are now able to display a BST of about
5 levels deep on a text-screen. If you calculate the number
of spaces between two values on the same line properly, you
can even do without the CRT-procedure gotoxy().

3. If 2. works and you have plenty of time left, try to turn it
into a horizontal layout or a graphical display.

Greetings. Huub.

Other Threads