• 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
    LaserVault

    Integrate Virtual Tape to Automate Your Backups And Strengthen Your Ability To Recover From Cyber Attacks And Disasters

    With most IT departments stretched thin, finding something that can quickly free up IT time is definitely a bonus. That’s why it’s important to stop and take a look at integrating virtual tape into your backup and recovery. Virtual tape is one of those technologies where once you have it, you’ll wonder why you didn’t do it sooner. See a demo and get a $50 gift card.

    But what is it about using virtual tape that makes it so worthwhile? Why is it that so many IBM i shops are already using or considering using virtual tape for all or part of their backup and recovery systems?

    Virtual tape and virtual tape libraries offer a way to both simplify and strengthen backup and recovery operations. By incorporating virtual tape technology, automation of backups becomes possible resulting in hundreds of hours saved annually for IT departments and personnel.

    “We needed to find a replacement that would lower the maintenance cost and reduce complexity of our backup and recovery functions without a major disruption to our operations.” David Fray, Director of Enterprise Systems, ABC Financial

    LaserVault ViTL is a virtual tape and tape library solution developed specifically for use with IBM Power Systems (from AS/400 to iSeries to Power 9s). With ViTL you can:

    • Replace physical tape and tape libraries and eliminate associated delays
    • Automate backup operations, including the ability to purge or archive backups
    • Remotely manage your backups – no need to be onsite with your server
    • Save backups to a dedupe appliance and the cloud
    • Recover your data at lightspeed greatly improving your ability to recover from cyberattacks
    • And so much more

    Sign-up now to see a ViTL online demo and get a $50 Amazon e-gift card when the demo is complete as our way of saying thanks for your time. Plus when you sign-up you’ll receive a free facts comparison sheet on using virtual tape vs tape so you can compare the functionality for yourself.

    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

  • Guild Mortgage Takes The 20-Year Option For Modernization
  • IBM i Licensing, Part 3: Can The Hardware Bundle Be Cheaper Than A Smartphone?
  • Guru: The Finer Points of Exit Points
  • Big Blue Tweaks IBM i Pricing Ahead Of Subscription Model
  • We Still Want IBM i On The Impending Power E1050
  • DRV Brings More Automation to IBM i Message Monitoring
  • Managed Cloud Saves Money By Cutting System And People Overprovisioning
  • Multiple Security Vulnerabilities Patched on IBM i
  • Four Hundred Monitor, June 22
  • IBM i PTF Guide, Volume 24, Number 25

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 © 2022 IT Jungle

loading Cancel
Post was not sent - check your email addresses!
Email check failed, please try again
Sorry, your blog cannot share posts by email.