Category : C++ Source Code
Archive   : SBBTREE.ZIP
Filename : TREE.CPP

/*
* Program ID: tree.cpp
*
* Description: Implementation for in-memory balanced binary
* trees
*
* Input Parameters: none
*
* Return/Exit Values: none
*
* Input Files: none
*
* Output Files: none
*
* Linking Procedures: none
*
* Special Logic Notes: This C++ class uses the AVL (Adelson-Velski and
* Landis) method for correcting binary tree
* imbalances.
*
* Taken from The C Users Journal, January 1991
* pages 65-74
*
* This class is not able to use a container iterator to delete or detach
* Objects stored in the tree. It results in the corruption of the tree,
* and causes a refrence to de-allocated memory.
*
**************************************************************************
*
* Modification Log
**************************************************************************
*
*/

/*** revision history ***/
/* 1 TREE.CPP 3-Jul-91,1:42:34,`ERIK' Initial Code Checkin. */
/* 2 TREE.CPP 28-Jul-91,20:44:32,`ERIK' Saved during development. */
/* 3 TREE.CPP 28-Jul-91,23:01:20,`ERIK' changed some things. */
/* 4 TREE.CPP 8-Nov-91,19:31:34,`ERIK' Changed to new version tracking \ */
/* variables for .cpp modules. */
/* 5 TREE.CPP 10-Nov-91,21:38:10,`ERIK' spaced some #defines out. */
/* 6 TREE.CPP 10-Nov-91,22:20:16,`ERIK' Integrated with classlib by \ */
/* inheriting from Object, and making printOn/print_tree pass a Rost */
/* 7 TREE.CPP 10-Nov-91,22:31:28,`ERIK' Spaced version string out. */
/* 8 TREE.CPP 10-Nov-91,22:35:50,`ERIK' Unspaced version string out. */
/* 9 TREE.CPP 10-Nov-91,23:08:44,`ERIK' */
/* Passed test program, inheriting from \ */
/* Object. */
/* 10 TREE.CPP 10-Nov-91,23:12:06,`ERIK' */
/* Passed test program, inheriting from \ */
/* Object. */
/* 11 TREE.CPP 10-Nov-91,23:30:36,`ERIK' Removed dsize data element. */
/* 12 TREE.CPP 10-Nov-91,23:33:06,`ERIK' Got the class working again by \ */
/* re-adding dsize data element. */
/* 13 TREE.CPP 11-Nov-91,12:51:18,`ERIK' */
/* Passed test program. Comparing now done \ */
/* by calling compare method, which uses compare operators inherited */
/* Sortable class */
/* 14 TREE.CPP 11-Nov-91,13:00:22,`ERIK' */
/* Removed dsize data element, alloc_data, \ */
/* copy_data methods. Passed test program. */
/* 15 TREE.CPP 11-Nov-91,13:20:02,`ERIK' Made all the methods return \ */
/* PCObject rather the Pvoid. Passed test program. */
/* 16 TREE.CPP 11-Nov-91,13:29:18,`ERIK' Made public methods return \ */
/* NOOBJECT instead of NULL to better integrate the class into the c */
/* 17 TREE.CPP 11-Nov-91,13:55:08,`ERIK' Make current methods adhere to \ */
/* Classlib method naming convention. */
/* 18 TREE.CPP 11-Nov-91,14:48:38,`ERIK' Spinkled const all over and \ */
/* made a number of the passed and return types RCObjects to more cl */
/* match what the classlib is doing. Ran test program OK. */
/* 19 TREE.CPP 11-Nov-91,15:23:40,`ERIK' Added elements method. */
/* 20 TREE.CPP 12-Nov-91,1:01:40,`ERIK' Got basic iterator code in place. */
/* Still need to work out the methods so that they will start, resta */
/* increment (++), and test (operator int) correctly. */
/* 21 TREE.CPP 12-Nov-91,11:22:48,`ERIK' */
/* Got basic iterator functionality. But \ */
/* it does not recognize the end of the tree until it tries to refre */
/* element after the last, causing an error. Need to make the int o */
/* smarter. */
/* 22 TREE.CPP 12-Nov-91,12:34:06,`ERIK' */
/* Finally worked out the last problems \ */
/* with the iterator. Passed the test program. */
/* 23 TREE.CPP 15-Nov-91,15:32:16,`ERIK' Added error code to make sure */
/* that the iterator checks lastError. Also added code to */
/* keep the Container::itemsInContainer variable in sync */
/* with the number of nodes in the tree. */
/* 24 TREE.CPP 17-Nov-91,20:57:36,`ERIK' Need to eliminate the \ */
/* duplication of objects when written to persistent store by */
/* the TABSTree class and the TABSNode class. */
/* 25 TREE.CPP 11-Dec-91,19:07:52,`ERIK' Added error strings and the */
/* errorString method to the class. */
/* 26 TREE.CPP 13-Dec-91,0:31:04,`ERIK' changed something? */
/* 27 TREE.CPP 29-Dec-91,10:42:50,`ERIK' ported code to version 3.0 */
/* of classlib. Also corrected a number of bugs. */
/* 28 TREE.CPP 6-Feb-92,23:20:46,`ERIK' changed appropriate Object */
/* arguments and such to Sortable. */
/* 29 TREE.CPP 7-Feb-92,17:45:12,`ERIK' Through testing, it has been \ */
/* determined that the fault is not in the btree module nor in the \ */
/* TTopic::getIndent method. This is due to this version of the \ */
/* driver program iterating over all the nodes in the tree and apply */
/* the getIndent method to all of them, without a failure. */
/* 30 TREE.CPP 8-Feb-92,12:01:44,`ERIK' Stalled out trying to \ */
/* solve the virtual method not being called problem. This version */
/* represents the stalled spot. */
/*** revision history ***/

/***************************************************************************/
/* Header Files: */

// Standard C headers:
#include
#include
#include
#include
#include

// Project Headers:
#include "tree.hpp"
#include "topic.hpp"

/***************************************************************************/

/***-=>keyflag<=-- "&(#)%n %v %d %t" ***/
static char TLIBSTRING[] = "&(#)TREE.CPP 30 8-Feb-92 12:01:44";

/***************************************************************************/

// constants which tell which way the tree is out of balance
#define BALANCED 0
#define LEFT -1
#define RIGHT 1

#define DOUBLE_LEFT (LEFT*2)
#define DOUBLE_RIGHT (RIGHT*2)

// messages used by getprev () and getnext ()
#define RETURN_CURRENT 0
#define RETURN_PARENT 1

// maximum allowable imbalance in a subtree
#define ALLOWABLE_IMBALANCE 1

// maximum characters in an output buffer line.
#define MAXBUFF 100

// messages passed from a child to a parent
#define DELETE_THIS_BalancedTreeNode 2
#define TREE_SHRANK 1
#define NO_CHANGE 0
#define BalancedTreeNode_NOT_FOUND -2

/***************************************************************************/

RContainerIterator BalancedTree::initIterator () const
{
return (*(ContainerIterator *)new BalancedTreeIterator (*this));
}

/***************************************************************************/

BalancedTreeIterator::BalancedTreeIterator (RCBalancedTree tree) :
beingIterated (tree)
{
firstflag = 1; // set first time though flag
last = &beingIterated.findLast ();
beingIterated.findFirst (); // reset current so as not to match last
}

/***************************************************************************/

BalancedTreeIterator::operator RObject ()
{
if (beingIterated.lastError () != OK)
return (NOOBJECT);
else
return ((RObject)beingIterated.current->data);
}

/***************************************************************************/

void BalancedTreeIterator::restart ()
{
firstflag = 1; // set first time though flag
}

/***************************************************************************/

RObject BalancedTreeIterator::operator ++ ()
{
// if we are at that first node (head), we have just initialized the
// iterator, so here we must return the first node (head), rather than
// the second one.

// return refrence before incrementing

if (beingIterated.lastError () != OK)
return (NOOBJECT);

if (firstflag)
{
firstflag = 0;
RObject retval = (RObject)beingIterated.findFirst ();
beingIterated.findNext ();
return (retval);
}
else
{
RObject retval = (RObject)beingIterated.findCurr ();
beingIterated.findNext ();
return (retval);
}
}

/***************************************************************************/

RObject BalancedTreeIterator::operator ++ (int)
{

// return refrence after incrementing

if (beingIterated.lastError () != OK)
return (NOOBJECT);

if (firstflag)
{
firstflag = 0;
return ((RObject)beingIterated.findFirst ());
}
else
return ((RObject)beingIterated.findNext ());
}

/***************************************************************************/

BalancedTreeIterator::operator int ()

{
if (beingIterated.lastError () != OK)
return (0);

if (beingIterated.current->data != last || firstflag)
return (1);
else
return (0);
}

/***************************************************************************/
/***************************************************************************/

static const char *unknown_err = "Unknown error code";
static const char *ok = "No Error";
static const char *mem_alloc_fail = "Could not allocate memory for node";
static const char *no_dupes = "Duplicates not allowed";
static const char *tree_empty = "Tree is empty";
static const char *no_such_node = "No such node";
static const char *obj_not_sort = "Object not sortable";

/***************************************************************************/

const char *BalancedTree::errorString ()

{
switch (errval)
{
case OK:
return (ok);

case MEM_ALLOC_FAIL:
return (mem_alloc_fail);

case NO_DUPES:
return (no_dupes);

case TREE_EMPTY:
return (tree_empty);

case NO_SUCH_BalancedTreeNode:
return (no_such_node);

case OBJECT_NOT_SORTABLE:
return (obj_not_sort);
}

return (unknown_err);
}

/***************************************************************************/

void BalancedTree::delete_data (BalancedTreeNode *nodeptr)

{
if (detach_deletes_data)
delete nodeptr->data;
nodeptr->data = NULL;
}

/***************************************************************************/

void BalancedTree::delete_subtree (BalancedTreeNode *nodeptr)

{
if (nodeptr->right != NULL)
{
delete_subtree (nodeptr->right);
delete nodeptr->right;
}

if (nodeptr->left != NULL)
{
delete_subtree (nodeptr->left);
delete nodeptr->left;
}

delete_data (nodeptr);
}

/***************************************************************************/

void BalancedTree::rebalance (BalancedTreeNode *parent)

{
BalancedTreeNode *p1;
BalancedTreeNode *p2;
BalancedTreeNode swapnode;

if (parent->balance == DOUBLE_LEFT)
{
if (parent->left->balance != RIGHT) // LL imbalance
{
p1 = parent->left;
parent->left = p1->right;
p1->right = p1; // will resolve properly after node swap
if (p1->balance == LEFT)
parent->balance = p1->balance = BALANCED;
else
{
parent->balance = LEFT;
p1->balance = RIGHT;
}
swapnode = *parent;
*parent = *p1;
*p1 = swapnode;
}
else
{
p1 = parent->left; // LR imbalance
p2 = p1->right;
p1->right = p2->left;
p2->left = p1;
parent->left = p2->right;
p2->right = p2; // will resolve properly after node swap
if (p2->balance == RIGHT)
{
parent->balance = BALANCED;
p1->balance = LEFT;
p2->balance = RIGHT;
}
else if (p2->balance == LEFT)
{
parent->balance = RIGHT;
p1->balance = BALANCED;
p2->balance = BALANCED;
}
else
parent->balance = p1->balance = p2->balance = BALANCED;
swapnode = *parent;
*parent = *p2;
*p2 = swapnode;
}
}
else
{ // parent->balance == DOUBLE_RIGHT
if (parent->right->balance != LEFT) // RR imbalance
{
p1 = parent->right;
parent->right = p1->left;
p1->left = p1; // will resolve properly after node swap

if (p1->balance == RIGHT)
parent->balance = p1->balance = BALANCED;
else
{
parent->balance = RIGHT;
p1->balance = LEFT;
}
swapnode = *parent;
*parent = *p1;
*p1 = swapnode;
}
else
{
p1 = parent->right;
p2 = p1->left;
p1->left = p2->right;
p2->right = p1;
parent->right = p2->left;
p2->left = p2; // will resolve properly after node swap

if (p2->balance == RIGHT)
{
parent->balance = LEFT;
p1->balance = BALANCED;
p2->balance = BALANCED;
}
else if (p2->balance == LEFT)
{
parent->balance = BALANCED;
p1->balance = RIGHT;
p2->balance = BALANCED;
}
else
parent->balance = p1->balance = p2->balance = BALANCED;

swapnode = *parent;
*parent = *p2;
*p2 = swapnode;
}
}
}

/***************************************************************************/

int BalancedTree::addnode (BalancedTreeNode *parent, BalancedTreeNode *newnode)

{
int retval;
int addside;

if ((retval = compare (*parent->data, *newnode->data)) != 0)
{
if (retval < 0) // parent < newnode - add on RIGHT size of parent
{
if (parent->right != NULL)
retval = addnode (parent->right, newnode);
else
{
parent->right = newnode;
retval = (parent->balance == LEFT) ? 0 : 1;
}
addside = RIGHT;
}
else // parent > newnode - add on LEFT size of parent
{
if (parent->left != NULL)
retval = addnode (parent->left, newnode);
else
{
parent->left = newnode;
retval = (parent->balance == RIGHT) ? 0 : 1;
}
addside = LEFT;
}
}
else // duplicate item not allowed
{
errval = NO_DUPES;
return (0);
}

// Part B - adjust the parent balance of necssary
if (retval != 0) // tree changed depth
{
parent->balance += addside;
if (abs (parent->balance) > ALLOWABLE_IMBALANCE)
rebalance (parent);
}
return (parent->balance == BALANCED) ? 0 : retval;
}

/***************************************************************************/

int BalancedTree::add (RSortable data)

{ // build the node to be added
if (!data.isSortable ())
{
errval = OBJECT_NOT_SORTABLE;
return (0);
}

errval = OK;
BalancedTreeNode *nptr = new BalancedTreeNode;

if (nptr == NULL) // unable to allocate new node
{
errval = MEM_ALLOC_FAIL;
return (0);
}
nptr->left = NULL;
nptr->right = NULL;
nptr->balance = BALANCED;
nptr->data = &data;

// now determine where to add the new node
if (head == NULL)
head = nptr;
else
addnode (head, nptr);

Container::itemsInContainer++; // increment node count
if (errval == OK)
return (1);
else
return (0);
}

/***************************************************************************/

BalancedTreeNode *BalancedTree::walk_tree (BalancedTreeNode *nptr, int walk_size)

{
if (walk_size == RIGHT)
{
if (nptr->right == NULL)
return (nptr);
else
return (walk_tree (nptr->right, walk_size));
}
else
{
if (nptr->left == NULL)
return (nptr);
else
return (walk_tree (nptr->left, walk_size));
}
}

/***************************************************************************/

int BalancedTree::remove_node (BalancedTreeNode *currnode, RSortable key)

{
int retval;
int crval;
int remove_side;
BalancedTreeNode *new_head_ptr;
BalancedTreeNode work_node;

if ((crval = compare (*currnode->data, key)) < 0)
{
if (currnode->right != NULL)
{
remove_side = RIGHT;
retval = remove_node (currnode->right, key);
}
else
return (BalancedTreeNode_NOT_FOUND);
}
else if (crval > 0)
{
if (currnode->left != NULL)
{
remove_side = LEFT;
retval = remove_node (currnode->left, key);
}
else
return (BalancedTreeNode_NOT_FOUND);
}
else // currnode is the node to remove
{
if (currnode->left == NULL && currnode->right == NULL) // no children
return (DELETE_THIS_BalancedTreeNode);
else if ((currnode->left == NULL && currnode->right != NULL) ||
(currnode->left != NULL && currnode->right == NULL))
{
// one child
BalancedTreeNode *saveptr;
if (currnode->left != NULL)
{
saveptr = currnode->left;
*currnode = *(currnode->left);
delete saveptr;
}
else
{
saveptr = currnode->left;
*currnode = *(currnode->right);
delete saveptr;
}
return (TREE_SHRANK);
}
else // two children
{
if (currnode->balance == LEFT)
new_head_ptr = walk_tree (currnode->left, RIGHT);
else
new_head_ptr = walk_tree (currnode->right, LEFT);
work_node.data = new_head_ptr->data;
remove (*new_head_ptr->data);
delete_data (currnode);
currnode->data = work_node.data;
return (NO_CHANGE);
}
}

// we're on the way back up the recursion stack
if (retval == DELETE_THIS_BalancedTreeNode)
{
if (remove_side == RIGHT)
{
delete_data (currnode->right);
delete currnode->right;
currnode->right = NULL;
currnode->balance += LEFT;
}
else
{
delete_data (currnode->left);
delete currnode->left;
currnode->left = NULL;
currnode->balance += RIGHT;
}

if (abs (currnode->balance) > ALLOWABLE_IMBALANCE)
rebalance (currnode);

if (currnode->balance == BALANCED)
return (TREE_SHRANK);
else
return (NO_CHANGE);
}
else if (retval == TREE_SHRANK)
{
if (remove_side == LEFT)
currnode->balance += RIGHT;
else
currnode->balance += LEFT;

if (abs (currnode->balance) > ALLOWABLE_IMBALANCE)
rebalance (currnode);

if (currnode->balance == BALANCED)
return (TREE_SHRANK);
else
return (NO_CHANGE);
}
else
return (NO_CHANGE);
}

/***************************************************************************/

void BalancedTree::detach (RCSortable o, int deleteit)

{
detach_deletes_data = deleteit;
remove (o);
}

/***************************************************************************/

int BalancedTree::remove (RCSortable key) // delete a node

{
int retval;

errval = OK;

if (head == NULL)
{
errval = TREE_EMPTY;
return (0);
}
else
{
retval = remove_node (head, (RSortable)key);
switch (retval)
{
case BalancedTreeNode_NOT_FOUND:
errval = NO_SUCH_BalancedTreeNode;
return (0);

case DELETE_THIS_BalancedTreeNode:
delete_data (head);
delete head;
head = NULL;
Container::itemsInContainer--; // decrement node count
return (1);

default:
return (1);
}
}
}

/***************************************************************************/

BalancedTreeNode *BalancedTree::findnode (BalancedTreeNode *currnode,
RCSortable key)

{
int cresult = compare (*currnode->data, (RSortable)key);

if (cresult < 0) // node < data - go right
{
if (currnode->right == NULL)
return (NULL); // node not found
else
return (findnode (currnode->right, key));
}
else if (cresult > 0) // node > data - go left
{
if (currnode->left == NULL)
return (NULL); // node not found
else
return (findnode (currnode->left, key));
}
else // this must be the place!
return (currnode);
}

/***************************************************************************/

int BalancedTree::compare (RSortable data1, RSortable data2)

{
if ((RSortable)data1 == (RSortable)data2)
return (0);
else if ((RSortable)data1 > (RSortable)data2)
return (1);
else
return (-1);
}

/***************************************************************************/

RSortable BalancedTree::find (RCSortable key) // locate a node

{
BalancedTreeNode *nodeptr;

errval = OK;

// if head is NULL, there is no tree, so return NOOBJECT
if (head == NULL)
{
errval = TREE_EMPTY;
return ((RSortable)NOOBJECT);
}

// if current is not NULL, and data is equal to the key, return the value
if (current != NULL)
{
if (*current->data == key) // Virtual isEqual not working here
return (*current->data);
}

// else we must search for the key
nodeptr = findnode (head, key);
if (nodeptr == NULL)
{
errval = NO_SUCH_BalancedTreeNode;
return ((RSortable)NOOBJECT);
}
else
{
current = nodeptr;
return (*nodeptr->data);
}
}

/***************************************************************************/

RCSortable BalancedTree::findFirst (void) // locate first entry in tree

{
errval = OK;
if (head != NULL)
{
current = walk_tree (head, LEFT);
return (*current->data);
}
else
{
errval = NO_SUCH_BalancedTreeNode;
return ((RCSortable)NOOBJECT);
}
}

/***************************************************************************/

RCSortable BalancedTree::findLast (void) // locate the last entry in a tree

{
errval = OK;
if (head != NULL)
{
current = walk_tree (head, RIGHT);
return (*current->data);
}
else
{
errval = NO_SUCH_BalancedTreeNode;
return ((RCSortable)NOOBJECT);
}
}

/***************************************************************************/

int BalancedTree::getprev (BalancedTreeNode *currnode)

{
int side;
int retval;
int cresult;

cresult = compare (*currnode->data, *current->data);
if (cresult < 0) // node < data - go right
{
side = RIGHT;
retval = getprev (currnode->right);
}
else if (cresult > 0) // node > data - go left
{
side = LEFT;
retval = getprev (currnode->left);
}
else // this must be the place!
{
if (current->left != NULL)
{
current = current->left; // step to left
while (current->right != NULL) // then walk the right edge of
current = current->right; // the subtree
return (RETURN_CURRENT);
}
else
return (RETURN_PARENT);
}

// unwind the recusion stack
if (retval == RETURN_PARENT)
{
if (side != LEFT)
{
current = currnode;
return (RETURN_CURRENT);
}
else
return (retval);
}
return (0); // should never get here.
}

/***************************************************************************/

RCSortable BalancedTree::findPrev (void)

{
int retval;

errval = OK;
retval = getprev (head);
if (retval == RETURN_PARENT)
{
errval = NO_SUCH_BalancedTreeNode; // 'current' is pointing to first node in tree
return ((RCSortable)NOOBJECT);
}
else
return (*current->data);
}

/***************************************************************************/

int BalancedTree::getnext (BalancedTreeNode *currnode)

{
int side;
int retval;
int cresult;

cresult = compare (*currnode->data, *current->data);
if (cresult < 0) // node < data - go right
{
side = RIGHT;
retval = getnext (currnode->right);
}
else if (cresult > 0) // node > data - go left
{
side = LEFT;
retval = getnext (currnode->left);
}
else // this must be the place!
{
if (current->right != NULL)
{
current = current->right; // step to the right
while (current->left != NULL) // then walk the left edge of the
current = current->left; // subtree
return (RETURN_CURRENT);
}
else
return (RETURN_PARENT);
}

// unwind the recusion stack
if (retval == RETURN_PARENT)
{
if (side != RIGHT)
{
current = currnode;
return (RETURN_CURRENT);
}
else
return (retval);
}
return (0); // should never get here.
}

/***************************************************************************/

RCSortable BalancedTree::findNext (void) // locate the 'next' entry in
// the tree

{
int retval;

errval = OK;
retval = getnext (head);
if (retval == RETURN_PARENT)
{
errval = NO_SUCH_BalancedTreeNode; // 'current' is pointing to last node in tree
return ((RCSortable)NOOBJECT);
}
else
return (*current->data);
}

/***************************************************************************/

static const char *VERTBAR = "| ";
static const char *BLANK = " ";
static const char *RIGHT_DOWN = "--+ ";
static const char *LEFT_DOWN = "+------";

static unsigned char *mapptr;

/***************************************************************************/

static void print_bars (int level, int isright, Rostream os)

{
for (int i = 0; i < level; i++)
{
unsigned char bit = 0x80 >> (i % 8);
int ndx = i / 8;

if (i < level - 1)
{
if (mapptr[ndx] & bit)
os << VERTBAR;
else
os << BLANK;
}
else // i = level - 1
{
if (mapptr[ndx] & bit)
{
if (!isright)
{
os << LEFT_DOWN;
mapptr[ndx] ^= bit; // turn off the appropriate line
}
else
os << VERTBAR;
}
else
os << BLANK;
}
}
}

/***************************************************************************/

static void print_node (BalancedTreeNode *nptr, int level, int isright, Rostream os)

{
// print bars and leaders
print_bars (level, isright, os);

// print actual node
char balchar = (nptr->balance == BALANCED) ? 'B' :
((nptr->balance == LEFT) ? 'L' : 'R');

char *buff = new char [MAXBUFF];
nptr->data->printOn (os);
sprintf (buff, "(%c0)", balchar);
os << buff;
delete buff;

if (nptr->right != NULL) // add trailing right extension if appropriate
os << RIGHT_DOWN;
os << '\n';

// set appropriate bits
if (nptr->left != NULL)
{
unsigned char bit = 0x80 >> (level % 8);
int ndx = level / 8;
mapptr[ndx] |= bit;
}

if (nptr->right != NULL)
print_node (nptr->right, level + 1, 1, os);

if (nptr->left != NULL)
print_node (nptr->left, level + 1, 0, os);

if (!isright && nptr->left == NULL && nptr->right == NULL)
{
print_bars (level - 1, 1, os);
os << '\n';
}
}

/***************************************************************************/

int BalancedTree::print_tree (Rostream os) const

{
// figure out the maximum possible tree depth
BalancedTreeNode *nptr = head;

for (int maxdepth = 0; nptr != NULL; maxdepth++, nptr = nptr->right)
; // nothing, for loop does it all

maxdepth += 2; // max difference between left & right tree is 2

// allocate bit array used for printing verticle bars
mapptr = new unsigned char[(maxdepth / 8) + 1];
if (mapptr == NULL)
{
delete mapptr;
return (MEM_ALLOC_FAIL);
}

for (int i = 0; i < (maxdepth / 8) + 1; i++)
mapptr[i] = 0;

print_node (head, 0, 0, os);

delete mapptr;
return (OK);
}