• The Four Hundred
  • Subscribe
  • Media Kit
  • Contributors
  • About Us
  • Contact
Menu
  • The Four Hundred
  • Subscribe
  • Media Kit
  • Contributors
  • About Us
  • Contact
  • 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:

    1. The key value of the left child must be less than the key value of the node.
    2. The key value of the right child must be greater than or equal to the key value of the node.

    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.

    • Tyron becomes the left child of Vine.
    • Stevens becomes the left child of Tyron.
    • Alison becomes the left child of Henning.
    • Doe becomes the right child of Alison.
    • Thomas becomes the right child of Stevens.
    • Williams becomes the right child of Vine.
    • Lee becomes the left child of Stevens.
    • Abraham becomes the right child of Alison.

    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:

    • Begin at the root.
    • For each node visited, visit the left child (if there is one), the node itself, then the right child (if there is one). This is commonly called “in-order traversal.”
    • The root node is Henning.
    • Henning has a left child–Alison.
    • Alison has a left child–Abraham.
    • Abraham has no left child.
    • Print Abraham.
    • Abraham has no right child. Back to Alison.
    • Print Alison.
    • Alison has a right child–Doe.
    • Doe has no left child.
    • Print Doe.
    • Doe has no right child. Back to Alison. Back to Henning.
    • Print Henning.
    • Henning has a right child–Jones.

    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



                         Post this story to del.icio.us
                   Post this story to Digg
        Post this story to Slashdot

    Share this:

    • Reddit
    • Facebook
    • LinkedIn
    • Twitter
    • Email

    Tags:

    Sponsored by
    Maxava

    Migrate IBM i with Confidence

    Tired of costly and risky migrations? Maxava Migrate Live minimizes disruption with seamless transitions. Upgrading to Power10 or cloud hosted system, Maxava has you covered!

    Learn More

    Share this:

    • Reddit
    • Facebook
    • LinkedIn
    • Twitter
    • Email

    Sponsored Links

    SEQUEL Software:  FREE Webinar. Learn how ABSTRACT can smooth software development. Jan. 19
    Vision Solutions:  Leaders Have Vision...And Vision Has Leaders! FREE White Papers!
    Bytware:  Try StandGuard Network Security FREE for 30 days

    IT Jungle Store Top Book Picks

    BACK IN STOCK: Easy Steps to Internet Programming for System i: List Price, $49.95

    The iSeries Express Web Implementer's Guide: List Price, $49.95
    The iSeries Pocket Database Guide: List Price, $59
    The iSeries Pocket SQL Guide: List Price, $59
    The iSeries Pocket WebFacing Primer: List Price, $39
    Migrating to WebSphere Express for iSeries: List Price, $49
    Getting Started with WebSphere Express for iSeries: List Price, $49
    The All-Everything Operating System: List Price, $35
    The Best Joomla! Tutorial Ever!: List Price, $19.95

    Help/Systems Touts Deal with Asian Insurance Company i5/OS and IBM i Support: How Long Does It Last?

    Leave a Reply Cancel reply

Volume 11, Number 2 -- January 12, 2011
THIS ISSUE SPONSORED BY:

Bytware
Vision Solutions
System i Developer

Table of Contents

  • Implementing Binary Trees in RPG
  • Closing the Gaps
  • Admin Alert: Basic i/OS Error Monitoring and Response, Part 2

Content archive

  • The Four Hundred
  • Four Hundred Stuff
  • Four Hundred Guru

Recent Posts

  • POWERUp 2025 –Your Source For IBM i 7.6 Information
  • Maxava Consulting Services Does More Than HA/DR Project Management – A Lot More
  • Guru: Creating An SQL Stored Procedure That Returns A Result Set
  • As I See It: At Any Cost
  • IBM i PTF Guide, Volume 27, Number 19
  • IBM Unveils Manzan, A New Open Source Event Monitor For IBM i
  • Say Goodbye To Downtime: Update Your Database Without Taking Your Business Offline
  • i-Rays Brings Observability To IBM i Performance Problems
  • Another Non-TR “Technology Refresh” Happens With IBM i TR6
  • IBM i PTF Guide, Volume 27, Number 18

Subscribe

To get news from IT Jungle sent to your inbox every week, subscribe to our newsletter.

Pages

  • About Us
  • Contact
  • Contributors
  • Four Hundred Monitor
  • IBM i PTF Guide
  • Media Kit
  • Subscribe

Search

Copyright © 2025 IT Jungle