Binary Search Tree template class in C ++ with C bst and now Red-Black version

[David]

Update: Update: please see this next link:

http://developers-heaven.net/forum/index.php/topic,2636.0.html


FREE homework help NOW available ...

You can contact me via:
http://sites.google.com/site/andeveryeyeshallseehim/home/he-comes
http://developers-heaven.net/forum/index.php/board,9.0.html

Here is a little introduction to coding for a binary search tree in C and C++

Enjoy


At first, let's look at some simpler C code re. a 'first go' at a Binary Search Tree ...
(Note: the previous error in the C version, of the  ... 'remove value from the BST' function, is now fixed, as of 2014-11-05)

Below, please find a little test program ... followed by the .h include file that is being tested' by this demo test program ...

Code: [Select]

/* test_binarySearchTree_c.h.c*/ /* 2014-11-02 */

 /* presuming ? negative numbers are stored in memory using 2's complement ? */
#define MIN_INT (1 << (sizeof(int)*8 - 1))
#define MAX_INT -(MIN_INT + 1)

#define startWithAryValues 1
#define RAN_ARY_SIZE 25

#include "binarySearchTree_c.h" /* includes <stdio.h>, <stdlib.h> */

#include <time.h> /* re. srand( time(0) ) */


const char* MENU = "\n 1.  Add to the tree"
"\n 2.  Find maxDepth of tree"
"\n 3.  printInOrder"
"\n 4.  printInPreOrder"
"\n 5.  printInPostOrder"
"\n 6.  Delete a node"
"\n 7.  Delete all"
"\n 8.  Delete a value"
"\n 9.  Find a value"
"\n 0.  Exit"
"\n\nEnter your choice: ";


void transfer( Node**, const int ary[], int size );

int getValidInt( const char* msg );

void testDeleteAllInOrderInserted()
{
    int ary[RAN_ARY_SIZE] = { 0 } ;
const int sizeAry = RAN_ARY_SIZE;

Node* root = NULL;
int i, size = 0;

srand( time(0) ) ;

for( i = 0; i < sizeAry; ++i )
{
        ary[i] = rand() % sizeAry;
        if( !find( root, ary[i]) ) ++size;
        insert( &root, ary[i] );
    }
       
    puts( "printInOrder ... " );
    printInOrder( root );
    printf("with size = %d", size );

    for( i = 0; i < sizeAry; ++i )
    {
        if( find( root, ary[i] ) ) --size;
        delVal( &root, ary[i] );
        printf( "\n\nAfter attempt at deleting %d, size is %d, "
                "getCount is %d, maxDepth is %d\n",
                ary[i], size, getCount(root), maxDepth(root) );
        printInOrder( root );
    }
   
    printf("\n\nPress 'Enter' to continue ..." );
    while( getchar() != '\n' ) ;
}


int main()
{
#if startWithAryValues
const int ary[] = { 30, 10, 40, 20, 50,
      11, 5, -5, 44, 66,
77, 33, 22, 99, -7 };
const int sizeAry = sizeof( ary ) / sizeof(int);
int i;
#endif

int choice, numGood, value;

Node* root = NULL;
int size = 0;

#if startWithAryValues
int loop = 3;

printf( "testDeleteAllInOrderInserted() ... \n" );
testDeleteAllInOrderInserted();
top:
size = sizeAry/loop;
transfer( &root, ary, size  );
printf( "\nThe maxDepth of tree from root is: %d", maxDepth( root ) );
printf( "\nprintInPreOrder: " );
printInPreOrder( root );
printf( "\nprintInOrder: " );
printInOrder( root );
printf( "\nThe size of tree is: %d\n", size );
printf( "The getCount from root is: %d\n", getCount( root ) );
for( i = 1; i <= size; ++i )
{
NodePos np;
initNodePos( &np );
getKthNode( root, &np, i );
printf( "\nThe maxDepth of tree from position %d is: %d", i,
  maxDepth( np.cur ) );
printf( "\nThe getCount from position %d is: %d", i,
getCount( np.cur ) );
}
fputs( "\n\nPress 'Enter' to continue ... ", stdout ); fflush( stdout );
while( getchar() != '\n' );

if( --loop > 0 ) goto top;

#endif

printf( "\n\nMIN_INT = %d, MAX_INT = %d\n\n", MIN_INT, MAX_INT );
do
{
printf( MENU ); fflush( stdout );
choice = -1;
scanf( "%d", &choice );
while( getchar() != '\n' );

switch( choice )
{
case 1:
printf("Enter a value: ");
numGood = scanf( "%d", &value );
while( getchar() != '\n' );
if( numGood == 1 )
{
insert( &root, value );
++size;
printf( "\nThe maxDepth of tree is: %d", maxDepth( root ) );
printf( "\nprintInOrder: " );
printInOrder( root );
printf( "\nThe size of tree is: %d\n", size );
}

else printf( "\nBad entry NOT inserted ...\n" );
break;
case 2:
printf( "\nThe maxDepth of tree is: %d", maxDepth( root ) );
break;
case 3:
printf( "\nprintInOrder: " );
printInOrder( root );
printf( "\ngetCount = %d", getCount( root ) );
printf( ", getCountInOrder = %d", getCountInOrder( root ) );
break;
case 4:
printf( "\nprintInPreOrder: " );
printInPreOrder( root );
printf( "\ngetCount = %d", getCount( root ) );
printf( ", getCountInOrder = %d", getCountInOrder( root ) );
break;
case 5:
printf( "\nprintInPostOrder: " );
printInPostOrder( root );
printf( "\ngetCount = %d", getCount( root ) );
printf( ", getCountInOrder = %d", getCountInOrder( root ) );
break;
case 6:
if( root )
{
del( &root );
printf( "\nOne node has been deleted ....\n" );
--size;
printf( "\nThe size of tree now is: %d",size );
}
else printf( "\nTree was empty ....\n" );
break;
case 7:
{
int n = 0;
while( root )
{
del( &root );
++n;
--size;
}
printf( "\nThe size of tree now is: %d",size  );
printf( "\n%d nodes were deleted ... \n", n );
break;
}
case 8:
{
int delValue = getValidInt( "Enter value to delete: " );
if( find( root, delValue ) )
{
                delVal( &root, delValue );
                printf( "\n%d was deleted ok ... ", delValue );
--size;
printf( "\nThe size of tree is: %d",size );
}
else
printf( "\n%d was NOT found, so NOT deleted...", delValue );

}
break;
case 9:
{
int findValue = getValidInt( "Enter value to find: " );
if( find( root, findValue ) )
printf( "\n%d was found ok ...", findValue );
else
printf( "\n%d was NOT found ...", findValue );
}
break;
case 0: /* exit on 0 ... */
{
int count = 0;
count = delAll( &root );
printf( "\n%d nodes were deleted ...\n", count );
/*
int n = 0;
while( root )
{
del( &root );
++n;
--size;
}
printf( "\nThe size of tree now is: %d",size  );
printf( "\n%d nodes were deleted ... \n", n );
break;
*/
}
break;
default:
printf( "\nInvalid choice ... \n" );
}
putchar( '\n' );
}
while( choice != 0 );

fputs( "\nPress 'Enter' to continue ... ", stdout ); fflush( stdout );
while( getchar() != '\n' );
return 0;
}

[David]

Now, the .h include file  binarySearchTree_c.h   needed above ...

Code: [Select]

/* binarySearchTree_c.h */ /* 2014-11-02 */

#ifndef BINARYSEARCHTREE_C_H
#define BINARYSEARCHTREE_C_H

#include <stdio.h>
#include <stdlib.h>

#ifndef dwMYASSERT
#define dwMYASSERT
void myAssert( int condition, const char* text )
{
    if( !condition )
    {
        fprintf( stderr, "%s\n", text );
        fputs( "Press 'Enter' to exit program ... ", stderr );
        getchar();
        exit(1);
    }
}
#endif

typedef struct myNode
{
int val;
struct myNode* left;
struct myNode* right;
} Node ;

Node* newNode( int nval )
{
Node* n = (Node*) malloc( sizeof( Node ) );
myAssert( (n != NULL), "Call to newNode failed to allocate new memory." );
n->val = nval;
n->left = NULL;
n->right = NULL;
return n;
}


typedef struct myNodePos
{
Node* cur;
int pos;
} NodePos ;

void initNodePos( NodePos* np )
{
np->cur = NULL;
np->pos = 0;
}

/* used to facilitate tracking of Node address in an inorder count in a BST */
void push( NodePos* np, Node* node )
{
np->cur = node;
++ np->pos;
}

/* when 'done' ... initialed struct np passed in
   holds inorder final node address and count */
void countInOrder( Node* tmp, NodePos* np )
{
if( tmp )
{
countInOrder( tmp->left, np );
np->cur = tmp;
++ np->pos;
countInOrder( tmp->right, np );
}
}

/* returns node total count for branch beginning at 'root' node  passed in */
int getCountInOrder( Node* tmp )
{
NodePos np;
initNodePos( &np );
countInOrder( tmp, &np );
return np.pos;
}

/* returns address of node in kth pos (in initialed struct np passed by ref)
   for branch beginning at 'root' node  passed in */
void getKthNode( Node* tmp, NodePos* np, int k )
{
if( tmp )
{
getKthNode( tmp->left, np, k );
if( np->pos < k )
{
np->cur = tmp;
++ np->pos;
}
getKthNode( tmp->right, np, k );
}
}

/* utility function to facilitate ... */
void showKthValue( Node* start, int k )
{
NodePos np;
 initNodePos( &np );
getKthNode( start, &np, k );
if( np.pos ) printf( "Position %d has value %d\n", np.pos, np.cur->val );
else printf( "Nothing at position %d\n", np.pos );
}

/* deletes all and reports count of nodes deleted ... */
int delAll( Node** cur )
{
if( ! *cur )
return 0;
else
{
/* go to end of each sub myNodes */
int count = delAll( &(*cur)->left );
int count2 = delAll( &(*cur)->right );

printf( "deleting %d\n", (*cur)->val );
free( *cur );
*cur = NULL;
return 1 + count + count2;
}
}

int getCount( Node* cur )
{
if( !cur )
return 0; /* count is set to 0 at termination NULL of each branch */
else
{
/* go to end of each submyNode */
int count1 = getCount( cur->left );
int count2 = getCount( cur->right );
return 1 + count1 + count2; /* unwind stack ... */
}
}


void insert( Node**, int );
void printInOrder( Node* );
void printInPreOrder( Node* );
void printInPostOrder( Node* );
void del( Node** );

void delVal( Node**, int val );
int maxDepth( Node* );
Node* find( Node*, int val );


void insert( Node** root, int v )
{
Node* h = *root;
if( h )
{
if( v < h->val )
{
        if( h->left == NULL )
            h->left = newNode( v );
        else
            insert( &h->left, v );
}
else if( v > h->val )
{
        if( h->right == NULL )
            h->right = newNode( v );
        else
            insert( &h->right, v );
}
else
{
printf( "Value %d already exists in myNodes... \n", v );
return;
}
}
else
{
*root = newNode( v ); /* update root ... */
}
}

void printInPreOrder( Node* tmp )
{
if( tmp )
{
printf( "%d  ",tmp->val );
printInPreOrder( tmp->left );
printInPreOrder( tmp->right );
}
}

void printInOrder( Node* tmp )
{
if( tmp )
{
printInOrder( tmp->left );
printf( "%d  ", tmp->val );
printInOrder( tmp->right );
}
}

void printInPostOrder( Node* tmp )
{
if( tmp )
{
printInPostOrder( tmp->left );
printInPostOrder( tmp->right );
printf( "%d  ",tmp->val );
}
}

void del( Node** root )
{
Node* h = *root;  /* get a working copy */

int val = 0;

if( !h )
{
printf( "\n\n Empty ... \n" );
return;
}

else if( h->right == NULL )
{
Node* tmp = h;
val = tmp->val;
*root = h->left; /* update root */
free( tmp );
}
else if( h->left == NULL )
{
Node* tmp = h;
val = tmp->val;
*root = h->right; /* update root */
free( tmp );
}
else
{
Node* tmp;
for( tmp = h->right; tmp->left; tmp = tmp->left ) ;

tmp->left = h->left;

tmp = h;
val = tmp->val;
*root = h->right; /* update root */
free( tmp );
}
printf( "Deleted val = %d\n", val );
}

#if 0
// deletes one node IF FOUND & updates size to indicate that node was deleted //
template< class Obj >
void BinarySearchTree< Obj >::delVal( Node< Obj >*& ptr, const Obj& val )
{
if( ptr ==  NULL )
        return;

if( val < ptr->data )
        delVal( ptr->left, val );
else if( val > ptr->data )
        delVal( ptr->right, val );
else
{
Node< Obj >* tmp;

if( ptr->left == NULL )
{
tmp = ptr->right;
delete ptr;
ptr = tmp;
--size;
return;
}
else if( ptr->right == NULL )
{
tmp = ptr->left;
delete ptr;
ptr = tmp;
--size;
return;
}
else /* both left and right exist ... */
{
Node< Obj >* prev = NULL;

tmp = ptr->right;
while( tmp->left != NULL )
{
        prev = tmp;
        tmp = tmp->left;
}
ptr->data = tmp->data;

if( prev != NULL )
    delVal( prev->left, prev->left->data );
else
    delVal( ptr->right, ptr->right->data );
}
}
}
#endif

/* if val found and deleted ... */
void delVal( Node** ptr, int val )
{
if( *ptr ==  NULL )
        return;   /* val not in BST */
       
    if( val < (*ptr)->val )
        delVal( &(*ptr)->left, val );
    else if( val > (*ptr)->val )
        delVal( &(*ptr)->right, val );
       

else /* both left and right exist ... */
{
        Node* tmp;

if( (*ptr)->left == NULL )
{
tmp = (*ptr)->right;
free (*ptr);
(*ptr) = tmp;
return;
}
else if( (*ptr)->right == NULL )
{
tmp = (*ptr)->left;
free (*ptr);
(*ptr) = tmp;
return;
}
    else
    {
    Node* prev = NULL;

    tmp = (*ptr)->right;

    while( tmp->left != NULL )
    {
            prev = tmp;
            tmp = tmp->left;
    }
    (*ptr)->val = tmp->val;

    if( prev != NULL )
        delVal( &prev->left, prev->left->val );
    else
        delVal( &(*ptr)->right, (*ptr)->right->val );
}
}
}


int maxDepth( Node* cur )
{
if( !cur )
return 0;
else
{
/* get depth of each submyNode */
int ld = maxDepth( cur->left );
int rd = maxDepth( cur->right );

/* return greater of two values + 1 */
return ( ld > rd ? ld +1 : rd +1 );
}
}

Node* find( Node* cur, int val )
{
while( cur != NULL )
{
if( val == cur->val )
return cur;
else if( val < cur->val )
cur = cur->left;
else
cur = cur->right;
}
return NULL; /* NOT found ... */
}

void transfer( Node** root, const int ary[], int size )
{
int i;
for( i = 0; i < size; ++i )
insert( root, ary[i] );
}


int getValidInt( const char* msg )
{
for( ; ; )
{
int tmp, numGood;
fputs( msg, stdout ); fflush( stdout );
numGood = scanf( "%d", &tmp );
while( getchar() != '\n' );
if( numGood == 1 ) return tmp;
/* else */
fputs( "Integers only here please ...\n", stdout );
}
}


#if 0 /* so will NOT compile this next block of code ... */
int delAll( Node** root )
{
/* only gives correct count if delAll is called just once in program ...
   to give correct count on repeated calls, need a global initialed to 0 */
static int count = 0;

Node* start = *root; /* get a working copy ... */
while( start )
{
Node* p = start;
Node* prev = NULL;
while( p->left ) /* go to the left most */
{
prev = p;
p = p->left;
}
if( p != start )
{
++count;
if( p->right ) delAll( &p->right );

printf( "deleting %d\n", p->val );
free( p );
prev->left = NULL;
}

p = start;
prev = NULL;
while( p->right ) /* go to the right most */
{
prev = p;
p = p->right;
}
if( p != start )
{
++ count;
if( p->left ) delAll( &p->left );
printf( "deleting %d\n", p->val );
free( p );
prev->right = NULL;
}
else
{
printf( "deleting %d\n", p->val );
free( p );
start = NULL;
++ count;
}
}
*root = NULL;
return count;
}
#endif


#endif

[David]

Ok ... this is a start to a C++ template class for a binary search tree type C++ container.

Again firstly, a test program that is followed by the .h file that holds the template class code.

Code: [Select]

// test_myBinarySearchTreeTemplateClass.cpp //  // this revision 2017-04-16 //

/*
    A simple implementation of a BinarySearchTree

    1.  void printInOrder( Node< Obj >* node) const;
        void printPreOrder( Node< Obj >* node) const;
        void printPostOrder( Node< Obj >* node) const;
        void printLevelOrder( Node< Obj >* node) const;

    Please see 'MENU' below to see more of what this 'test'
    program does ...

    Note: has copy ctor and overloaded assignment
          also using class ObjPos to minimize memory use

*/
#define show_dels 1 // to show deletes one by one whenever delOne is called //

#include "myBinarySearchTreeTemplateClass.h"

#include <ctime> // re. srand( time(0) );

const int RAN_ARY_SIZE = 25;

const char* MENU = "\n 1.  Print tree"
"\n 2.  Find maxDepth of tree"
"\n 3.  Find kth ('index[k-1]') node in tree"
"\n 4.  Delete in original insertion order"
"\n 5.  Add to the tree"
"\n 6.  Delete a value"
"\n 7.  Delete a node"
"\n 8.  Delete all"
"\n 9.  Find a value"
"\n 0.  Exit"
"\n\nEnter your choice: ";

const char* PMENU = "\n0 = inorder, 1 = preorder, 2= postorder, 3 = levelorder";


enum { inorder, preorder, postorder, levelorder };

void printAllOrders( const BinarySearchTree< int >& t, int k )
{
// 0 = inorder, 1 = preorder, 2= post order, 3 = level order
t.print(inorder);
t.print(preorder);
t.print(postorder);
t.print(levelorder );

cout << "\n\nt.get_size() " << t.get_size() << endl;
cout << "Min: " << t.findMin() << endl; // find min element
cout << "Max: " << t.findMax() << endl; // find max element
cout << "maxDepth from root is " << t.maxDepth() << endl;

cout << "Here we start with the 'index[" << k << "]' value in the tree ... \n";
Node< int >* kthPtr = t.findKth( k ); // find address of element k
if( kthPtr != 0 ) // get size of subtree starting from kth element on ...
{
cout << "Element at index[" << k << "] = " << kthPtr->get_data() << endl;
//cout << "Branch size: " << t.branchSize(kthPtr) << endl;
cout << "Branch count: " << t.branchCount(kthPtr) << endl;
cout << "maxDepth here is " << t.maxDepth(kthPtr) << endl << endl;
}
}

void pauseForEnter( const char* msg )
{
cout << msg << flush;
cin.get();
cin.sync();
}

void testDelete()
{
    cout << "Inside testDelete() ... \n";
BinarySearchTree < int > t; //creating an empty tree
BinarySearchTree < int > t3 = t;
t3.insert(30);
t3.insert(10);
t3.insert(40);
t3.insert(20);
t3.insert(50);

printAllOrders( t3, 1 );
t3 = t;
pauseForEnter( "Press 'Enter' to exit testDelete/continue ... " );
}

void testDeleteInOriginalInsertOrder()
{
    const int sizeAry = RAN_ARY_SIZE ;
    int ary[RAN_ARY_SIZE] = {0} ;

BinarySearchTree < int > t; //creating an empty tree

srand( time(0) ) ;

for( int i = 0; i < sizeAry; ++i )
    {
        ary[i] = rand() % sizeAry;
        t.insert( ary[i] );
        cout << ' ' << ary[i];
    }
    cout << "\nt.get_size() = " << t.get_size()
         << ", t.maxDepth() = " << t.maxDepth();

for( int i = 0; i < sizeAry; ++i )
    {
        cout  << "\n\nAttempting delete of " << ary[i] << endl;
        t.delVal( ary[i] );
        t.print(inorder);
        t.print(levelorder);
        cout << "\nt.get_size() = " << t.get_size()
             << ", t.maxDepth() = " << t.maxDepth();
    }
}

int getValidInt( const char* msg )
{
int tmp;
for( ; ; )
{
cout << msg << flush;
if( cin >> tmp )
{
cin.sync();
return tmp;
}
// else ...
cin.clear();
cin.sync();
cout << "Integers only here please ...\n";
}
}


int main()
{
  testDelete();

const int ary[] = { 30, 10, 40, 20, 50,
                        11, 5, -5, 44, 66,
                        77, 33, 22, 99, -7,
                        11, 77 };
const int sizeAry = sizeof( ary ) / sizeof(int);

BinarySearchTree < int > t; //creating an empty tree

for( int i = 0; i < 5; ++ i )
        t.insert( ary[i] );

cout << "\nShowing structure of tree t ...\n";
t.showStruture();
pauseForEnter( "Press 'Enter' to continue ... " );


for( int j = 0; j < 2; ++ j )
{
printAllOrders( t, 3 );
        pauseForEnter( "Press 'Enter' to continue ... " );

if( j == 0 )
for( int i = 5; i < sizeAry; ++i )
t.insert( ary[i] );
}


// more testing ...

int k = 3;

for( int loop = 0; loop < 3; ++ loop )
{
        for( int i = 0; i < 3; ++i )
{
t.delOne();
cout << "t.get_size() " << t.get_size() << endl;
}

printAllOrders( t, k );
++k;
        pauseForEnter( "Press 'Enter' to continue ... " );
}


    cout << "\n\nNow using a copy ... \n\n";
    pauseForEnter( "Press 'Enter' to continue ... " );


    BinarySearchTree < int > t2 = t; // creating a copy
printAllOrders( t2, 5 );

    k = 1;

for( int loop = 0; loop < 2; ++ loop )
{
for( int i = 0; i < 2; ++i )
{
t2.delOne();
cout << "t2.get_size() " << t2.get_size() << endl;
}

printAllOrders( t2, k );
++k;
pauseForEnter( "\nPress 'Enter' to continue ... " );
}

t2.clear();
cout << endl;
t.clear();



Node< int >* kthPtr;
int pchoice, value, delValue;
bool more = true;
while( more )
{
//t.print(inorder);
//cout << endl;
switch( getValidInt( MENU ) )
{
case 1:
cout << PMENU << flush;
pchoice = getValidInt( "\nYour printout choice: " );
if( pchoice >= 0 && pchoice <= 3 ) t.print( pchoice );
else cout << "\nValid choices in range 0..3 only ...\n";
break;
case 2:
cout << "\nThe maxDepth of tree is: " << t.maxDepth();
break;
case 3:
{
int k = getValidInt( "Enter kth element to find: " );
Node< int >* kthPtr = t.findKth( k ); // find address of element k
if( kthPtr != NULL ) // get size of subtree starting from kth element on ...
{
cout << "\nElement " << k << " = " << kthPtr->get_data() << endl;
//cout << "Branch size: " << t.branchSize(kthPtr) << endl;
cout << "Branch count: " << t.branchCount(kthPtr) << endl;
cout << "maxDepth here is " << t.maxDepth(kthPtr) << endl;
}
else
{
    if( k>0 ) cout << "\nThe element " << k << " is beyond size of: " << t.get_size() << endl;
    else cout << "\nOnly values > 0 are valid here ...\n";
            }
}
break;
case 4:
             testDeleteInOriginalInsertOrder();
break;
case 5: // add a value to tree //
value = getValidInt( "Enter a value: " );
t.insert( value );

kthPtr = t.findKth( 1 ); // find address of element k
if( kthPtr != NULL ) // get size of subtree starting from kth element on ...
{
cout << "\nElement " << k << " = " << kthPtr->get_data() << endl;
//cout << "Branch size: " << t.branchSize(kthPtr) << endl;
cout << "Branch count: " << t.branchCount(kthPtr) << endl;
cout << "maxDepth here is " << t.maxDepth(kthPtr) << endl << endl;
}
t.print(inorder);
cout << "\nThe maxDepth of tree is: " << t.maxDepth();
cout << "\nThe size of tree is: " << t.get_size() << endl;
break;
case 6:
delValue = getValidInt( "Enter value to delete: " );
if( t.delVal( delValue ))
{
cout << '\n' << delValue << " deleted ok.";
cout << "\nThe size of tree is: " << t.get_size();
}
else
cout << '\n' << delValue << " NOT found ... NOT deleted.";
break;
case 7:
if( t.get_size() )
{
t.delOne();
kthPtr = t.findKth( 3 ); // find address of element k
if( kthPtr != 0 ) // get size of subtree starting from kth element on ...
{
cout << "\nElement " << k << " = " << kthPtr->get_data() << endl;
//cout << "Branch size: " << t.branchSize(kthPtr) << endl;
cout << "Branch count: " << t.branchCount(kthPtr) << endl;
cout << "maxDepth here is " << t.maxDepth(kthPtr) << endl << endl;
}
t.print(inorder);
cout << "\nThe maxDepth of tree is: " << t.maxDepth();
cout << "\nThe size of tree is: " << t.get_size() << endl;
}
else cout << "\nTree was empty ....\n";
break;
case 8:
t.clear();
cout << "\nThe size of tree now is: " << t.get_size();
break;
case 9:
{
int findValue = getValidInt( "Enter value to find: " );
if( t.find( findValue ))
cout << '\n' << findValue << " was found ok.";
else
cout << '\n' << findValue << " was NOT found.";
}
break;
case 0: /* exit on 0 ... */
{
t.clear();
cout << "\nThe size of tree now is: " << t.get_size() << endl;
more = false;
}
break;
default:
cout << "\nInvalid choice ... \n";
} // end of switch( ... )
cout << endl;
} // end of while( more ) ...

return 0;

}


[David]

And now the include.h file needed above ...

Code: [Select]

// myBinarySearchTreeTemplateClass.h //   // this revision 2017-04-16 //

#ifndef myBinarySearchTreeTemplateClass_H
#define myBinarySearchTreeTemplateClass_H

#ifndef show_dels
#define show_dels 0 // define as 1 (in main) to show deletes one by one //
#endif

#include <iostream>
#include <string>
#include <queue>

#include <cstdlib> // re. exit //

using namespace std;

// simple class to represent a binary search tree node

template< class Obj > class BinarySearchTree; // forward declaration ... //

template < class Obj >
class Node
{
private:
    friend class BinarySearchTree< Obj >;
Obj data;
Node< Obj > *left, *right;
public:
Node() : left(NULL), right(NULL) {}
Node( const Obj& data ) : data(data), left(NULL), right(NULL) {}
    Obj get_data() const { return data; }
} ;

template < class Obj > // hold an Obj & position 1..n of obj's in tree //
class ObjPos
{
public:
ObjPos() : curObj(0), pos(0) {}
ObjPos( const Obj& n, int p ) : curObj(n), pos(p) {}

void push( const Obj& n )
{
curObj = n;
++pos;
}
int size() const { return pos; }
Obj back() { return curObj; }
private:
Obj curObj;
int pos;
} ;


template< class Obj >
class BinarySearchTree
{
public:
BinarySearchTree() : size(0), root(NULL) {}
~BinarySearchTree() { clear(); }

void clear() ;

BinarySearchTree( const BinarySearchTree& ) ; // copy ctor //
BinarySearchTree& operator = ( const BinarySearchTree& ) ; // overloaded = //

void insert( const Obj& ) ; // insert a node in the tree //

const Obj& findMin() const;
const Obj& findMax() const;


Node< Obj >* find( const Obj& val ) const
{
return find( root, val );
}

int branchCount( Node< Obj >* cur ) const ;

// using here 'minimal memory' via class ObjPos (instead of class queue) //
void countInOrder( Node< Obj >* node, int count,
   ObjPos< Node< Obj >* >& q ) const ;

// find the kth element in the tree (uses above function and class ObjPos) //
Node< Obj >* findKth( int k ) const ;

//void countInOrder( Node< Obj >* node, int& count ) const ;

// get number of nodes in any given branch
//int branchSize( Node< Obj >* startNode ) const ;


// print all the elements starting with the root based on the given type
// 0 = inorder, 1 = preorder, 2= post order, 3 = level order
void print( int type ) const ;

void delOne() ; // deletes one node ...

// delete the tree from a given root
// void deleteAll( Node< Obj >*& node ) ;
// now using delAll instead of deleteAll ... //

int maxDepth( Node< Obj >* node ) const ;
int maxDepth() const ;

int get_size() const { return size; }
int count_size() const { return branchCount( root ); }

bool delVal( const Obj& val ) ;

    void showStruture() const
    {
        showStructure_r( root, 0 );
    }

private:
int size; // the number of nodes in the tree
Node< Obj >* root; // root of the tree

// insert a node given a pointer to a tree node
void insert_r( Node<Obj>*& node, const Obj& data ) ;

// updates size if val found and deleted ... else size not changed //
void delVal( Node< Obj >*& ptr, const Obj& val ) ;

    // deletes all and reports count of nodes deleted
int delAll( Node< Obj >*& cur ) ;

void showStructure_r( Node< Obj >* n, int level ) const ;

void printInOrder( Node< Obj >* node ) const ;
void printPreOrder( Node< Obj >* node ) const ;
void printPostOrder( Node< Obj >* node ) const ;
void printLevelOrder( Node< Obj >* node ) const ;

// A NON-recursive find ... //
Node< Obj >* find( Node< Obj >* cur, const Obj& val ) const
{
while( cur != NULL )
{
if( val == cur->data )
return cur;
else if( val < cur->data )
cur = cur->left;
else
cur = cur->right;
}
return NULL; /* NOT found ... */
}
} ;



//////////////////////////////  DEFINITIONS ////////////////////////////////////

// copy ctor ...
template< class Obj >
BinarySearchTree< Obj >::BinarySearchTree( const BinarySearchTree& bt )
{
root = NULL;
size = 0;
if( bt.size )
{
Node< Obj >* tmp;
queue< Node< Obj >*  >  q;
q.push( bt.root );
while( !q.empty() )
{
tmp = q.front();
insert( tmp->data );
if( tmp->left != NULL ) q.push( tmp->left );
if( tmp->right != NULL ) q.push( tmp->right );
q.pop();
}
}
}

// overloaded assignment ...
template< class Obj >
BinarySearchTree< Obj >& BinarySearchTree< Obj >::
    operator = ( const BinarySearchTree& bt )
{
if( this != &bt )
{
        clear();
        if( bt.size )
        {
Node< Obj >* tmp;
queue< Node< Obj >*  >  q;
q.push( bt.root );
while( !q.empty() )
{
tmp = q.front();
insert( tmp-> data );
if( tmp->left != NULL ) q.push( tmp->left );
if( tmp->right != NULL ) q.push( tmp->right );
q.pop();
}
}
}
return *this;
}

template< class Obj >
const Obj& BinarySearchTree< Obj >::findMin() const
{
if( root )
{
Node< Obj > * p = root;

while( p->left != NULL ) // go to the left most
p = p->left;

return p->data;
}
else
{
cout << "\nCan't access an empty BinarySearchTree ... "
"Press 'Enter' to exit ... " << flush;
string line;
getline( cin, line );
exit(0);
}
}

template< class Obj >
const Obj& BinarySearchTree< Obj >::findMax() const
{
if( root )
{
Node< Obj >* p = root;

while( p->right != NULL ) // go to the right most
p = p->right;

return p->data;
}
else
{
cout << "\nCan't access an empty BinarySearchTree ... "
"Press 'Enter' to exit ... " << flush;
string line;
getline( cin, line );
exit(0);
}
}

// returns the count of all the nodes in a branch beginning with node passed in
template< class Obj >
int BinarySearchTree< Obj >::branchCount( Node< Obj >* cur ) const
{
if( !cur )
return 0; /* count is set to 0 at termination NULL of each branch */
else
{
/* go to end of each subtree */
int count1 = branchCount( cur->left );
int count2 = branchCount( cur->right );
return 1 + count1 + count2; /* unwind stack ... */
}
}

// deletes all of branch pass in and reports count of nodes deleted //
template< class Obj >
int BinarySearchTree< Obj >::delAll( Node< Obj >*& cur )
{
if( !cur )
return 0;
else
{
/* go to end of each subtree */
int count = delAll( cur->left );
int count2 = delAll( cur->right );
#if show_dels
cout << "Inside delAll() ... deleting " << cur->data << endl;
#endif
delete cur;
cur = NULL;
return  1 + count + count2;
}
}

template< class Obj >
void BinarySearchTree< Obj >::clear()
{
    cout << "clear() was called ... \n";
if( size )
{
int count = delAll( root ); // also sets, by ref, root to NULL when all done //
#if show_dels
if( size == count )
{
cout << "   All " << count << " nodes deleted.\n";
size = 0;
}
else
{
cout << "   Only " << count << " nodes deleted. \n" << size-count
                 << " nodes NOT deleted = MEMORY LEAK!\n"
                 << "Press 'Enter' to continue/exit ... " << flush;;
string line;
getline( cin, line );
exit(0);
}
}
else
cout << "  Tree was already empty.\n";
#endif
#if !show_dels
}
#endif
}

// using here 'minimal memory' via class ObjPos (instead of class queue) //
// used by findKth ... below ...
template< class Obj >
void BinarySearchTree< Obj >::
countInOrder( Node< Obj >* node, int count, ObjPos< Node< Obj >* >& q ) const
{
if( node )
{
countInOrder( node->left, count, q );
if( q.size() < count ) q.push( node );
countInOrder( node->right, count, q );
}
}

// find the kth element in the tree (uses above function and class ObjPos) //
template< class Obj >
Node< Obj >* BinarySearchTree< Obj >::findKth( int k ) const
{
// invalid ...
if( k < 1 || k > size || root == NULL )
return NULL;


if( size == 1 )
return root;

ObjPos< Node< Obj >* > q; // calls default ctor to give initial values //
countInOrder( root, k, q );
// cout << "\nq.size() = " << q.size() << endl;
return q.back(); // returns a copy of pointer //
}

/*
template< class Obj >
void BinarySearchTree< Obj >::countInOrder( Node< Obj >* node, int& count ) const
{
if( node )
{
countInOrder( node->left, count );
++count;
countInOrder(node->right, count );
}
}

// get number of nodes in any given branch
template< class Obj >
int BinarySearchTree< Obj >::branchSize( Node< Obj >* startNode ) const
{
int count = 0;
countInOrder( startNode, count );
return count;
}
*/
template< class Obj >
void BinarySearchTree< Obj >::insert( const Obj& data )
{
    insert_r( root, data ); // calls the private resursive method below ... //
    ++ size;
}

// recursive method //
// insert a node to the tree
template< class Obj >
void BinarySearchTree< Obj >::insert_r( Node< Obj >*& node, const Obj& data )
{
    // Note that root is passed by reference since its value
    // can change in the case where the tree is empty.
    if( ! node )
    {
        // The tree is empty. Set root to point to a new node containing
        // the new data. This becomes the only node in the tree.

        node = new Node< Obj >( data );

        // NOTE: The left and right subtrees of root
        // are automatically set to 0 by the constructor.
        // This is important! !!! //

        return;
    }
    if( data < node->data )
        insert_r( node->left, data );
    else
        insert_r( node->right, data );
}

/*
// insert a node to the tree
template< class Obj >
void BinarySearchTree< Obj >::insert( const Obj& data )
{
// create a node with the given data
if( root != NULL )
insert_r( root, data );
else
{
root = new Node<Obj>( data );
++size; // increment the list counter
}
}

// insert a node given a pointer to a tree node
template< class Obj >
void BinarySearchTree< Obj >::insert_r( Node<Obj> *node, const Obj& data )
{
if( data < node->data )
{
if( node->left != NULL )
insert_r( node->left, data ); // insert to the left
else
{
node->left = new Node<Obj>( data );
++size; // increment list counter
}
}
else if( node->data < data ) //  data > node->data
{
if( node->right != NULL )
insert_r( node->right, data ); // insert to the right
else
{
node->right = new Node<Obj>( data );
++size; //i ncrement list counter
}
}
// else  // duplication
}
*/

// print all the elements starting with the root based on the given type
// 0 = inorder, 1 = preorder, 2= post order, 3 = level order
template< class Obj >
void BinarySearchTree< Obj >::print( int type ) const
{
if( root != NULL )
{
switch( type )
{
case 0: cout << "\nprintInOrder: "; printInOrder( root ); break;
case 1: cout << "\nprintPreOrder: "; printPreOrder( root ); break;
case 2: cout << "\nprintPostOrder: "; printPostOrder( root ); break;
case 3: cout << "\nprintLevelOrder: "; printLevelOrder( root );
}
}
}

template< class Obj >
void BinarySearchTree< Obj >::printInOrder( Node< Obj >* node ) const
{
if( !node ) return;

printInOrder( node->left );
cout << " " << node->data;
printInOrder( node->right );
}

template< class Obj >
void BinarySearchTree< Obj >::printPreOrder( Node< Obj >* node ) const
{
if( !node ) return;

cout << " " << node -> data;
printPreOrder( node->left );
printPreOrder( node->right );
}

template< class Obj >
void BinarySearchTree< Obj >::printPostOrder( Node< Obj >* node ) const
{
if( !node ) return;

printPostOrder( node->left );
printPostOrder (node->right );
cout << " " << node -> data;
}

template< class Obj >
void BinarySearchTree< Obj >::printLevelOrder( Node< Obj >* node ) const
{
Node< Obj >* tmp;
queue< Node< Obj >*  > q;
q.push( node );
while( !q.empty() )
{
tmp = q.front();
cout << " " << tmp-> data;
if( tmp->left ) q.push( tmp->left );
if( tmp->right ) q.push( tmp->right );
q.pop();
}
}

// deletes one node and updates size to indicate that node was deleted //
template< class Obj >
void BinarySearchTree< Obj >::delOne()
{
#if show_dels
Obj val;
#endif
Node< Obj >* h = root;  /* get a working copy */

if( !h )
{
cout << "\n\n Empty ... \n";
return;
}

else if( h->right == NULL )
{
Node< Obj >* tmp = h;
#if show_dels
val = tmp->data;
#endif
root = h->left; /* update root */
delete tmp;
}
else if( h->left == NULL )
{
Node< Obj >* tmp = h;
#if show_dels
val = tmp->data;
#endif
root = h->right; /* update root */
delete tmp;
}
else
{
Node< Obj >* tmp;
for( tmp = h->right; tmp->left; tmp = tmp->left ) ;

tmp->left = h->left;

tmp = h;
#if show_dels
val = tmp->data;
#endif
root = h->right; /* update root */
delete tmp;
}

--size;

#if show_dels
cout << "Inside delOne() ... Deleted " << val
<< "  Press 'Enter to continue ... " << flush;
cin.get();
cin.sync();
#endif
}

template< class Obj >
int BinarySearchTree< Obj >::maxDepth( Node< Obj >* node ) const
{
if( !node )
return 0;
else
{
/* get depth of each subtree */
int ld = maxDepth( node->left );
int rd = maxDepth( node->right );

/* return greater of two values + 1 */
return ( ld > rd ? ld +1 : rd +1 );
}
}
// uses function above //
template< class Obj >
int BinarySearchTree< Obj >::maxDepth() const
{
return maxDepth( root );
}

// deletes one node IF FOUND & updates size to indicate that node was deleted //
template< class Obj >
void BinarySearchTree< Obj >::delVal( Node< Obj >*& ptr, const Obj& val )
{
if( ptr ==  NULL )
        return;

if( val < ptr->data )
        delVal( ptr->left, val );
else if( val > ptr->data )
        delVal( ptr->right, val );
else
{
Node< Obj >* tmp;

if( ptr->left == NULL )
{
tmp = ptr->right;
delete ptr;
ptr = tmp;
--size;
return;
}
else if( ptr->right == NULL )
{
tmp = ptr->left;
delete ptr;
ptr = tmp;
--size;
return;
}
else /* both left and right exist ... */
{
Node< Obj >* prev = NULL;

tmp = ptr->right;
while( tmp->left != NULL )
{
        prev = tmp;
        tmp = tmp->left;
}
ptr->data = tmp->data;

if( prev != NULL )
    delVal( prev->left, prev->left->data );
else
    delVal( ptr->right, ptr->right->data );
}
}
}

template< class Obj >
bool BinarySearchTree< Obj >::delVal( const Obj& val )
{
int oldSize  = size;
delVal( root, val );
return oldSize != size;
}

/*
// delete the tree from a given root
template< class Obj >
void BinarySearchTree< Obj >::deleteAll( Node< Obj >*& node )
{
while( node ) delOne(); // keep deleting till done (and node == NULL)
}
*/


template< class Obj >
void BinarySearchTree< Obj >::showStructure_r( Node< Obj >* cur, int level ) const
{
    if( !cur ) return;

    cout << "Level: " << level << ",  Data: "<< cur->data << endl;

    showStructure_r( cur->left, level + 1 );
    showStructure_r( cur->right, level + 1 );
}

#endif

[David]

Also ... (re. binary search trees ... and ... especially *balanced* RED-BLACK binary search trees ... )

I found this site that looks very helpful ...

with extensively explained code examples (put into the public domain) for serious help to student C and C++ coders ...


http://eternallyconfuzzled.com/jsw_home.aspx


Below, please find some C binary search tree example code that I found there ... but all put together here, into one working program ...

The code here is my slightly revised version ... and has several added comments ... to attempt to help the reader see just what/why the code is  ... as it is ...


Firstly ... a plain (unbalanced) BST with example code for several recursive and non-recursive BST functions ...

Enjoy

The short test program next is followed by the .h file that it includes ...

Code: [Select]

/* test_binSTree.h.c */  /*  2014-11-03 */


#define showdeletes 1 /* set to 0 to turn off ... */

#define ARY_SIZE 22

#include "binSTree.h"
/*
#include <stdio.h>
#include <stdlib.h>
*/
#include <time.h> /* re. srand( time(0) ); */



int main()
{
    int i, ary[ARY_SIZE];
    Tree set;
   
    initTree( &set );
   
    srand( time(0) );
    puts( "Insert random value then printInLevelOrder... (size, height)" );
    for( i = 0; i < ARY_SIZE; ++i )
    {
        ary[i] = rand() % ARY_SIZE;
        if( insertValue_nr( &set, ary[i] )) /* test non-recursive insert */
        {
            printInLevelOrder( &set );
            printf( " (%d", set.size );
            printf( ", %d)\n", height( &set ) );
        }
    }

    puts( "\nprintInPostOrder:" );
    printInPostOrder( &set ); printf( " size = %d\n", set.size ) ;
    puts( "\nprintInPreOrder:" );
    printInPreOrder( &set ); printf( " size = %d\n", set.size ) ;
    puts( "\nprintInOrder:" );
    printInOrder( &set ); printf( " size = %d\n", set.size ) ;

    puts( "\nPrinting structure:" );
    structure ( &set );
    /*
    destroyTree_nr( & set );
    printf( "After destroyTree_nr ... size = %d\n", set.size );
    */
    for( i = 0; i < ARY_SIZE; ++i )
    {
        removeValue_nr( &set, ary[i] );
        printf( "\nprintInLevelOrder AFTER trying to remove %d:\n",
                ary[i] );
        printInLevelOrder( &set );
        printf( " (%d", set.size );
        printf( ", %d)\n", height( &set ) );
    }
   
   
    printf( "\nPress 'Enter' to continue/exit ... " ); fflush(stdout);
    while( getchar() != '\n' );
    return 0;
}

[David]

Now here the binSTree.h file needed by the test program above ...

Code: [Select]

/* binSTree.h */  /* 2014-11-03 */

#ifndef BINSTREE_H
#define BINSTREE_H

#include <stdio.h>
#include <stdlib.h>


/*
  Edited from: "Eternally Confuzzled - Binary Search Trees I.htm"
*/

#ifndef showdeletes
#define showdeletes 0 /* define in main and set to 1 to show deletes */
#endif

typedef struct myNode
{
  int data;
  struct myNode* link[2]; /* Note: index 0 => left, 1 => right */
} Node ;

typedef struct myTree
{
  Node* root;
  unsigned size;
} Tree ;

void initTree( Tree* tr )
{
   tr->root = NULL;
   tr->size = 0;
}


Node* newNode( int val )
{
    Node* n = malloc( sizeof(Node) );
    n->data = val;
    n->link[0] = n->link[1] = NULL;
    return n;
}

unsigned height_r( Node* cur )
{
if( !cur )
return 0;
else
{
/* get depth of each sub-tree ... */
unsigned ld = height_r( cur->link[0] );
unsigned rd = height_r( cur->link[1] );

/* return greater of two values + 1 */
return ( ld > rd ? ld +1 : rd +1 );
}
}
/* uses function above */
unsigned height( Tree* tr)
{
return height_r( tr->root );
}

/* Note: the '_r' indicates that this is a recursive function ... */
void destroyTree_r ( Node* root )
{
  if ( root )
  {
    /* Note: using a 'printInPostorder' traversal ...
      so each 'root' is a 'leaf' */
    destroyTree_r ( root->link[0] );
    destroyTree_r ( root->link[1] );
#if showdeletes
    printf( "destroying %d\n", root->data );
#endif
    free ( root );
  }
}
void destroyTree ( Tree* tr )
{
  destroyTree_r ( tr->root );
  initTree( tr );
}

void destroyTree_nr ( Tree* tr )
{
  Node* it = tr->root;
  Node* save;

  while ( it )
  {
    if ( it->link[0] )
    {
      /* Right rotation */
      save = it->link[0];
      it->link[0] = save->link[1];
      save->link[1] = it;
    }
    else
    {
      save = it->link[1];
#if showdeletes
      printf( "after destroying %3d", it->data );
#endif
      free ( it );
      -- tr->size;
#if showdeletes
      printf( ", size = %d\n", tr->size );
#endif
    }

    it = save;
  }
  initTree( tr );
}

int findValue_r ( Node* root, int data )
{
  if ( !root )
    return 0;
  else if ( root->data == data )
    return 1;
  else
  {
    int dir = root->data < data;
    return findValue_r ( root->link[dir], data );
  }
}
int findValue ( Tree* tree, int data )
{
  return findValue_r ( tree->root, data );
}

/* non-recursive ... */
int findValue_nr ( Tree* tree, int data )
{
  Node* it = tree->root;

  while ( it )
  {
    if ( it->data == data )
      return 1;
    else
    {
      int dir = it->data < data;
      it = it->link[dir];
    }
  }
  /* if reach here ... not found ... */
  return 0;
}

Node* insertValue_r ( Node* root, int data, int* wasInserted )
{
  if ( !root )
  {
    root = newNode ( data );
    if( root ) *wasInserted = 1;
  }
  else if ( root->data == data )
    return root;
  else
  {
    int dir = root->data < data;
    root->link[dir] = insertValue_r ( root->link[dir], data, wasInserted );
  }

  return root;
}

int insertValue ( Tree* tr, int data )
{
  int wasInserted = 0;
  tr->root = insertValue_r ( tr->root, data, &wasInserted );
  if( wasInserted ) ++ tr->size;
  return tr->size;
}

/* non-recursive */
int insertValue_nr ( Tree* tr, int data )
{
  if ( tr->root )
  {
    Node* it = tr->root;
    int dir;

    for ( ; ; )
    {
      dir = it->data < data;

      if ( it->data == data )
        return 0;
      else if ( it->link[dir] == NULL )
        break;

      it = it->link[dir];
    }

    it->link[dir] = newNode ( data );
    if( it->link[dir] ) ++ tr->size;
  }
  else
  {
    tr->root = newNode ( data );
    if( tr->root ) ++ tr->size;
  }

  return tr->size;
}

/* non-recursive */
int removeValue_nr ( Tree* tr, int data )
{
  /* using trick to insertValue 'a guard root' ABOVE the original root ... */
  if ( tr->root != NULL )
  {
    Node head = {0};
    Node* it = &head; /* address of new dummy root,
                        to ALWAYS have the val to be deleted
                        as BELOW 'the new dummy root node' */
    Node* p, *f = NULL;
    int dir = 1; /* go to 'right' the first time ... */

    it->link[1] = tr->root; /* links new dummy root to tree */

    while ( it->link[dir] != NULL ) /* loop NOT entered if root == NULL */
    {
      p = it;
      it = it->link[dir]; /* first time, go to 'right' ... */
     
      dir = it->data <= data;

      if ( it->data == data )
        f = it;
    }

    /* if found ... */
    if ( f ) /* NOTE! handles case if tree->root was NULL, f will also be NULL */
    {
      f->data = it->data; /* copy next vale up and over data value ... */

      /* NOW can 'cut out' node 'it' ... */
      p->link[p->link[1] == it] = it->link[it->link[0] == NULL];
      /*
        if (p->link[1] == it) == 0 ... move from prev was to left
        if (it->link[0] == NULL) == 1 ... link is to 'right'
      */
      free ( it );
      -- tr->size;
    }

    /* recall head.link[1] holds the address of the ACTUAL root */
    tr->root = head.link[1]; /* update root address ... */
  }

  return tr->size;
}


Node* removeValue_r ( Node* root, int data, int* wasRemoved )
{
  if ( root )
  {
    int dir;

    if ( root->data == data )
    {
      if ( root->link[0] && root->link[1] )
      {
        Node* succ = root->link[1];

        while ( succ->link[0] )
          succ = succ->link[0];

        data = succ->data;
        root->data = data;
      }
      else
      {
        Node* save = root;

        root = root->link[root->link[0] == NULL];

        free ( save );
        *wasRemoved = 1;
        return root;
      }
    }

    dir = root->data <= data;
    root->link[dir] = removeValue_r ( root->link[dir], data, wasRemoved );
  }

  return root;
}

int removeValue ( Tree* tr, int data )
{
  int wasRemoved = 0;
  tr->root = removeValue_r ( tr->root, data, &wasRemoved );
  if( wasRemoved ) --tr->size;
  return tr->size;
}


void printInPreOrder_r ( Node* root )
{
  if ( root )
  {
    printf ( "%3d ", root->data );
    printInPreOrder_r ( root->link[0] );
    printInPreOrder_r ( root->link[1] );
  }
}
void printInPreOrder ( Tree* tree )
{
  printInPreOrder_r ( tree->root );
}

void printInOrder_r ( Node* root )
{
  if ( root )
  {
    printInOrder_r ( root->link[0] );
    printf ( "%3d ", root->data );
    printInOrder_r ( root->link[1] );
  }
}
void printInOrder ( Tree* tree )
{
  printInOrder_r ( tree->root );
}

void printInPostOrder_r ( Node* root )
{
  if ( root )
  {
    printInPostOrder_r ( root->link[0] );
    printInPostOrder_r ( root->link[1] );
    printf ( "%3d ", root->data );
  }
}
void printInPostOrder ( Tree* tree )
{
  printInPostOrder_r ( tree->root );
}

/* shows tree rotated 90 degress counter-clockwise ... */
void structure_r ( Node* root, int level )
{
  int i;

  if ( root == NULL )
  {
    for ( i = 0; i < level; i++ )
      printf( "    " ); /* putchar ( '\t' ); */
    printf( "   ~\n" ); /* puts ( "~" ); */
  }
  else
  {
    structure_r ( root->link[1], level + 1 );

    for ( i = 0; i < level; i++ )
      printf( "    " ); /* putchar ( '\t' ); */
    printf( " %3d\n", root->data ); /* printf ( "%d\n", root->data ); */

    structure_r ( root->link[0], level + 1 );
  }
}

void structure ( Tree* tree )
{
  structure_r ( tree->root, 0 );
}

void printInLevelOrder ( Tree* tr )
{
    if ( !tr->root ) return;
    else
    {
        Node* it = tr->root;
        Node** q = malloc( sizeof( Node* ) * tr->size );
        if( q )
        {
            int front = 0, back = 0;

            q[front++] = it; /* insert root at front of q... */

            while ( front != back )
            {
                it = q[back++]; /* on first pass, gets root here ... */

                printf ( "%3d ", it->data );
               
                /* adds Node to q... if exists ... */
                if ( it->link[0] ) q[front++] = it->link[0];
                if ( it->link[1] ) q[front++] = it->link[1];
            }
            free( q );
        }
    }
}

/* non-recursive ... */
void printInOrder_nr ( Tree* tr )
{
    Node* it = tr->root;
    Node** up = malloc( sizeof( Node* ) * tr->size );
    if( up )
    {
        int top = 0;

        while ( it )
        {
            while ( it )
            {
                if ( it->link[1] )
                   up[top++] = it->link[1];

                up[top++] = it;
                it = it->link[0];
            }

            it = up[--top];

            while ( top != 0 && !it->link[1] )
            {
                printf ( "%3d ", it->data );
                it = up[--top];
            }

            printf ( "%3d ", it->data );

            if ( top == 0 )
               break;

            it = up[--top];
        }
       
        free( up );
    }
}

#endif




[David]

Now the C test code for a Red-Black binary search tree (Insert, Delete, etc... code is demo'd here ...)


Note: needs to include files Clist.h and Clist_func's.h available here

Clist.h
http://developers-heaven.net/forum/index.php/topic,2582.msg2877.html#msg2877

Clist_func's.h
http://developers-heaven.net/forum/index.php/topic,2582.msg2883.html#msg2883

(these are used for the list used as a queue in the print level code)

Code: [Select]

/* test_rbt.h.c */  /* 2014-11-06 */

#include "rbt.h" /* includes: <stdio.h>, <stdlib.h> */

#define MAX_TEST_SIZE 28

/*
    NEED the following defn's and include ...
    before can include Clist.h and then Clist_func's.h ...
*/

/* A 'queue-Clist' is used re. 'printInLevelOrder' ... */
typedef struct myList
{
    Node* address;
    struct myList* next;
   
} List ;

typedef List* pList;

void clearLrec( pList p )
{
    /* do NOT want to delete Node pointers here ...
    since here using alias */
}

#ifndef dwMYASSERT
#define dwMYASSERT
void myAssert( int condition, const char* text )
{
    if( !condition )
    {
        fprintf(stderr, "%s\n", text );
        fputs( "Press 'Enter' to exit program ... ", stderr );
        getchar();
        exit(1);
    }
}
#endif


#include <string.h> /* re. memcpy... */

/* NOW can ... include ... */
#include "Clist.h"
#include "Clist_func's.h" /* re. erase... */

void printLevelOrder( Node* root )
{
/*
    queue< Node< Obj >*  > q;
q.push( node );
while( !q.empty() )
{
Node< Obj >* tmp = q.front();
cout << " " << tmp-> data;
if( tmp->left != NULL ) q.push( tmp->left );
if( tmp->right != NULL ) q.push( tmp->right );
q.pop();
}
*/
if( root )
    {
        Clist cl;
        List lTmp;
       
        initClist( &cl );
        lTmp.address = root;
        push_backClist( &cl, &lTmp );

    while( cl.size )
    {
        Node* tmp = cl.start->address; /* front node */
        printf( " %d", tmp->data );
        if( tmp->red ) putchar('r');

        /* if( cl.size == 1 ) { putchar('\n'); } */

    if( tmp->link[0] != 0 ) { lTmp.address = tmp->link[0];
                                      push_backClist( &cl, &lTmp ); }
    if( tmp->link[1] != 0 ) { lTmp.address = tmp->link[1];
                                      push_backClist( &cl, &lTmp ); }

            eraseClist( &cl, cl.start ); /* pop front */
    }
    }
}

/* non-recursive ... */
void printInOrder_nr ( Tree* tr )
{
    Node* it = tr->root;
    /* Node** up = malloc( sizeof( Node* ) * tr->size ); */
    Clist stk;
    List tmp;
    initClist( &stk );
    /* if( up ) */
    {
        /* int top = 0; */

        while ( it )
        {
            while ( it )
            {
                if ( it->link[1] )
                   /* up[top++] = it->link[1]; */
                   {
                       tmp.address = it->link[1];
                       push_frontClist( &stk, &tmp );
                   }

                /* up[top++] = it; */
                tmp.address = it;
                push_frontClist( &stk, &tmp );

                it = it->link[0];
            }

            /* it = up[--top]; */
            it = stk.start->address;
            eraseClist( &stk, stk.start );

            /* while ( top != 0 && !it->link[1] ) */
            while( stk.size && !it->link[1] )
            {
                printf ( " %d", it->data );
                /* it = up[--top]; */
                it = stk.start->address;
                eraseClist( &stk, stk.start );
            }

            printf ( " %d", it->data );

            /* if ( top == 0 ) */
            if( !stk.size )
               break;

            /* it = up[--top]; */
            it = stk.start->address;
            eraseClist( &stk, stk.start );
        }

        /*free( up ); */
        clearClist( &stk );
    }
}

void print4Orders( Tree* mySet, int useRecursion )
{
    int num;
   
    printf( "mySet->size = %d, ", mySet->size );
    if( mySet->size )
    {
        Node* tmp = minVal( mySet->root );
        printf( "minVal = %d, ", tmp->data );
        tmp = maxVal( mySet->root );
        printf( "maxVal = %d\n", tmp->data );
    }

    if( mySet->size <= 1000 )
    {
        if( useRecursion )
        {
            puts( "printInOrder: " );
            printInOrder( mySet->root );
            puts( "\nprintInPreOrder: " );
            printInPreOrder( mySet->root );
            puts( "\nprintInPostOrder: " );
            printInPostOrder( mySet->root );
        }
        else
        {
            puts( "printInOrder_nr: " );
            printInOrder_nr ( mySet );
        }
       
        puts( "\nprintInLevelOrder (printing with 'r' if 'red'):" );
        printLevelOrder( mySet->root );
    }
   
    num = isRBT( mySet->root ) ;
    printf( "\nisRBT( mySet->root ) = %s, 'BLACK' count here = %d\n",
            (num ? "TRUE" : "FALSE"), num );
}



#include <time.h> /* re. srand( time(0) ); */


int main()
{
    Tree mySet, mySet2;
    Traversal it;
    Node* x;
    int i, maxSize = MAX_TEST_SIZE, ary[MAX_TEST_SIZE+1] = {0};
   
    initTree( &mySet );
    initTree( &mySet2 );
   
    srand( time(0) );
   
    /* testing recursive parts ...*/
   
    printf( "Now ... insertVal, (recursive), in RANDOM order, "
            "in range 1 to %d\n", maxSize );
    for( i = 1; i <= maxSize; ++ i )
    {
        ary[i] = 1 + rand() % maxSize;
        insertVal( &mySet, ary[i] );
    }
    print4Orders( &mySet, 1 ); /* 1 => use recursive calls ... */


    printf( "\n\nNow ... removeVal, (recursive), with pause, "
            "in same random insertion order ...\n" );
    for( i = 1; i <= maxSize; ++ i )
    {
        int removed;
        printf( "\n%d %s available to be removed ... ",
                ary[i], ( findVal( &mySet, ary[i] ) ? "*IS*": "is *NOT*" ) );
        removed  = removeVal( &mySet, ary[i] );
        printf( "after attempt to remove %d ...\n", ary[i] );
        if( removed )
        {
            print4Orders( &mySet, 1 );
        }
        else printf( "%d NOT removed.\n", ary[i] );

        fputs( "\nPAUSE ... Press 'Enter' to continue... ", stdout );
        while( getchar() != '\n' );
    }

    /* testing NON-recursive (_nr) parts ...*/

    printf( "\n\nNow ... insertVal_nr, with pause, "
            "in ascending order from 1 to %d\n", maxSize );
    for( i = 1; i <= maxSize; ++ i )
    {
        insertVal_nr( &mySet2, i ); /* non-recursive insertVal... */
        putchar( '\n' ) ;
        print4Orders( &mySet2, 0 );
        fputs( "\nPAUSE ... Press 'Enter' to continue... ", stdout );
        while( getchar() != '\n' );
    }
   
    printf( "size = %d\n", mySet2.size );
    printf( "\n\nNow ... removeVal_nr, with pause, "
            "in random order ...\n" );
    while( mySet2.size )
    {
        int test, removed;
        do
        {
            test = 1 + rand() % maxSize;
        }
        while( !findVal_nr( &mySet2, test) );
       
        removed  = removeVal_nr ( &mySet2, test );
        printf( "\nAfter attempt to remove %d ... ", test );
        if( removed )
        {
            print4Orders( &mySet2, 0 );
        }
        else printf( "%d NOT removed.\n", test );
       
        fputs( "\nPAUSE ... Press 'Enter' to continue... ",
               stdout );
        while( getchar() != '\n' );
    }
   
    printf( "size = %d\n", mySet2.size );
   
   
    for( i = 1; i <= maxSize; ++ i )
    {
        insertVal( &mySet2, ary[i] );
    }
    printf( "\nBefore testing destroy... size = %d ... ",
            mySet2.size );

    puts( "testing 'Traversal' ..." );
    /* Node* x; Traversal it; */
    x = traversalBegin ( &mySet2, &it );
    while( x )
    {
        printf ( " %d", x->data );
        x = traversalNext ( &it );
    }
    puts( "\nprintInOrder_nr:" );
    printInOrder_nr ( &mySet2 );

    destroyTree( &mySet2 );
    printf( "\nAfter destroy... size = %d\n", mySet2.size );
   
   
    fputs( "\n\nPress 'Enter' to continue/exit ... ", stdout );
    while( getchar() != '\n' );
   
    return 0;
}


[David]

Now the  rbt.h  file that needs to be included by the test program above ...

Code: [Select]

/* rbt.h */  /* 2014-11-06 */

/*
    This file is an edited version of example code found at:
    Eternally Confuzzled - Red Black Tree Tutorial.htm
    Article was placed by its author, Julienne Walker, into 'Public Domain'
*/

#include <stdio.h>
#include <stdlib.h>

#define MAX_DEPTH_EXPECTED 50 /* for pre-fixed max size stack used in Traversal */


typedef struct myNode
{
    int red;
    int data;
    struct myNode* link[2]; /* link[0] holds 'left' pointer,
                            link[1] holds the 'right' ... */
} Node ;

typedef struct myTree
{
    Node* root;
    int size;
} Tree ;

void initTree( Tree* tr )
{
    tr->root = 0;
    tr->size = 0;
}

int isRed( Node* root )
{
    return root && root->red;
}

/* a non-recursive find... */
Node* findVal_nr( Tree* tr, int val )
{
    Node* cur = tr->root;
    while( cur && cur->data != val )
    {
        int dir = cur->data < val;
        cur = cur->link[dir];
    }
    return cur;
}

/* a recursive find... */
Node* findVal_r( Node* cur, int val )
{
    if ( !cur )
       return cur;
    else if ( cur->data == val )
         return cur;
    else
    {
        int dir = cur->data < val;
        return findVal_r ( cur->link[dir], val );
    }
}
Node* findVal( Tree* tr, int val )
{
    return findVal_r( tr->root, val );
}



Node* rotate1( Node* root, int dir )
{
    Node* save = root->link[!dir];

    root->link[!dir] = save->link[dir];
    save->link[dir] = root;

    root->red = 1;
    save->red = 0;

    return save;
}

Node* rotate2( Node* root, int dir )
{
    root->link[!dir] = rotate1( root->link[!dir], !dir );
    return rotate1( root, dir );
}

/* test if really is a Red Black Tree, i.e. conditions hold ... */
int isRBT( Node* root )
{
    int lh, rh;

    if( root == 0 )
        return 1;
    else
    {
        Node* ln = root->link[0];
        Node* rn = root->link[1];

        /* Consecutive red links */
        if ( isRed( root ) )
        {
            if( isRed( ln ) || isRed( rn ) )
            {
                puts( "Red violation" );
                return 0;
            }
        }

        lh = isRBT( ln );
        rh = isRBT( rn );

        /* Invalid binary search tree */
        if( ( ln  && ln->data >= root->data )
            || ( rn && rn->data <= root->data ) )
        {
            puts( "Binary tree violation" );
            return 0;
        }

        /* Black height mismatch */
        if( lh && rh && lh != rh )
        {
            puts( "Black violation" );
            return 0;
        }

        /* Only count black links */
        if( lh && rh )
            return isRed( root ) ? lh : lh + 1;
        else
            return 0;
    }
}

 Node* makeNode ( int data )
 {
    Node* rn = malloc( sizeof(Node) );

    if( rn )
    {
        rn->data = data;
        rn->red = 1; /* 1 is red, 0 is black */
        rn->link[0] = 0;
        rn->link[1] = 0;
     }
     
     return rn;
}

/* a recursive insert... */
Node* insertVal_r( Node* root, int data, int* size )
{
    if( !root )
        { root = makeNode( data ); ++ *size; }
    else if( root->data != data )
    {
        int dir = root->data < data;

        root->link[dir] = insertVal_r( root->link[dir], data, size );

        if( isRed ( root->link[dir] ) )
        {
            if( isRed ( root->link[!dir] ) )
            {
                /* Case 1 */
                root->red = 1;
                root->link[0]->red = 0;
                root->link[1]->red = 0;
            }
            else
            {
                /* Cases 2 & 3 */
                if( isRed ( root->link[dir]->link[dir] ) )
                    root = rotate1( root, !dir );
                else if( isRed ( root->link[dir]->link[!dir] ) )
                     root = rotate2( root, !dir );
            }
        }
    }
   
    return root;
}
int insertVal( Tree* tr, int data )
{
    tr->root = insertVal_r( tr->root, data, &tr->size );
    tr->root->red = 0;
    return tr->size;
}

/* a non-recursive insert... */
int insertVal_nr ( Tree *tr, int data )
{
  int sav_size = tr->size;
  if ( !tr->root )
  {
    /* Empty tr case */
    tr->root = makeNode ( data );
    if ( !tr->root )
      return 0;
    else ++ tr->size;
  }
  else
  {
    Node head = {0}; /* False Tree root */

    Node *g, *t;     /* Grandparent & parent */
    Node *p, *q;     /* Iterator & parent */
    int dir = 0, last;

    /* Set up helpers */
    t = &head;
    g = p = NULL;
    q = t->link[1] = tr->root;

    /* Search down the Tree */
    for ( ; ; )
    {
      if ( !q )
      {
        /* Insert new node at the bottom */
        p->link[dir] = q = makeNode ( data );
        if ( !q )
          return 0;
        else ++ tr->size;
      }
      else if ( isRed ( q->link[0] ) && isRed ( q->link[1] ) )
      {
        /* Color flip */
        q->red = 1;
        q->link[0]->red = 0;
        q->link[1]->red = 0;
      }

      /* Fix red violation */
      if ( isRed ( q ) && isRed ( p ) )
      {
        int dir2 = t->link[1] == g;

        if ( q == p->link[last] )
          t->link[dir2] = rotate1 ( g, !last );
        else
          t->link[dir2] = rotate2 ( g, !last );
      }

      /* Stop if found */
      if ( q->data == data )
        break;

      last = dir;
      dir = q->data < data;

      /* Update helpers */
      if ( g )
        t = g;
      g = p, p = q;
      q = q->link[dir];
    }

    /* Update root */
    tr->root = head.link[1];
  }

  /* Make root black */
  /* if reach here ... tr->root) != 0 ... */
  tr->root->red = 0;

  return sav_size < tr->size;
}

/* a non-recursive remove... */
int removeVal_nr ( Tree* tr, int data )
{
  int sav_size = tr->size;
  if ( tr->root )
  {
    Node head = {0}; /* False tree root */
    Node *q, *p, *g; /* Helpers */
    Node *f = 0;  /* Found item */
    int dir = 1;

    /* Set up helpers */
    q = &head;
    g = p = 0;
    q->link[1] = tr->root;

    /* Search and push a red down */
    while ( q->link[dir] )
    {
      int last = dir;

      /* Update helpers */
      g = p, p = q;
      q = q->link[dir];
      dir = q->data < data;

      /* Save found node */
      if ( q->data == data )
        f = q;

      /* Push the red node down */
      if ( !isRed ( q ) && !isRed ( q->link[dir] ) )
      {
        if ( isRed ( q->link[!dir] ) )
          p = p->link[last] = rotate1 ( q, dir );
        else if ( !isRed ( q->link[!dir] ) )
        {
          Node *s = p->link[!last];

          if ( s )
          {
            if ( !isRed ( s->link[!last] ) && !isRed ( s->link[last] ) )
            {
              /* Color flip */
              p->red = 0;
              s->red = 1;
              q->red = 1;
            }
            else
            {
              int dir2 = g->link[1] == p;

              if ( isRed ( s->link[last] ) )
                g->link[dir2] = rotate2 ( p, last );
              else if ( isRed ( s->link[!last] ) )
                g->link[dir2] = rotate1 ( p, last );

              /* Ensure correct colouring */
              q->red = g->link[dir2]->red = 1;
              g->link[dir2]->link[0]->red = 0;
              g->link[dir2]->link[1]->red = 0;
            }
          }
        }
      }
    }

    /* Replace and remove if found */
    if ( f )
    {
      f->data = q->data;
      p->link[p->link[1] == q] = q->link[q->link[0] == 0];
      free ( q );
      --tr->size;
    }

    /* Update root and make it black */
    tr->root = head.link[1];
    if( tr->root )
      tr->root->red = 0;
  }
 
  return tr->size < sav_size;;
}

/* for the recursive remove... */
Node* remove_balance ( Node* root, int dir, int* done )
{
  Node* p = root;
  Node* s = root->link[!dir];

  /* Case reduction, remove red sibling */
  if ( isRed ( s ) )
  {
    root = rotate1 ( root, dir );
    s = p->link[!dir];
  }

  if ( s != 0 )
  {
    if ( !isRed ( s->link[0] ) && !isRed ( s->link[1] ) )
    {
      if ( isRed ( p ) )
        *done = 1;
      p->red = 0;
      s->red = 1;
    }
    else
    {
      int save = p->red;
      int new_root = ( root == p );

      if ( isRed ( s->link[!dir] ) )
        p = rotate1 ( p, dir );
      else
        p = rotate2 ( p, dir );

      p->red = save;
      p->link[0]->red = 0;
      p->link[1]->red = 0;

      if ( new_root )
        root = p;
      else
        root->link[dir] = p;

      *done = 1;
    }
  }

  return root;
}
/* for the recursive remove... */
Node* remove_r ( Node* root, int data, int* done, int* size )
{
    if ( !root )
       *done = 1;
    else
    {
        int dir;

        if ( root->data == data )
        {
            if ( root->link[0] == 0 || root->link[1] == 0 )
            {
                Node* save = root->link[root->link[0] == 0];

                /* Case 0 */
                if ( isRed ( root ) )
                   *done = 1;
                else if ( isRed ( save ) )
                {
                    save->red = 0;
                    *done = 1;
                }

                free ( root );
                -- *size;

                return save;
            }
            else
            {
                Node* heir = root->link[0];

                while ( heir->link[1] != 0 )
                    heir = heir->link[1];

                root->data = heir->data;
                data = heir->data;
            }
        }

        dir = root->data < data;
        root->link[dir] = remove_r ( root->link[dir], data, done, size );

        if ( !*done )
            root = remove_balance ( root, dir, done );
    }

    return root;
}
/* a recursive remove... */
int removeVal ( Tree* tr, int data )
{
    int done = 0, sav_size = tr->size;

    tr->root = remove_r ( tr->root, data, &done, &tr->size );
    if ( tr->root )
       tr->root->red = 0;

    return tr->size < sav_size;
}

/* recursive... */
void printInOrder( const Node* root )
{
    if( root )
    {
        printInOrder(root->link[0] );
        printf( " %d", root->data );
        printInOrder(root->link[1] );
    }
}
/* recursive... */
void printInPreOrder( const Node* root )
{
    if( root )
    {
        printf( " %d", root->data );
        printInPreOrder(root->link[0] );
        printInPreOrder(root->link[1] );
    }
}
/* recursive... */
void printInPostOrder( const Node* root )
{
    if( root )
    {
        printInPostOrder(root->link[0] );
        printInPostOrder(root->link[1] );
        printf( " %d", root->data );
    }
}

/* non_recursive... ***ASSUMES NONE EMPTY TREE***  */
Node* minVal( Node* root )
{
    Node* cur = root;
    while( cur && cur->link[0] ) cur = cur->link[0];
    return cur;
}
/* non_recursive... ***ASSUMES NONE EMPTY TREE***  */
Node* maxVal( Node* root )
{
    Node* cur = root;
    while( cur && cur->link[1] ) cur = cur->link[1];
    return cur;
}


/* Note: the '_r' indicates that this is a recursive function ... */
void destroyTree_r ( Node* cur )
{
    if ( cur )
    {
        /* Note: using a 'postorder' traversalersal ...
        so each 'root' is a 'leaf' */
        destroyTree_r ( cur->link[0] );
        destroyTree_r ( cur->link[1] );
        free ( cur );
    }
}
void destroyTree ( Tree* tr )
{
    destroyTree_r ( tr->root );
    initTree( tr );
}



typedef struct myTraversal
{
    Node* up[MAX_DEPTH_EXPECTED]; /* Stack */
    Node* it;     /* Current node */
    int top;      /* Top of stack */
} Traversal ;


Node* traversalBegin ( Tree *tre, Traversal* trv )
{
    trv->it = tre->root;
    trv->top = 0; /* now initial values are ser ... */

    if ( trv->it )
    {
        while ( trv->it->link[0] )
        {
            trv->up[trv->top++] = trv->it;
            trv->it = trv->it->link[0];
        }
    }
    return trv->it;
}


Node* traversalNext ( Traversal* trv )
{
    if ( trv->it->link[1] )
    {
        trv->up[trv->top++] = trv->it;
        trv->it = trv->it->link[1];

        while ( trv->it->link[0] )
        {
            trv->up[trv->top++] = trv->it;
            trv->it = trv->it->link[0];
        }
    }
    else
    {
        Node* last;

        do
        {
            if ( !trv->top )
            {
                trv->it = 0;
                break;
            }

            last = trv->it;
            trv->it = trv->up[--trv->top];
        }
        while ( last == trv->it->link[1] );
    }

    return trv->it;
}


[David]

And now back to a demo of coding and using an iterator for a binary search tree ...

Firstly the .txt data file (Name it Persons.txt), then the test .cpp file ... and then the .h file ...

Enjoy

Code: [Select]

19570810 101440980 Bob Lamprey NY
19270624 103980155 Pinky Fellowes OR
19470314 106100903 Oliver Kringle ND
19480105 108690448 Louie Brown KS
19641028 111180924 Alan Davies UT
19710227 112200747 Bella Napster OK
19730716 112550407 Roger Stone OR
19750716 111111111 Mary Stone OR
19570504 113070570 James Mitchell TX
19401023 113220519 Jilly Aston WY
19670607 114680858 Matt Vincent MI

Now the . cpp file ...

Code: [Select]

// test_bsTreeIterator.h.cpp //  // 2017-04-16 //


#include "bsTreeIterator.h"

#include <fstream>
#include <iomanip>
#include <sstream>
#include <string>


const char* MENU =
    "Find .............. Enter :  F lastname \n"
    "Print (tree) ...... Enter :  P lastname \n"
    "eXit .............. Enter :  X";

const char* FNAME = "Persons.txt";
/*
19570810 101440980 Bob Lamprey NY
19270624 103980155 Pinky Fellowes OR
19470314 106100903 Oliver Kringle ND
19480105 108690448 Louie Brown KS
19641028 111180924 Alan Davies UT
19710227 112200747 Bella Napster OK
19730716 112550407 Roger Stone OR
19750716 111111111 Mary Stone OR
19570504 113070570 James Mitchell TX
19401023 113220519 Jilly Aston WY
19670607 114680858 Matt Vincent MI
*/


class Person
{
public:
    // ctor... (also default ctor with default values) //
    Person( int dob=0, int ssn=0, std::string fn="", std::string ln="", std::string st="" )
        : dob(dob), ssn(ssn), fname(fn), lname(ln), state(st) {}

    // re. 'ordering rule' for 'Person' objects ...
    bool operator < ( const Person& other ) const
    {
        if( lname != other.lname )
            return lname < other.lname;
        // else are the same ... so ...
        return fname < other.fname;
    }
    // re. search on names ...
    bool operator == ( const Person& other ) const
    {
        return lname == other.lname;
    }
private:
    int dob;
    int ssn;
    std::string fname;
    std::string lname;
    std::string state;
   
    // def'n of overloaded operator << for Person objects ...
    friend std::ostream& operator << ( std::ostream& os, const Person& per )
    {
        return os << std::left << std::setw(25) << per.lname + ", " + per.fname
                  << std::right << ' ' << per.state
                  << ' ' << per.dob << ' ' << per.ssn;
    }
    // to facilitate file input //
    friend std::istream& operator >> ( std::istream& is, Person& per )
    {
        is >> per.dob >> per.ssn >> per.fname >> per.lname >> per.state;
        return is;
    }
} ;


// load into (an empty) BSTree object, all records from file with name: fname
// BUT only load up to MAX elements //
bool load( const char* fname, BSTree< Person >& bst )
{
    std::ifstream fin( fname );
    if( fin )
    {
        Person tmp;
        while( fin >> tmp )
            bst.insert( tmp );
        fin.close();
        return true;
    }

    std::cout << "\nThere was a problem opening file "
              << fname << '\n';
    return false;
}

Person extractSearchInfo( const std::string& ans )
{
    std::string dummy, lname;
    std::istringstream iss( ans );
    iss >> dummy >> lname;
    return Person( 0, 0, "", lname );
}

std::string showMenuGetChoice()
{
    std::cout << MENU << "\nEnter your choice of line :  ";
    std::string line;
    getline( std::cin, line );
    return line;
}




int main()
{
    using std::cout; using std::string;
   
    BSTree< Person > tree;
    if( load( FNAME, tree ) )
    {
        cout << "There were " << tree.size() << " people in file '"
             << FNAME << "'\n";
             
        BSTree< Person >::Iterator it;
        for( it = tree.begin(); it != tree.end(); ++ it )
        {
            cout << *it << '\n';
        }
       
        for( ; ; )
        {
            char ch = 0;
            string ans = showMenuGetChoice();
            if( ans.size() ) ch = ans[0];
            Person tmp;
            switch( ch )
            {
                case 'f' : case 'F' : /* take in search info and search and report */
                    tmp = extractSearchInfo( ans );
                    if( tree.isItem( tmp, true ) ) // 'true' to show num checks //
                        cout << "Found and data on file is: "
                             << *tree.find( tmp ) << '\n';
                    else cout << "Not found.\n";
                break;
                case 'p' : case 'P' : /* talke in top of tree info and report (from there) */
                    tmp = extractSearchInfo( ans );
                    if( tree.isItem( tmp ) )
                    {
                        cout << "Found and tree (printed in order) from there is:\n";
                        tree.print_r( tree.findNode(tmp), cout, '\n' );

                    }
                    else cout << "Not found.\n";
                break;
                case 'x' : case 'X' :
                    return 0;
                break;
                default  : cout << "'" << ch << "' is NOT a valid entry here ...\n";
            }
        }
    }
}


And finally, the .h file ...

Code: [Select]

// BSTreeIterator.h //  // revised 2017-04-16 //

// this revision was on 2017-04-15 ...
// and was to make (most all) recursive methods PRIVATE
// since these meyhods are NOT to Be called by the user. //


// Using the C++ library stack in the following (nested) class iterator  ...

#ifndef BSTREEITERATOR_H
#define BSTREEITERATOR_H

#include <iostream>
#include <stack>


////////////////////////////////////////////////////////////
//
// // USAGE example:
//
// // constuct begin ('it') and end ('end') iterators:
// BSTree< objTYPE >::Iterator it = bst.begin(), end = bst.end();
//
// // print tree via *it and ++ it  ... till reach end:
// for( ; it != end ;  ++ it ) std::cout << *it << '\n';
//
////////////////////////////////////////////////////////////


template< typename T >
class BSTree
{
    // forward declaration ...
    class TreeNode;
public:
    // default ctor...
    BSTree() : root(0), len(0) {}

    // dtor...
    ~BSTree() { clean(); }
   
    void clean()
    {
std::cout << "Please wait a bit while the tree memory is freed up ... ";
        clean_r( root );

        root = 0;
        len = 0;
    }
   
    // copy ctor ... calls the recursive private method given below...
    BSTree( const BSTree& bst )
    {
        root = 0;
        len = 0;
        BSTree_r( root, bst.root );
    }

    // overloaded asignment ... calls the same recursive private method ...
    BSTree& operator = ( const BSTree& bst )
    {
        if( this != &bst )
        {
            clean(); // Note: sets root to 0 and len to 0 //
            BSTree_r( root, bst.root );
        }
        return *this;
    }

    void insert( const T& data )
    {
        insert_r( root, data ); // calls the private resursive method below ... //
        ++ len;
    }

    // A NON recursive search method ... //
    bool isItem( const T& data, bool show_count_steps = false ) const
    {
        // Return true if data is one of the items in the binary
        // sort tree to which root points.   Return false if not.
        TreeNode* cur = root;  // For "running" down the tree ...
                                    // start at the root node
        int count = 0; // so can count 'steps' ... and report if needed. //
        for( ; ; )
        {
            if( cur == 0 ) // We've fallen off the tree without finding data.
            {
                if( show_count_steps)
                    std::cout << "Number of tests was: " << ++count << '\n';
                return false;
            }
            else if( data == cur->data ) // We've found the data.
            {
                if( show_count_steps)
                    std::cout << "Number of tests was: " << ++count << '\n';
                return true;
            }
            else if( data < cur->data )
            {
                ++ count;
                // If the data occurs, it must be in the left subtree,
                // So, advance the runner down one level to the left.
                cur = cur->left;
            }
            else
            {
                ++ count;
                // If the data occurs, it must be in the right subtree.
                // So, advance the runner down one level to the right.
                cur = cur->right;
            }
        }  // end 'loop for ever' ... until return is reached //
    }
   
    TreeNode* findNode( const T& data )
    {
        return findNode( root, data ); // calls private method //
    }
   
   
    class Iterator
    {
    private:
        TreeNode* curNode;
        std::stack< TreeNode* > stkNodes;
    public:
        Iterator() : curNode(0) {}
       
        void set_curNode( TreeNode* tn ) { curNode = tn; }
       
        Iterator( TreeNode* binTree )
        {
            TreeNode* root = binTree;

            while( root )
            {
                stkNodes.push( root );
                root = root->left;
            }

            if( stkNodes.size() > 0 )
            {
                curNode = stkNodes.top();
                stkNodes.pop();
            }
            else
                curNode = 0;
        }

        T& operator * ()             { return curNode->data; }
        const T& operator * () const { return curNode->data; }


        bool operator == (const Iterator& other) const
        {
            return curNode == other.curNode;
        }

        bool operator != (const Iterator& other) const
        {
            return curNode != other.curNode;
        }

        Iterator& operator ++ ()
        {
            if( curNode->right )
            {
                stkNodes.push( curNode->right );

                if( curNode->right->left )
                    stkNodes.push( curNode->right->left );
            }

            if( stkNodes.empty() )
            {
                curNode = 0;
                return *this;
            }

            curNode = stkNodes.top();
            stkNodes.pop();

            return *this;
        }

        // Note that since, here, we are returning ONLY a copy,
        // this version does NOT permit records to be updated. //
        Iterator operator ++ ( int )
        {
            // NOTE this cpy here, i..e the correct way to implement POST ++ //
            Iterator cpy = *this;

            if( curNode->right )
            {
                stkNodes.push( curNode->right );

                if( curNode->right->left )
                    stkNodes.push( curNode->right->left );
            }

            if( stkNodes.empty() )
            {
                curNode = 0;
                return *this;
            }

            curNode = stkNodes.top();
            stkNodes.pop();
           
            return cpy;
        }
       
    } ; // END class Iterator //
   
    Iterator begin() { return Iterator( root ); }
    Iterator end() { return Iterator( 0 ); }
   
    Iterator find( const T& data )
    {
        Iterator tmp;
        tmp.set_curNode( findNode( root, data ) ); // calls the private method def'd below ... //
        return tmp;
    }
   
   
    //TreeNode* get_root() { return root; }

    size_t size() const { return len; }

/*
    size_t countNodes_r( const TreeNode< T >* cur ) const // recursive //
    {
        if( cur == 0 ) return 0;  // The tree is empty.  It contains no nodes.
        // else

        size_t count = 1;  // Start by counting the root.
        count += countNodes_r( cur->left) ;  // Add the number of nodes in the left subtree.
        count += countNodes_r( cur->right ); // Add the number of nodes in the right subtree.
        return count;  // Return the total.
    }
    size_t countNodes() const { return countNodes_r( root ); }
*/
    int maxDepth_r( const TreeNode* cur ) const
    {
        if( cur == 0 ) return 0;
        // else
       
        /* get depth of each subtree */
        int ld = maxDepth_r( cur->left );
        int rd = maxDepth_r( cur->right );

        /* return greater of two values + 1 */
        return ( ld > rd ? ld +1 : rd +1 );
    }
    int maxDepth() const // calls above method //
    {
        return maxDepth_r( root );
    }
   
    // print in order  ... used in main here so left here in public section ... //
    void print_r( const TreeNode* root, std::ostream& os = std::cout, char end = ' ' ) const
    {
        // The items in the left subtree are printed first, followed
        // by the data in the root node, followed by the items in
        // the right subtree.
        if( root == 0 )  return;         // there's nothing to print //

        print_r( root->left, os, end );  // Print items in left subtree.
        os << root->data << end;         // Print the root data.
        print_r( root->right, os, end ); // Print items in right subtree.
    }

    // print in order //
    void print( std::ostream& os = std::cout, char end = ' ' ) const
    {
        print_r( root, os, end );
    }
    void preorderPrint( std::ostream& os = std::cout, char end = ' ' ) const
    {
        preorderPrint_r( root, os, end );
    }
    void postorderPrint( std::ostream& os = std::cout, char end = ' ' ) const
    {
        postorderPrint_r( root, os, end );
    }

private:
    struct TreeNode
    {
        T data;           // The data in this node.
        TreeNode* left;   // Pointer to the left subtree.
        TreeNode* right;  // Pointer to the right subtree.
       
        // ctor...
        TreeNode( T data ) : data(data), left(0), right(0) {}
/*
        friend std::ostream& operator << ( std::ostream& os, const TreeNode& tn )
        {
            return os << tn.data;
        }
*/
    } ;

    TreeNode* root;
    size_t len;
   
    void clean_r( TreeNode* root )
    {
        if( root == 0 ) return;

        clean_r( root->left  );
        clean_r( root->right );
        delete root;
    }
   
    // Note ...traversing the passed in const bst in pre-order

    // Note that this recusive method is also called by
    // the overloaded assignment nelow //
    void BSTree_r( TreeNode*& nroot, const TreeNode* bstroot  )
    {
        if( ! bstroot ) return; // there's nothing to insert //

        insert( bstroot->data );           // insert the root data
        BSTree_r( nroot, bstroot->left );  // ...items in left subtree
        BSTree_r( nroot, bstroot->right ); // ... items in right subtree
    }
   
    // recursive method //
    void insert_r( TreeNode*& root, const T& data )
    {
        // Note that root is passed by reference since its value
        // can change in the case where the tree is empty.
        if( ! root )
        {
            // The tree is empty. Set root to point to a new node containing
            // the new data. This becomes the only node in the tree.

            root = new TreeNode( data );

            // NOTE: The left and right subtrees of root
            // are automatically set to 0 by the constructor.
            // This is important! !!! //

            return;
        }
        if( data < root->data )
            insert_r( root->left, data );
        else
            insert_r( root->right, data );
    }

    // A NON-recursive find ...
    // BUT!!! do NOT CHANGE, via this pointer,
    // the 'key' field(s) in the Mode !!! //
    TreeNode* findNode( TreeNode* cur, const T& data )
{
while( cur )
{
            if( data == cur->data )
                return cur;
if( data < cur->data )
cur = cur->left;
else
cur = cur->right;
}
return 0; // NOT found ... //
     }
     
    void preorderPrint_r( const TreeNode* root, std::ostream& os, char end ) const
    {
        if( root == 0 ) return;

        os << root->data << end; // Print the root data.
        preorderPrint_r( root->left, os, end );  // Print items in left subtree.
        preorderPrint_r( root->right ); // Print items in right subtree.
    }
    void postorderPrint_r( const TreeNode* root, std::ostream& os, char end ) const
    {
        if( root == 0 ) return;

        postorderPrint_r( root->left );  // Print items in left subtree.
        postorderPrint_r( root->right ); // Print items in right subtree.
        os << root->data << end;  // Print the root data.
    }
   
} ;

 #endif