Desktop Programming > C/C++ & Visual C++

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

(1/2) > >>

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: ---/* 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;
}
--- End code ---

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


--- Code: ---/* 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
--- End code ---

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: ---// 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;

}

--- End code ---

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


--- Code: ---// 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
--- End code ---

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: ---/* 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;
}
--- End code ---

Navigation

[0] Message Index

[#] Next page