[Back to TUTOR SWAG index] [Back to Main SWAG index] [Original]
Turbo Pascal for DOS Tutorial
by Glenn Grotzinger
Part 19: Binary Trees
copyright (c) 1995-96 by Glenn Grotzinger
OK. I stated no real problem that needed solving earlier, so we will start
getting into some new material. This is an extension to part 18, in a small
way, since it involves pointered structures similar to the linked lists,
but the procedures for handling them are much different, so I am covering
them in a seperate section.
What is a Binary Tree?
======================
A binary tree is a set of nodes with 2 possible paths for each node, left
or right. Hence, a binary tree node would look something like this:
type
nodeptr = ^node;
node = record
ourinfo: integer;
left, right: nodeptr;
end;
Conceptually (my best low ASCII rendering, trust me!), a binary tree would
look something like this. We can see from below that the possible paths of
those two directions are any numerous. As with the linked lists, nil ends
the path (knowing, it is probably garbled, but....).
NODE
_________/ \_________
/ \
NODE NODE
____/ \____ ____/ \____
/ \ / \
NODE nil nil NODE
____/ \____ ____/ \____
/ \ / \
nil nil NODE nil
____/ \____
/ \
NODE nil
____/ \____
/ \
nil nil
Rules of a Binary Tree
======================
Now that we see what the basic idea of a binary tree is, we will now study
the rules for it. The basic rules of a binary tree is the following for
any node in a binary tree commonly used for the purpose that they are used
for a lot of times -- as a binary search tree or BST. Any program code
in this section will make use of BSTs...:
1) values smaller than the value currently stored in a questioned
node goes to the left.
2) values larger than the value currently stored in a questioned
node goes the right.
3) values which are equal to other values in the tree are not placed
into the tree.
Let us see this by manually examining how we might build a small binary tree.
Example of a Binary Tree Manual Build
=====================================
Let us examine how we would build a binary tree for a set of values and
how a program would traverse the tree with a very short example.
1) Let us start examining a tree build with a value set data of 27, 54,
32, 18, and 5.
a) 27 is naturally the first or root node of the tree. There is no
issue there.
b) 54 > 27 so 54 would go to the right. Our resultant tree looks now
like this:
27
\
54
c) 32 > 27. So we would move to the right. Now we see 54 as the main
node 32 < 54, so we would go to the left. So the resultant tree
after this addition looks like this:
27
\
54
/
32
d) 18 < 27. So we would move to the left. So our tree looks like this:
27
/ \
18 54
/
32
e) 5 < 27. So we would move to the left. Now we see 18 as the current
node. 5 < 18. Then we would move to the left again. So the final
binary tree for those 5 values looks like this:
27
/ \
18 54
/ /
5 32
This is a reasonable binary tree structure. Any paths not used are
set to nil in the process. We should see now how binary trees are
constructed.
2) Now lets study traversal of the tree. It would depend on if we
visit the actual node first or last. (I will give a detailed explanation
of that last statement later.) Normally, as a standard, it's good to
use the left side first. Therefore, lets look at the tree built in #1.
The order the numbers would come up in is 5-18-27-32-54 on a basis that we
handle or visit the head node of the tree last in moving through the binary
tree. If you remember the discussion of the array binary search, we had to
sort the data to accomplish it. Here it is taken care of already for us.
Basic Idea of Programming for Binary Trees
==========================================
You may have figured out already from our preliminary discussions, that
recursion is a _major_ staple of binary tree programming (read ALWAYS use
it!). Note that a binary tree can be divided up into smaller and smaller
trees, hence our ability to use recursion. Any functions involved almost
always ends up using some order of the following pseudocode, assuming a
name of PROCEDURE for the procedure:
PERFORM PROCEDURE ON LEFT SIDE OF TREE
PERFORM ACTION ON ROOT NODE (the top node of the tree)
PERFORM PROCEDURE ON RIGHT SIDE OF TREE
We will see this idea be paramount in all the code we use. If you have
noticed in your previous work about recursion, there is always a control
statement present. Here, it will always be searching for the nil nodes.
*ALWAYS* remember to replace the nil nodes if they come up....binary
search trees are the perferred method generally, for setting up searches.
program binary_tree_example;
type
nodeptr = ^node;
node = record
somedata: integer;
left, right: nodeptr;
end;
var
tree: nodeptr;
afile: text;
i: integer;
procedure deletetree(var tree: nodeptr);
{ This procedure is a function designed to remove a binary tree
from memory }
begin
{ Given the background information, and other procedures as examples,
you should be able to come up with this one }
end;
procedure inserttree(anumber: integer; var tree: nodeptr);
{ This procedure is a function designed to create a binary tree
in memory by inserting a node in the proper position in the tree }
begin
if tree = nil then
begin
new(tree);
tree^.somedata := anumber;
tree^.left := nil;
tree^.right := nil;
end
else
begin
if anumber > tree^.somedata then
inserttree(anumber, tree^.right);
if anumber < tree^.somedata then
inserttree(anumber, tree^.left);
end;
end;
procedure searchthrutree(anumber: integer; tree: nodeptr);
{ This procedure is designed to search through a binary tree for a
particular value given in the variable anumber. }
begin
{ Given the background information and other procedures as examples,
you should be able to come up with this one. }
end;
procedure writeouttree(tree: nodeptr);
{ This procedure outputs a binary tree. }
begin
if tree <> nil then
begin
writeouttree(tree^.left);
write(afile, tree^.somedata, ',');
writeouttree(tree^.right);
end;
end;
begin
randomize;
tree := nil;
{ the last statement is required for the nil markers set up via the
BST procedures listed above }
assign(afile, 'BTEST.TXT');
rewrite(afile);
writeln(memavail, ' bytes available before tree creation.');
for i := 1 to 10 do
inserttree(random(5)+1, tree); {This creates the tree. }
writeln(memavail, ' bytes available after tree created.');
for i := 1 to 10 do
searchthrutree(random(5)+1, tree);
writeln(afile);
writeln(afile);
writeln(afile, 'I will now output the binary tree for the example.');
writeouttree(tree);
writeln;
close(afile);
writeln('Now deleting tree out of memory');
deletetree(tree);
writeln(memavail, ' bytes available after tree deletion.');
end.
This is a whole program for working with a binary tree. I purposely left
out 2 of the procedures, because the background information I gave earlier,
plus pointer logic you should have learned from part 18 should allow you to
logically come up with it. Do like I recommended in part 18 and draw it
out. Example code is often not available for many problems, but the
information _is_ there to be used. To program it is a needed skill to be
able to figure out things on your own given some information. Code should
not be handed out readily, IMO, unless there is no other way.
Practice Programming Problem #19
================================
One noted thing I have noticed with the binary search tree method especially,
is that searches can be done very quickly with any kind of data -- working
with arrays have a small way of being kludgy. Here we will see an example.
You need to create a binary data file named SOMEWRDS.DAT which should
contain 50 non-duplicated words, randomly defined (do not alphabetize them)
out of 70 total words in the file.
Allow users to type words into the keyboard, until they type the word
"quit". Case-sensitivity should not matter in any usage of words.
Write out to the user whether the word they typed was found in your
database or not.
Do not be concerned with reporting of run-time errors. Do be concerned,
though, with the removal of the final binary-tree you use.
Also for the delete code you write for binary trees, explain why your
code does what it is supposed to do.
Note
----
1) Exercise prudent practice as programmers. In the event it was not
covered, accuracy is a programmer's #1 concern, followed by efficiency
in speed, memory usage, and disk usage.
2) This program should be friendly to the user, letting the user know
precisely what is going on in all cases, even if a common error occurs,
and cleaning up anything that may be of a problematic nature from those
errors. You should have enough experience from previous parts to be
able to determine what those errors are you would commonly encounter here.
3) The goal here for this program is to create a high-quality application.
Final Statements for this Part
==============================
I know many people may wish to someday release their creations to the public,
or make programs for themselves or other's general usage. This is why I am
being so vague now about describing programs, and will be from now on.
Creativity and neatness is one of the major qualities that need to be
developed by those who program.
Also for all who program: The way to solve the problem is not always handed
to you. You have to identify problems that are encountered, sit down and
solve them. I estimate I'm probably 4-6 parts away from completing this
whole tutorial, and 2 parts away from completing the parts of the tutorial
regarding conventional Pascal programming. By now, most, if not all the
tools have been presented for you to do this, and not need me to give you
clues, and point you in the direction of what to do to solve the problem.
Most if not all problems you will encounter in normal programming practice
anywhere are normally presented in the form that this one is in -- a
statement of what the program is expected to do.
In short, I feel those who have been new programmers that have been following
my tutorial from part 1 are about ready for the *REAL* world of programming.
<grin>
Next Time
---------
I will cover several short random topics, which some of which may be
suggested by those who e-mail me. I know I will cover hooking interrupts,
calling an interrupt procedure, and linking an OBJ into Pascal code,
incorporating assembler code into pascal code, and including inline
statements in pascal program code. Is there any more people would like to
see? E-mail me. Also, I haven't gotten any comments from anyone
about how I am doing. Is anyone interested? Email ggrotz@2sprint.net.
Note: I am sorry if I offended anyone by the "Final Statements for This
Part" section. I am apologizing in advance if I come off too harsh.
[Back to TUTOR SWAG index] [Back to Main SWAG index] [Original]