Implementing Binary Trees in RPG
January 12, 2011 Ted Holt
|
Note: The code accompanying this article is available for download here. Last week, I wrote about linked lists. Each node in the list points to another node. Binary trees differ from linked lists in only one way–each node has two pointers to other nodes. How you label these pointers is up to you, but most people choose to call them left and right. Here’s a data structure that defines a node with left and right pointers.
D Record ds qualified
D Name 20a
D City 12a
D Left *
D Right *
A node that points to one or two other nodes is called a “parent” node. A node that is pointed to by another node is called a “child” node. There are many things you can do with binary trees. Since I need a technique to use as an illustration in this article, I use a binary tree to sort data. I used this technique in Pascal when I was working on my computer science degree because the Pascal compiler could not access a system sort. In order to use a binary tree to sort, I make the following rules:
For example, if we want to store nodes for Able, Baker, and Charley, any of these three binary trees is acceptable.
Loading the Tree Loading the tree is a matter of starting at the root of the tree and working through the nodes for a suitable null pointer. By suitable, I mean that the key value of a node with a null left pointer must be greater than or equal to the key value of the new node, or the key value of a node with a null right pointer must be less than the key value of the new node. The first insert into the tree puts the node at the root of the tree, since the tree is empty. My example program reads my favorite database file, QIWS/QCUSTCDT, loads it into a binary tree, and prints the tree in sorted order. The first record is for Henning. It goes into the root of the tree. The tree looks like this:
The second record is for Jones. Since the root is not null, and Henning is at the root, and Jones is alphabetically after Henning, and Henning’s right pointer is null, Jones goes into the tree like this:
The next record is for Vine. Vine can’t go in at the root. Vine is greater than Henning, but the right pointer is not null. Vine is greater than Jones, and Jones’ right pointer is null. Here’s the tree:
After the fourth record, Johnson, the tree looks like this:
On it goes.
Voilà! The load is done. The final tree looks like this:
Traversing the Tree Once the tree is loaded, printing the tree in sorted order is simple. Here’s the way it works:
And so it goes. Here’s the report. Abraham M T Isle Alison J S Isle Doe J W Sutter Henning G K Dallas Johnson J A Helen Jones B D Clay Lee F L Hector Stevens K L Denver Thomas A N Casper Tyron W E Hector Vine S S Broton Williams E D Dallas The Power and Magic of Recursion What amazes me about binary trees is the simplicity of the routines that process them. The reason the routines are so simple is because they’re recursive. Take the print routine for example.
P PrintNode b
D pi
D inAtAddr *
D* locals
D NodeAddr s *
D Node ds likeds(Record)
D based(NodeAddr)
/free
if inAtAddr = *null;
return;
endif;
NodeAddr = inAtAddr;
PrintNode (Node.Left);
PrintLine = Node.Name + ' ' + Node.City;
except Print;
PrintNode (Node.Right);
/end-free
P e
Because PrintNode is recursive, it prints a node and all the nodes under it. Since all nodes are under the root node, printing the entire tree is a simple matter of calling PrintNode one time, telling it to print the root node. In the same way, the deletion routine is recursive, deleting not only a node but its children as well. Deleting the root node deletes the entire binary tree. Pointers are Fun I always enjoyed using pointers in Pascal ages ago, when I was young and energetic and couldn’t learn enough or learn fast enough, so I’ve had a lot of fun putting these example programs together. If you decide to implement pointer-based programming techniques in your shop, please email me and tell me about your application. RELATED STORY Implementing Linked Lists in RPG
|
