Binary Tree

Another code example that I’ve dug out of my archives is one that shows how to create a binary tree structure and print out the results using in ALGOL 68.

The only changes I’m made to my original code before posting it was to add the GNU Licence.

When traversing a binary tree in ‘pre-order’ you print the current value and then select the left hand branch at each node, before the right hand branch; when traversing the tree in ‘post-order’ you select the left hand branch, then the right hand branch before printing the value; and when traversing the tree ‘in-order’ you traverse the left hand branch and print the value before traversing right hand branch. The result will be to print the values in the tree an alphabetic order.

{ Binary tree manipulation program - 23 May 85 - MEJT }

PROGRAM tree

BEGIN

  { This program is free software: you can redistribute it and/or modify it
  under the terms of the GNU General Public License as published by the Free
  Software Foundation, either version 3 of the License, or (at your option)
  any later version.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  for more details.

  You should have received a copy of the GNU General Public License along
  with this program.  If not, see <http://www.gnu.org/licenses/>

  Demonstrates the use of a binary tree to store information.
 
  Entering f, b, g, a, d, i, c, e, h will produce the following tree
  structure:
 
                                    f
                                   / \
                                  /   \
                                 /     \
                                b       g
                               / \       \
                              /   \       \
                             a     d       i
                                   / \     /
                                  c   e   h

  Printing this tree in pre-order should produce :  f, b, a, d, c, e, g, i, h
  Printing this tree in order should produce :      a, b, c, d, e, f, g, h, i
  Printing this tree in post-order should produce : a, c, e, d, b, h, i, g, f

  }

  MODE TREE = STRUCT (REF TREE left, right, STRING data);

  REF TREE empty = NIL;  { Define a nil pointer as an empty tree. }
  REF TREE root := empty;  { Define a new tree, initially empty. }

  STRING data;  { String to hold data entered by the user. }

  { Recursive procedure to add data to the tree. }

  PROC add = (REF REF TREE tree, STRING data)VOID:

  BEGIN
    IF tree IS empty THEN
      tree := HEAP TREE := (empty, empty, data)
    ELSE
      IF data < data OF tree THEN
        add (left OF tree, data)
      ELSE
        add (right OF tree, data)
      FI
    FI
  END;

  { Recursive procedure to print out the contents of the tree in pre-order. }

  PROC print in pre order = (REF REF TREE tree)VOID:

  BEGIN
    IF tree ISNT empty THEN
      print ((data OF tree, ", "));
      print in pre order (left OF tree);
      print in pre order (right OF tree)
    FI
  END;

  { Recursive procedure to print out the contents of the tree in order. }

  PROC print in order = (REF REF TREE tree)VOID:

  BEGIN
    IF tree ISNT empty THEN
      print in order (left OF tree);
      print ((data OF tree, ", "));
      print in order (right OF tree)
    FI
  END;

  { Recursive procedure to print out the contents of the tree in post-order. }

  PROC print in post order = (REF REF TREE tree)VOID:

  BEGIN
    IF tree ISNT empty THEN
      print in post order (left OF tree);
      print in post order (right OF tree);
      print ((data OF tree, ", "))
    FI
  END;

  { Read a series of strings from the user and add each one to a binary
    tree structure. }

  print (("*** Enter data", newline));
  WHILE (read ((data,newline)); data /= "") DO
    add (root, data)
  OD;

  print (("*** Tree in pre order", newline));
  print in pre order (root);
  print (newline);

  print (("*** Tree in order", newline));
  print in order (root);
  print (newline);

  print (("*** Tree in post order", newline));
  print in post order (root)

END

FINISH

I can’t quite believe that is it over 30 years since I wrote the original code!

*** Enter data
>f
>b
>g
>a
>d
>i
>c
>e
>h
>
*** Tree in pre order
f, b, a, d, c, e, g, i, h,
*** Tree in order
a, b, c, d, e, f, g, h, i,
*** Tree in post order
a, c, e, d, b, h, i, g, f,
$


This entry was posted in Programming and tagged . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s