DS_BinarySearchTree.h

Go to the documentation of this file.

#ifndef __BINARY_SEARCH_TREE_H
#define __BINARY_SEARCH_TREE_H

#include "DS_QueueLinkedList.h"
#include "RakMemoryOverride.h"
#include "Export.h"


#ifdef _MSC_VER
#pragma warning( push )
#endif

namespace DataStructures
{
        template <class BinarySearchTreeType>
        class RAK_DLL_EXPORT BinarySearchTree
        {
        
        public:

                struct node
                {
                        BinarySearchTreeType* item;
                        node* left;
                        node* right;
                };
                
                BinarySearchTree();
                virtual ~BinarySearchTree();
                BinarySearchTree( const BinarySearchTree& original_type );
                BinarySearchTree& operator= ( const BinarySearchTree& original_copy );
                unsigned int Size( void );
                void Clear( const char *file, unsigned int line );
                unsigned int Height( node* starting_node = 0 );
                node* Add ( const BinarySearchTreeType& input, const char *file, unsigned int line );
                node* Del( const BinarySearchTreeType& input, const char *file, unsigned int line );
                bool IsIn( const BinarySearchTreeType& input );
                void DisplayInorder( BinarySearchTreeType* return_array );
                void DisplayPreorder( BinarySearchTreeType* return_array );
                void DisplayPostorder( BinarySearchTreeType* return_array );
                void DisplayBreadthFirstSearch( BinarySearchTreeType* return_array );
                BinarySearchTreeType*& GetPointerToNode( const BinarySearchTreeType& element );
                
        protected:

                node* root;
                
                enum Direction_Types
                {
                        NOT_FOUND, LEFT, RIGHT, ROOT
                } direction;
                unsigned int HeightRecursive( node* current );
                unsigned int BinarySearchTree_size;
                node*& Find( const BinarySearchTreeType& element, node** parent );
                node*& FindParent( const BinarySearchTreeType& element );
                void DisplayPostorderRecursive( node* current, BinarySearchTreeType* return_array, unsigned int& index );
                void FixTree( node* current );
                
        };
        
        template <class BinarySearchTreeType>
        class RAK_DLL_EXPORT AVLBalancedBinarySearchTree : public BinarySearchTree<BinarySearchTreeType>
        {
        
        public:
                AVLBalancedBinarySearchTree()   {}
                virtual ~AVLBalancedBinarySearchTree();
                void Add ( const BinarySearchTreeType& input );
                void Del( const BinarySearchTreeType& input );
                BinarySearchTree<BinarySearchTreeType>& operator= ( BinarySearchTree<BinarySearchTreeType>& original_copy )
                {
                        return BinarySearchTree<BinarySearchTreeType>::operator= ( original_copy );
                }
                
        private:
                void BalanceTree( typename BinarySearchTree<BinarySearchTreeType>::node* current, bool rotateOnce );
                void RotateRight( typename BinarySearchTree<BinarySearchTreeType>::node *C );
                void RotateLeft( typename BinarySearchTree<BinarySearchTreeType>::node* C );
                void DoubleRotateRight( typename BinarySearchTree<BinarySearchTreeType>::node *A );
                void DoubleRotateLeft( typename BinarySearchTree<BinarySearchTreeType>::node* A );
                bool RightHigher( typename BinarySearchTree<BinarySearchTreeType>::node* A );
                bool LeftHigher( typename BinarySearchTree<BinarySearchTreeType>::node* A );
        };
        
        template <class BinarySearchTreeType>
        void AVLBalancedBinarySearchTree<BinarySearchTreeType>::BalanceTree( typename BinarySearchTree<BinarySearchTreeType>::node* current, bool rotateOnce )
        {
                int left_height, right_height;
                
                while ( current )
                {
                        if ( current->left == 0 )
                                left_height = 0;
                        else
                                left_height = Height( current->left );
                                
                        if ( current->right == 0 )
                                right_height = 0;
                        else
                                right_height = Height( current->right );
                                
                        if ( right_height - left_height == 2 )
                        {
                                if ( RightHigher( current->right ) )
                                        RotateLeft( current->right );
                                else
                                        DoubleRotateLeft( current );
                                        
                                if ( rotateOnce )
                                        break;
                        }
                        
                        else
                                if ( right_height - left_height == -2 )
                                {
                                        if ( LeftHigher( current->left ) )
                                                RotateRight( current->left );
                                        else
                                                DoubleRotateRight( current );
                                                
                                        if ( rotateOnce )
                                                break;
                                }
                                
                        if ( current == this->root )
                                break;
                                
                        current = FindParent( *( current->item ) );
                        
                }
        }
        
        template <class BinarySearchTreeType>
        void AVLBalancedBinarySearchTree<BinarySearchTreeType>::Add ( const BinarySearchTreeType& input )
        {
        
                typename BinarySearchTree<BinarySearchTreeType>::node * current = BinarySearchTree<BinarySearchTreeType>::Add ( input, __FILE__,__LINE__ );
                BalanceTree( current, true );
        }
        
        template <class BinarySearchTreeType>
        void AVLBalancedBinarySearchTree<BinarySearchTreeType>::Del( const BinarySearchTreeType& input )
        {
                typename BinarySearchTree<BinarySearchTreeType>::node * current = BinarySearchTree<BinarySearchTreeType>::Del( input, __FILE__,__LINE__ );
                BalanceTree( current, false );
                
        }
        
        template <class BinarySearchTreeType>
        bool AVLBalancedBinarySearchTree<BinarySearchTreeType>::RightHigher( typename BinarySearchTree<BinarySearchTreeType>::node *A )
        {
                if ( A == 0 )
                        return false;
                        
                return Height( A->right ) > Height( A->left );
        }
        
        template <class BinarySearchTreeType>
        bool AVLBalancedBinarySearchTree<BinarySearchTreeType>::LeftHigher( typename BinarySearchTree<BinarySearchTreeType>::node *A )
        {
                if ( A == 0 )
                        return false;
                        
                return Height( A->left ) > Height( A->right );
        }
        
        template <class BinarySearchTreeType>
        void AVLBalancedBinarySearchTree<BinarySearchTreeType>::RotateRight( typename BinarySearchTree<BinarySearchTreeType>::node *C )
        {
                typename BinarySearchTree<BinarySearchTreeType>::node * A, *B, *D;
                /*
                  RIGHT ROTATION
                
                  A = parent(b)
                  b= parent(c)
                  c  = node to rotate around
                
                  A
                  | // Either direction
                  B
                  /   \
                  C
                  /   \
                  D
                
                  TO
                
                  A
                  | // Either Direction
                  C
                  /   \
                  B
                  /   \
                  D
                
                
                  <Leave all other branches branches AS-IS whether they point to another node or simply 0>
                
                */
                
                B = FindParent( *( C->item ) );
                A = FindParent( *( B->item ) );
                D = C->right;
                
                if ( A )
                {
                        // Direction was set by the last find_parent call
                        
                        if ( this->direction == this->LEFT )
                                A->left = C;
                        else
                                A->right = C;
                }
                
                else
                        this->root = C;  // If B has no parent parent then B must have been the root node
                        
                B->left = D;
                
                C->right = B;
        }
        
        template <class BinarySearchTreeType>
        void AVLBalancedBinarySearchTree<BinarySearchTreeType>::DoubleRotateRight( typename BinarySearchTree<BinarySearchTreeType>::node *A )
        {
                // The left side of the left child must be higher for the tree to balance with a right rotation.  If it isn't, rotate it left before the normal rotation so it is.
                RotateLeft( A->left->right );
                RotateRight( A->left );
        }
        
        template <class BinarySearchTreeType>
        void AVLBalancedBinarySearchTree<BinarySearchTreeType>::RotateLeft( typename BinarySearchTree<BinarySearchTreeType>::node *C )
        {
                typename BinarySearchTree<BinarySearchTreeType>::node * A, *B, *D;
                /*
                  RIGHT ROTATION
                
                  A = parent(b)
                  b= parent(c)
                  c  = node to rotate around
                
                  A
                  | // Either direction
                  B
                  /   \
                  C
                  /  \
                  D
                
                  TO
                
                  A
                  | // Either Direction
                  C
                  /   \
                  B
                  /   \
                  D
                
                
                  <Leave all other branches branches AS-IS whether they point to another node or simply 0>
                
                */
                
                B = FindParent( *( C->item ) );
                A = FindParent( *( B->item ) );
                D = C->left;
                
                if ( A )
                {
                        // Direction was set by the last find_parent call
                        
                        if ( this->direction == this->LEFT )
                                A->left = C;
                        else
                                A->right = C;
                }
                
                else
                        this->root = C;  // If B has no parent parent then B must have been the root node
                        
                B->right = D;
                
                C->left = B;
        }
        
        template <class BinarySearchTreeType>
        void AVLBalancedBinarySearchTree<BinarySearchTreeType>::DoubleRotateLeft( typename BinarySearchTree<BinarySearchTreeType>::node *A )
        {
                // The left side of the right child must be higher for the tree to balance with a left rotation.  If it isn't, rotate it right before the normal rotation so it is.
                RotateRight( A->right->left );
                RotateLeft( A->right );
        }
        
        template <class BinarySearchTreeType>
        AVLBalancedBinarySearchTree<BinarySearchTreeType>::~AVLBalancedBinarySearchTree()
        {
                this->Clear(__FILE__,__LINE__);
        }
        
        template <class BinarySearchTreeType>
        unsigned int BinarySearchTree<BinarySearchTreeType>::Size( void )
        {
                return BinarySearchTree_size;
        }
        
        template <class BinarySearchTreeType>
        unsigned int BinarySearchTree<BinarySearchTreeType>::Height( typename BinarySearchTree::node* starting_node )
        {
                if ( BinarySearchTree_size == 0 || starting_node == 0 )
                        return 0;
                else
                        return HeightRecursive( starting_node );
        }
        
        // Recursively return the height of a binary tree
        template <class BinarySearchTreeType>
        unsigned int BinarySearchTree<BinarySearchTreeType>::HeightRecursive( typename BinarySearchTree::node* current )
        {
                unsigned int left_height = 0, right_height = 0;
                
                if ( ( current->left == 0 ) && ( current->right == 0 ) )
                        return 1; // Leaf
                        
                if ( current->left != 0 )
                        left_height = 1 + HeightRecursive( current->left );
                        
                if ( current->right != 0 )
                        right_height = 1 + HeightRecursive( current->right );
                        
                if ( left_height > right_height )
                        return left_height;
                else
                        return right_height;
        }
        
        template <class BinarySearchTreeType>
        BinarySearchTree<BinarySearchTreeType>::BinarySearchTree()
        {
                BinarySearchTree_size = 0;
                root = 0;
        }
        
        template <class BinarySearchTreeType>
        BinarySearchTree<BinarySearchTreeType>::~BinarySearchTree()
        {
                this->Clear(__FILE__,__LINE__);
        }
        
        template <class BinarySearchTreeType>
        BinarySearchTreeType*& BinarySearchTree<BinarySearchTreeType>::GetPointerToNode( const BinarySearchTreeType& element )
        {
                static typename BinarySearchTree::node * tempnode;
                static BinarySearchTreeType* dummyptr = 0;
                tempnode = Find ( element, &tempnode );
                
                if ( this->direction == this->NOT_FOUND )
                        return dummyptr;
                        
                return tempnode->item;
        }
        
        template <class BinarySearchTreeType>
        typename BinarySearchTree<BinarySearchTreeType>::node*& BinarySearchTree<BinarySearchTreeType>::Find( const BinarySearchTreeType& element, typename BinarySearchTree<BinarySearchTreeType>::node** parent )
        {
                static typename BinarySearchTree::node * current;
                
                current = this->root;
                *parent = 0;
                this->direction = this->ROOT;
                
                if ( BinarySearchTree_size == 0 )
                {
                        this->direction = this->NOT_FOUND;
                        return current = 0;
                }
                
                // Check if the item is at the root
                if ( element == *( current->item ) )
                {
                        this->direction = this->ROOT;
                        return current;
                }

#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
                while ( true )
                {
                        // Move pointer
                        
                        if ( element < *( current->item ) )
                        {
                                *parent = current;
                                this->direction = this->LEFT;
                                current = current->left;
                        }
                        
                        else
                                if ( element > *( current->item ) )
                                {
                                        *parent = current;
                                        this->direction = this->RIGHT;
                                        current = current->right;
                                }
                                
                        if ( current == 0 )
                                break;
                                
                        // Check if new position holds the item
                        if ( element == *( current->item ) )
                        {
                                return current;
                        }
                }
                
                
                this->direction = this->NOT_FOUND;
                return current = 0;
        }
        
        template <class BinarySearchTreeType>
        typename BinarySearchTree<BinarySearchTreeType>::node*& BinarySearchTree<BinarySearchTreeType>::FindParent( const BinarySearchTreeType& element )
        {
                static typename BinarySearchTree::node * parent;
                Find ( element, &parent );
                return parent;
        }
        
        // Performs a series of value swaps starting with current to fix the tree if needed
        template <class BinarySearchTreeType>
        void BinarySearchTree<BinarySearchTreeType>::FixTree( typename BinarySearchTree::node* current )
        {
                BinarySearchTreeType temp;
                
                while ( 1 )
                {
                        if ( ( ( current->left ) != 0 ) && ( *( current->item ) < *( current->left->item ) ) )
                        {
                                // Swap the current value with the one to the left
                                temp = *( current->left->item );
                                *( current->left->item ) = *( current->item );
                                *( current->item ) = temp;
                                current = current->left;
                        }
                        
                        else
                                if ( ( ( current->right ) != 0 ) && ( *( current->item ) > *( current->right->item ) ) )
                                {
                                        // Swap the current value with the one to the right
                                        temp = *( current->right->item );
                                        *( current->right->item ) = *( current->item );
                                        *( current->item ) = temp;
                                        current = current->right;
                                }
                                
                                else
                                        break;  // current points to the right place so quit
                }
        }
        
        template <class BinarySearchTreeType>
        typename BinarySearchTree<BinarySearchTreeType>::node* BinarySearchTree<BinarySearchTreeType>::Del( const BinarySearchTreeType& input, const char *file, unsigned int line )
        {
                typename BinarySearchTree::node * node_to_delete, *current, *parent;
                
                if ( BinarySearchTree_size == 0 )
                        return 0;
                        
                if ( BinarySearchTree_size == 1 )
                {
                        Clear(file, line);
                        return 0;
                }
                
                node_to_delete = Find( input, &parent );
                
                if ( direction == NOT_FOUND )
                        return 0;  // Couldn't find the element
                        
                current = node_to_delete;
                
                // Replace the deleted node with the appropriate value
                if ( ( current->right ) == 0 && ( current->left ) == 0 )    // Leaf node, just remove it
                {
                
                        if ( parent )
                        {
                                if ( direction == LEFT )
                                        parent->left = 0;
                                else
                                        parent->right = 0;
                        }
                        
                        RakNet::OP_DELETE(node_to_delete->item, file, line);
                        RakNet::OP_DELETE(node_to_delete, file, line);
                        BinarySearchTree_size--;
                        return parent;
                }
                else
                        if ( ( current->right ) != 0 && ( current->left ) == 0 )   // Node has only one child, delete it and cause the parent to point to that child
                        {
                        
                                if ( parent )
                                {
                                        if ( direction == RIGHT )
                                                parent->right = current->right;
                                        else
                                                parent->left = current->right;
                                }
                                
                                else
                                        root = current->right; // Without a parent this must be the root node
                                        
                                RakNet::OP_DELETE(node_to_delete->item, file, line);
                                
                                RakNet::OP_DELETE(node_to_delete, file, line);
                                
                                BinarySearchTree_size--;
                                
                                return parent;
                        }
                        else
                                if ( ( current->right ) == 0 && ( current->left ) != 0 )   // Node has only one child, delete it and cause the parent to point to that child
                                {
                                
                                        if ( parent )
                                        {
                                                if ( direction == RIGHT )
                                                        parent->right = current->left;
                                                else
                                                        parent->left = current->left;
                                        }
                                        
                                        else
                                                root = current->left; // Without a parent this must be the root node
                                                
                                        RakNet::OP_DELETE(node_to_delete->item, file, line);
                                        
                                        RakNet::OP_DELETE(node_to_delete, file, line);
                                        
                                        BinarySearchTree_size--;
                                        
                                        return parent;
                                }
                                else // Go right, then as left as far as you can
                                {
                                        parent = current;
                                        direction = RIGHT;
                                        current = current->right; // Must have a right branch because the if statements above indicated that it has 2 branches
                                        
                                        while ( current->left )
                                        {
                                                direction = LEFT;
                                                parent = current;
                                                current = current->left;
                                        }
                                        
                                        // Replace the value held by the node to RakNet::OP_DELETE(with the value pointed to by current, __FILE__, __LINE__);
                                        *( node_to_delete->item ) = *( current->item );
                                        
                                        // Delete current.
                                        // If it is a leaf node just delete it
                                        if ( current->right == 0 )
                                        {
                                                if ( direction == RIGHT )
                                                        parent->right = 0;
                                                else
                                                        parent->left = 0;
                                                        
                                                RakNet::OP_DELETE(current->item, file, line);
                                                
                                                RakNet::OP_DELETE(current, file, line);
                                                
                                                BinarySearchTree_size--;
                                                
                                                return parent;
                                        }
                                        
                                        else
                                        {
                                                // Skip this node and make its parent point to its right branch
                                                
                                                if ( direction == RIGHT )
                                                        parent->right = current->right;
                                                else
                                                        parent->left = current->right;
                                                        
                                                RakNet::OP_DELETE(current->item, file, line);
                                                
                                                RakNet::OP_DELETE(current, file, line);
                                                
                                                BinarySearchTree_size--;
                                                
                                                return parent;
                                        }
                                }
        }
        
        template <class BinarySearchTreeType>
        typename BinarySearchTree<BinarySearchTreeType>::node* BinarySearchTree<BinarySearchTreeType>::Add ( const BinarySearchTreeType& input, const char *file, unsigned int line )
        {
                typename BinarySearchTree::node * current;
                
                // Add the new element to the tree according to the following alogrithm:
                // 1.  If the current node is empty add the new leaf
                // 2.  If the element is less than the current node then go down the left branch
                // 3.  If the element is greater than the current node then go down the right branch
                
                if ( BinarySearchTree_size == 0 )
                {
                        BinarySearchTree_size = 1;
                        root = RakNet::OP_NEW<typename BinarySearchTree::node>( file, line );
                        root->item = RakNet::OP_NEW<BinarySearchTreeType>( file, line );
                        *( root->item ) = input;
                        root->left = 0;
                        root->right = 0;
                        
                        return root;
                }
                
                else
                {
                        // start at the root
                        current = root;

#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
                        while ( true )    // This loop traverses the tree to find a spot for insertion
                        {
                        
                                if ( input < *( current->item ) )
                                {
                                        if ( current->left == 0 )
                                        {
                                                current->left = RakNet::OP_NEW<typename BinarySearchTree::node>( file, line );
                                                current->left->item = RakNet::OP_NEW<BinarySearchTreeType>( file, line );
                                                current = current->left;
                                                current->left = 0;
                                                current->right = 0;
                                                *( current->item ) = input;
                                                
                                                BinarySearchTree_size++;
                                                return current;
                                        }
                                        
                                        else
                                        {
                                                current = current->left;
                                        }
                                }
                                
                                else
                                        if ( input > *( current->item ) )
                                        {
                                                if ( current->right == 0 )
                                                {
                                                        current->right = RakNet::OP_NEW<typename BinarySearchTree::node>( file, line );
                                                        current->right->item = RakNet::OP_NEW<BinarySearchTreeType>( file, line );
                                                        current = current->right;
                                                        current->left = 0;
                                                        current->right = 0;
                                                        *( current->item ) = input;
                                                        
                                                        BinarySearchTree_size++;
                                                        return current;
                                                }
                                                
                                                else
                                                {
                                                        current = current->right;
                                                }
                                        }
                                        
                                        else
                                                return 0; // ((input == current->item) == true) which is not allowed since the tree only takes discrete values.  Do nothing
                        }
                }
        }
        
        template <class BinarySearchTreeType>
        bool BinarySearchTree<BinarySearchTreeType>::IsIn( const BinarySearchTreeType& input )
        {
                typename BinarySearchTree::node * parent;
                find( input, &parent );
                
                if ( direction != NOT_FOUND )
                        return true;
                else
                        return false;
        }
        
        
        template <class BinarySearchTreeType>
        void BinarySearchTree<BinarySearchTreeType>::DisplayInorder( BinarySearchTreeType* return_array )
        {
                typename BinarySearchTree::node * current, *parent;
                bool just_printed = false;
                
                unsigned int index = 0;
                
                current = root;
                
                if ( BinarySearchTree_size == 0 )
                        return ; // Do nothing for an empty tree
                        
                else
                        if ( BinarySearchTree_size == 1 )
                        {
                                return_array[ 0 ] = *( root->item );
                                return ;
                        }
                        
                        
                direction = ROOT;  // Reset the direction
                
                while ( index != BinarySearchTree_size )
                {
                        // direction is set by the find function and holds the direction of the parent to the last node visited.  It is used to prevent revisiting nodes
                        
                        if ( ( current->left != 0 ) && ( direction != LEFT ) && ( direction != RIGHT ) )
                        {
                                //  Go left if the following 2 conditions are true
                                //  I can go left
                                //  I did not just move up from a right child
                                //  I did not just move up from a left child
                                
                                current = current->left;
                                direction = ROOT;  // Reset the direction
                        }
                        
                        else
                                if ( ( direction != RIGHT ) && ( just_printed == false ) )
                                {
                                        // Otherwise, print the current node if the following 3 conditions are true:
                                        // I did not just move up from a right child
                                        // I did not print this ndoe last cycle
                                        
                                        return_array[ index++ ] = *( current->item );
                                        just_printed = true;
                                }
                                
                                else
                                        if ( ( current->right != 0 ) && ( direction != RIGHT ) )
                                        {
                                                // Otherwise, go right if the following 2 conditions are true
                                                // I did not just move up from a right child
                                                // I can go right
                                                
                                                current = current->right;
                                                direction = ROOT;  // Reset the direction
                                                just_printed = false;
                                        }
                                        
                                        else
                                        {
                                                //  Otherwise I've done everything I can.  Move up the tree one node
                                                parent = FindParent( *( current->item ) );
                                                current = parent;
                                                just_printed = false;
                                        }
                }
        }
        
        template <class BinarySearchTreeType>
        void BinarySearchTree<BinarySearchTreeType>::DisplayPreorder( BinarySearchTreeType* return_array )
        {
                typename BinarySearchTree::node * current, *parent;
                
                unsigned int index = 0;
                
                current = root;
                
                if ( BinarySearchTree_size == 0 )
                        return ; // Do nothing for an empty tree
                        
                else
                        if ( BinarySearchTree_size == 1 )
                        {
                                return_array[ 0 ] = *( root->item );
                                return ;
                        }
                        
                        
                direction = ROOT;  // Reset the direction
                return_array[ index++ ] = *( current->item );
                
                while ( index != BinarySearchTree_size )
                {
                        // direction is set by the find function and holds the direction of the parent to the last node visited.  It is used to prevent revisiting nodes
                        
                        if ( ( current->left != 0 ) && ( direction != LEFT ) && ( direction != RIGHT ) )
                        {
                        
                                current = current->left;
                                direction = ROOT;
                                
                                // Everytime you move a node print it
                                return_array[ index++ ] = *( current->item );
                        }
                        
                        else
                                if ( ( current->right != 0 ) && ( direction != RIGHT ) )
                                {
                                        current = current->right;
                                        direction = ROOT;
                                        
                                        // Everytime you move a node print it
                                        return_array[ index++ ] = *( current->item );
                                }
                                
                                else
                                {
                                        //  Otherwise I've done everything I can.  Move up the tree one node
                                        parent = FindParent( *( current->item ) );
                                        current = parent;
                                }
                }
        }
        
        template <class BinarySearchTreeType>
        inline void BinarySearchTree<BinarySearchTreeType>::DisplayPostorder( BinarySearchTreeType* return_array )
        {
                unsigned int index = 0;
                
                if ( BinarySearchTree_size == 0 )
                        return ; // Do nothing for an empty tree
                        
                else
                        if ( BinarySearchTree_size == 1 )
                        {
                                return_array[ 0 ] = *( root->item );
                                return ;
                        }
                        
                DisplayPostorderRecursive( root, return_array, index );
        }
        
        
        // Recursively do a postorder traversal
        template <class BinarySearchTreeType>
        void BinarySearchTree<BinarySearchTreeType>::DisplayPostorderRecursive( typename BinarySearchTree::node* current, BinarySearchTreeType* return_array, unsigned int& index )
        {
                if ( current->left != 0 )
                        DisplayPostorderRecursive( current->left, return_array, index );
                        
                if ( current->right != 0 )
                        DisplayPostorderRecursive( current->right, return_array, index );
                        
                return_array[ index++ ] = *( current->item );
                
        }
        
        
        template <class BinarySearchTreeType>
        void BinarySearchTree<BinarySearchTreeType>::DisplayBreadthFirstSearch( BinarySearchTreeType* return_array )
        {
                typename BinarySearchTree::node * current;
                unsigned int index = 0;
                
                // Display the tree using a breadth first search
                // Put the children of the current node into the queue
                // Pop the queue, put its children into the queue, repeat until queue is empty
                
                if ( BinarySearchTree_size == 0 )
                        return ; // Do nothing for an empty tree
                        
                else
                        if ( BinarySearchTree_size == 1 )
                        {
                                return_array[ 0 ] = *( root->item );
                                return ;
                        }
                        
                        else
                        {
                                DataStructures::QueueLinkedList<node *> tree_queue;
                                
                                // Add the root of the tree I am copying from
                                tree_queue.Push( root );
                                
                                do
                                {
                                        current = tree_queue.Pop();
                                        return_array[ index++ ] = *( current->item );
                                        
                                        // Add the child or children of the tree I am copying from to the queue
                                        
                                        if ( current->left != 0 )
                                                tree_queue.Push( current->left );
                                                
                                        if ( current->right != 0 )
                                                tree_queue.Push( current->right );
                                                
                                }
                                
                                while ( tree_queue.Size() > 0 );
                        }
        }
        
        
        template <class BinarySearchTreeType>
        BinarySearchTree<BinarySearchTreeType>::BinarySearchTree( const BinarySearchTree& original_copy )
        {
                typename BinarySearchTree::node * current;
                // Copy the tree using a breadth first search
                // Put the children of the current node into the queue
                // Pop the queue, put its children into the queue, repeat until queue is empty
                
                // This is a copy of the constructor.  A bug in Visual C++ made it so if I just put the constructor call here the variable assignments were ignored.
                BinarySearchTree_size = 0;
                root = 0;
                
                if ( original_copy.BinarySearchTree_size == 0 )
                {
                        BinarySearchTree_size = 0;
                }
                
                else
                {
                        DataStructures::QueueLinkedList<node *> tree_queue;
                        
                        // Add the root of the tree I am copying from
                        tree_queue.Push( original_copy.root );
                        
                        do
                        {
                                current = tree_queue.Pop();
                                
                                Add ( *( current->item ), __FILE__, __LINE__ )
                                
                                ;
                                
                                // Add the child or children of the tree I am copying from to the queue
                                if ( current->left != 0 )
                                        tree_queue.Push( current->left );
                                        
                                if ( current->right != 0 )
                                        tree_queue.Push( current->right );
                                        
                        }
                        
                        while ( tree_queue.Size() > 0 );
                }
        }
        
        template <class BinarySearchTreeType>
        BinarySearchTree<BinarySearchTreeType>& BinarySearchTree<BinarySearchTreeType>::operator= ( const BinarySearchTree& original_copy )
        {
                typename BinarySearchTree::node * current;
                
                if ( ( &original_copy ) == this )
                        return *this;
                        
                Clear( __FILE__, __LINE__ );  // Remove the current tree
                
                // This is a copy of the constructor.  A bug in Visual C++ made it so if I just put the constructor call here the variable assignments were ignored.
                BinarySearchTree_size = 0;
                
                root = 0;
                
                
                // Copy the tree using a breadth first search
                // Put the children of the current node into the queue
                // Pop the queue, put its children into the queue, repeat until queue is empty
                if ( original_copy.BinarySearchTree_size == 0 )
                {
                        BinarySearchTree_size = 0;
                }
                
                else
                {
                        DataStructures::QueueLinkedList<node *> tree_queue;
                        
                        // Add the root of the tree I am copying from
                        tree_queue.Push( original_copy.root );
                        
                        do
                        {
                                current = tree_queue.Pop();
                                
                                Add ( *( current->item ), __FILE__, __LINE__ )
                                
                                ;
                                
                                // Add the child or children of the tree I am copying from to the queue
                                if ( current->left != 0 )
                                        tree_queue.Push( current->left );
                                        
                                if ( current->right != 0 )
                                        tree_queue.Push( current->right );
                                        
                        }
                        
                        while ( tree_queue.Size() > 0 );
                }
                
                return *this;
        }
        
        template <class BinarySearchTreeType>
        inline void BinarySearchTree<BinarySearchTreeType>::Clear ( const char *file, unsigned int line )
        {
                typename BinarySearchTree::node * current, *parent;
                
                current = root;
                
                while ( BinarySearchTree_size > 0 )
                {
                        if ( BinarySearchTree_size == 1 )
                        {
                                RakNet::OP_DELETE(root->item, file, line);
                                RakNet::OP_DELETE(root, file, line);
                                root = 0;
                                BinarySearchTree_size = 0;
                        }
                        
                        else
                        {
                                if ( current->left != 0 )
                                {
                                        current = current->left;
                                }
                                
                                else
                                        if ( current->right != 0 )
                                        {
                                                current = current->right;
                                        }
                                        
                                        else // leaf
                                        {
                                                // Not root node so must have a parent
                                                parent = FindParent( *( current->item ) );
                                                
                                                if ( ( parent->left ) == current )
                                                        parent->left = 0;
                                                else
                                                        parent->right = 0;
                                                        
                                                RakNet::OP_DELETE(current->item, file, line);
                                                
                                                RakNet::OP_DELETE(current, file, line);
                                                
                                                current = parent;
                                                
                                                BinarySearchTree_size--;
                                        }
                        }
                }
        }
        
} // End namespace

#endif

#ifdef _MSC_VER
#pragma warning( pop )
#endif