rexx-things/samples/oorexx/treeTraversal.rex
2025-03-12 20:50:48 +00:00

159 lines
6.8 KiB
Rexx
Executable File

#!@OOREXX_SHEBANG_PROGRAM@
/*----------------------------------------------------------------------------*/
/* */
/* Copyright (c) 2005-2014 Rexx Language Association. All rights reserved. */
/* */
/* This program and the accompanying materials are made available under */
/* the terms of the Common Public License v1.0 which accompanies this */
/* distribution. A copy is also available at the following address: */
/* https://www.oorexx.org/license.html */
/* */
/* Redistribution and use in source and binary forms, with or */
/* without modification, are permitted provided that the following */
/* conditions are met: */
/* */
/* Redistributions of source code must retain the above copyright */
/* notice, this list of conditions and the following disclaimer. */
/* Redistributions in binary form must reproduce the above copyright */
/* notice, this list of conditions and the following disclaimer in */
/* the documentation and/or other materials provided with the distribution. */
/* */
/* Neither the name of Rexx Language Association nor the names */
/* of its contributors may be used to endorse or promote products */
/* derived from this software without specific prior written permission. */
/* */
/* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS */
/* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT */
/* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS */
/* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT */
/* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, */
/* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED */
/* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, */
/* OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY */
/* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING */
/* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS */
/* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
/* */
/*----------------------------------------------------------------------------*/
/******************************************************************************/
/* treeTraversal.rex Open Object Rexx Samples */
/* */
/* -------------------------------------------------------------------------- */
/* */
/* Description: */
/* Build a binary tree structure and demonstrate different traversal */
/* methods */
/******************************************************************************/
-- the tree is built by hand by linking up a series of tree nodes.
one = .Node~new(1);
two = .Node~new(2);
three = .Node~new(3);
four = .Node~new(4);
five = .Node~new(5);
six = .Node~new(6);
seven = .Node~new(7);
eight = .Node~new(8);
nine = .Node~new(9);
one~left = two
one~right = three
two~left = four
two~right = five
three~left = six
four~left = seven
six~left = eight
six~right = nine
-- now traverse the tree in different orders, printing out the
-- nodes in the order visited.
out = .array~new
.treetraverser~preorder(one, out);
say "Preorder:" out~toString("l", ", ")
out~empty
.treetraverser~inorder(one, out);
say "Inorder:" out~toString("l", ", ")
out~empty
.treetraverser~postorder(one, out);
say "Postorder:" out~toString("l", ", ")
out~empty
.treetraverser~levelorder(one, out);
say "Levelorder:" out~toString("l", ", ")
-- a node in the tree. A node has data, plus
-- left and right children
::class node
::method init
expose left right data
use strict arg data
left = .nil
right = .nil
::attribute left
::attribute right
::attribute data
-- a tree traverser. All methods here a class methods, as we do not have
-- to create instances to uses the traversers.
::class treeTraverser
-- preorder traversal. The data is added to the set
-- when the node is first visited, then it visits the left
-- and right children
::method preorder class
use arg node, out
-- a .nil value means this branch doesn't exist.
if node \== .nil then do
-- append the node data, and recurse on each branch
out~append(node~data)
self~preorder(node~left, out)
self~preorder(node~right, out)
end
-- in order traversal. The code visits the left branch first,
-- adds it's own data, then takes the right branch.
::method inorder class
use arg node, out
if node \== .nil then do
-- go to the left, then add our data, then go right
self~inorder(node~left, out)
out~append(node~data)
self~inorder(node~right, out)
end
-- post order traversal. The nodes data is not added until both
-- the left and right branches are taken
::method postorder class
use arg node, out
if node \== .nil then do
self~postorder(node~left, out)
self~postorder(node~right, out)
out~append(node~data)
end
-- level order traversal visits each node at the same level before visiting
-- the next level down.
::method levelorder class
use arg node, out
if node == .nil then return
nodequeue = .queue~new
-- method of operation. We add the current node, to the queue
-- then start pulling items off the queue, adding each of their
-- children to the end of the queue. So, for the root, we push
-- that on the queue, immediately pull it off, visit the node, then
-- push both of its children on the queue. The next two nodes visited
-- will be at level two, which will push four children on to the queue.
-- The queuing ensures we can visit each node at a common level before
-- stepping further down the tree.
nodequeue~queue(node)
loop while \nodequeue~isEmpty
next = nodequeue~pull
out~append(next~data)
if next~left \= .nil then
nodequeue~queue(next~left)
if next~right \= .nil then
nodequeue~queue(next~right)
end