DataStructures::BinarySearchTree< BinarySearchTreeType > Class Template Reference

A binary search tree and an AVL balanced binary search tree. More...

#include <DS_BinarySearchTree.h>

Inheritance diagram for DataStructures::BinarySearchTree< BinarySearchTreeType >:

List of all members.

Classes
struct	node
Public Member Functions
node *	Add (const BinarySearchTreeType &input, const char *file, unsigned int line)
	BinarySearchTree ()
	BinarySearchTree (const BinarySearchTree &original_type)
void	Clear (const char *file, unsigned int line)
node *	Del (const BinarySearchTreeType &input, const char *file, unsigned int line)
void	DisplayBreadthFirstSearch (BinarySearchTreeType *return_array)
void	DisplayInorder (BinarySearchTreeType *return_array)
void	DisplayPostorder (BinarySearchTreeType *return_array)
void	DisplayPreorder (BinarySearchTreeType *return_array)
BinarySearchTreeType *&	GetPointerToNode (const BinarySearchTreeType &element)
unsigned int	Height (node *starting_node=0)
bool	IsIn (const BinarySearchTreeType &input)
BinarySearchTree &	operator= (const BinarySearchTree &original_copy)
unsigned int	Size (void)
virtual	~BinarySearchTree ()
Protected Types
enum	Direction_Types { NOT_FOUND, LEFT, RIGHT, ROOT }
Protected Member Functions
void	DisplayPostorderRecursive (node *current, BinarySearchTreeType *return_array, unsigned int &index)
node *&	Find (const BinarySearchTreeType &element, node **parent)
node *&	FindParent (const BinarySearchTreeType &element)
void	FixTree (node *current)
unsigned int	HeightRecursive (node *current)
Protected Attributes
unsigned int	BinarySearchTree_size
enum DataStructures::BinarySearchTree::Direction_Types	direction
node *	root

---

Detailed Description

template<class BinarySearchTreeType>
class DataStructures::BinarySearchTree< BinarySearchTreeType >

Initilize with the following structure

BinarySearchTree<TYPE>

OR

AVLBalancedBinarySearchTree<TYPE>

Use the AVL balanced tree if you want the tree to be balanced after every deletion and addition. This avoids the potential worst case scenario where ordered input to a binary search tree gives linear search time results. It's not needed if input will be evenly distributed, in which case the search time is O (log n). The search time for the AVL balanced binary tree is O (log n) irregardless of input.

Has the following member functions unsigned int Height(<index>) - Returns the height of the tree at the optional specified starting index. Default is the root add(element) - adds an element to the BinarySearchTree bool del(element) - deletes the node containing element if the element is in the tree as defined by a comparison with the == operator. Returns true on success, false if the element is not found bool IsInelement) - returns true if element is in the tree as defined by a comparison with the == operator. Otherwise returns false DisplayInorder(array) - Fills an array with an inorder search of the elements in the tree. USER IS REPONSIBLE FOR ALLOCATING THE ARRAY!. DisplayPreorder(array) - Fills an array with an preorder search of the elements in the tree. USER IS REPONSIBLE FOR ALLOCATING THE ARRAY!. DisplayPostorder(array) - Fills an array with an postorder search of the elements in the tree. USER IS REPONSIBLE FOR ALLOCATING THE ARRAY!. DisplayBreadthFirstSearch(array) - Fills an array with a breadth first search of the elements in the tree. USER IS REPONSIBLE FOR ALLOCATING THE ARRAY!. clear - Destroys the tree. Same as calling the destructor unsigned int Height() - Returns the height of the tree unsigned int size() - returns the size of the BinarySearchTree GetPointerToNode(element) - returns a pointer to the comparision element in the tree, allowing for direct modification when necessary with complex data types. Be warned, it is possible to corrupt the tree if the element used for comparisons is modified. Returns NULL if the item is not found

EXAMPLE

 BinarySearchTree<int> A;
 A.Add(10);
 A.Add(15);
 A.Add(5);
 int* array = RakNet::OP_NEW<int >(A.Size(), _FILE_AND_LINE_ );
 A.DisplayInorder(array);
 array[0]; // returns 5
 array[1]; // returns 10
 array[2]; // returns 15

compress - reallocates memory to fit the number of elements. Best used when the number of elements decreases

clear - empties the BinarySearchTree and returns storage The assignment and copy constructors are defined

Note:

The template type must have the copy constructor and assignment operator defined and must work with >, <, and == All elements in the tree MUST be distinct The assignment operator is defined between BinarySearchTree and AVLBalancedBinarySearchTree as long as they are of the same template type. However, passing a BinarySearchTree to an AVLBalancedBinarySearchTree will lose its structure unless it happened to be AVL balanced to begin with Requires queue_linked_list.cpp for the breadth first search used in the copy constructor, overloaded assignment operator, and display_breadth_first_search.

Definition at line 89 of file DS_BinarySearchTree.h.

---

Member Enumeration Documentation

template<class BinarySearchTreeType>

enum DataStructures::BinarySearchTree::Direction_Types [protected]

Enumerator:

NOT_FOUND
LEFT
RIGHT
ROOT

Definition at line 121 of file DS_BinarySearchTree.h.

        {
            NOT_FOUND, LEFT, RIGHT, ROOT
        } direction;

---

Constructor & Destructor Documentation

template<class BinarySearchTreeType >

DataStructures::BinarySearchTree< BinarySearchTreeType >::BinarySearchTree

(

)

Definition at line 412 of file DS_BinarySearchTree.h.

    {
        BinarySearchTree_size = 0;
        root = 0;
    }

template<class BinarySearchTreeType >

DataStructures::BinarySearchTree< BinarySearchTreeType >::~BinarySearchTree

(

)

[virtual]

Definition at line 419 of file DS_BinarySearchTree.h.

References _FILE_AND_LINE_.

    {
        this->Clear(_FILE_AND_LINE_);
    }

template<class BinarySearchTreeType >

DataStructures::BinarySearchTree< BinarySearchTreeType >::BinarySearchTree

(

const BinarySearchTree< BinarySearchTreeType > &

original_type

)

Definition at line 978 of file DS_BinarySearchTree.h.

References _FILE_AND_LINE_, cat::Atomic::Add(), DataStructures::BinarySearchTree< BinarySearchTreeType >::BinarySearchTree_size, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, DataStructures::QueueLinkedList< QueueType >::Pop(), DataStructures::QueueLinkedList< QueueType >::Push(), DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right, DataStructures::BinarySearchTree< BinarySearchTreeType >::root, and DataStructures::QueueLinkedList< QueueType >::Size().

    {
        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_AND_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 );
        }
    }

---

Member Function Documentation

template<class BinarySearchTreeType >

BinarySearchTree< BinarySearchTreeType >::node * DataStructures::BinarySearchTree< BinarySearchTreeType >::Add	(	const BinarySearchTreeType &	input,
		const char *	file,
		unsigned int	line
	)

Definition at line 675 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

Referenced by DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::Add().

    {
        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 >

void DataStructures::BinarySearchTree< BinarySearchTreeType >::Clear	(	const char *	file,
		unsigned int	line
	)		[inline]

Definition at line 1077 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, RakNet::OP_DELETE(), and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

    {
        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--;
                    }
            }
        }
    }

template<class BinarySearchTreeType >

BinarySearchTree< BinarySearchTreeType >::node * DataStructures::BinarySearchTree< BinarySearchTreeType >::Del	(	const BinarySearchTreeType &	input,
		const char *	file,
		unsigned int	line
	)

Definition at line 537 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, RakNet::OP_DELETE(), and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

Referenced by DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::Del().

    {
        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_AND_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 >

void DataStructures::BinarySearchTree< BinarySearchTreeType >::DisplayBreadthFirstSearch

(

BinarySearchTreeType *

return_array

)

Definition at line 931 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, DataStructures::QueueLinkedList< QueueType >::Pop(), DataStructures::QueueLinkedList< QueueType >::Push(), DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right, and DataStructures::QueueLinkedList< QueueType >::Size().

    {
        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 >

void DataStructures::BinarySearchTree< BinarySearchTreeType >::DisplayInorder

(

BinarySearchTreeType *

return_array

)

Definition at line 770 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

    {
        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 DataStructures::BinarySearchTree< BinarySearchTreeType >::DisplayPostorder

(

BinarySearchTreeType *

return_array

)

[inline]

Definition at line 897 of file DS_BinarySearchTree.h.

    {
        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 );
    }

template<class BinarySearchTreeType >

void DataStructures::BinarySearchTree< BinarySearchTreeType >::DisplayPostorderRecursive	(	typename BinarySearchTree< BinarySearchTreeType >::node *	current,
		BinarySearchTreeType *	return_array,
		unsigned int &	index
	)		[protected]

Definition at line 917 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

    {
        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 DataStructures::BinarySearchTree< BinarySearchTreeType >::DisplayPreorder

(

BinarySearchTreeType *

return_array

)

Definition at line 841 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

    {
        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>

node*& DataStructures::BinarySearchTree< BinarySearchTreeType >::Find	(	const BinarySearchTreeType &	element,
		node **	parent
	)		[protected]

template<class BinarySearchTreeType >

BinarySearchTree< BinarySearchTreeType >::node *& DataStructures::BinarySearchTree< BinarySearchTreeType >::FindParent

(

const BinarySearchTreeType &

element

)

[protected]

Definition at line 497 of file DS_BinarySearchTree.h.

    {
        static typename BinarySearchTree::node * parent;
        Find ( element, &parent );
        return parent;
    }

template<class BinarySearchTreeType >

void DataStructures::BinarySearchTree< BinarySearchTreeType >::FixTree

(

typename BinarySearchTree< BinarySearchTreeType >::node *

current

)

[protected]

Definition at line 506 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

    {
        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 >

BinarySearchTreeType *& DataStructures::BinarySearchTree< BinarySearchTreeType >::GetPointerToNode

(

const BinarySearchTreeType &

element

)

Definition at line 425 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item.

    {
        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 >

unsigned int DataStructures::BinarySearchTree< BinarySearchTreeType >::Height

(

typename BinarySearchTree< BinarySearchTreeType >::node *

starting_node = 0

)

Definition at line 382 of file DS_BinarySearchTree.h.

    {
        if ( BinarySearchTree_size == 0 || starting_node == 0 )
            return 0;
        else
            return HeightRecursive( starting_node );
    }

template<class BinarySearchTreeType >

unsigned int DataStructures::BinarySearchTree< BinarySearchTreeType >::HeightRecursive

(

typename BinarySearchTree< BinarySearchTreeType >::node *

current

)

[protected]

Definition at line 392 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

    {
        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 >

bool DataStructures::BinarySearchTree< BinarySearchTreeType >::IsIn

(

const BinarySearchTreeType &

input

)

Definition at line 757 of file DS_BinarySearchTree.h.

    {
        typename BinarySearchTree::node * parent;
        find( input, &parent );
        
        if ( direction != NOT_FOUND )
            return true;
        else
            return false;
    }

template<class BinarySearchTreeType >

BinarySearchTree< BinarySearchTreeType > & DataStructures::BinarySearchTree< BinarySearchTreeType >::operator=

(

const BinarySearchTree< BinarySearchTreeType > &

original_copy

)

Definition at line 1023 of file DS_BinarySearchTree.h.

References _FILE_AND_LINE_, cat::Atomic::Add(), DataStructures::BinarySearchTree< BinarySearchTreeType >::BinarySearchTree_size, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, DataStructures::QueueLinkedList< QueueType >::Pop(), DataStructures::QueueLinkedList< QueueType >::Push(), DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right, DataStructures::BinarySearchTree< BinarySearchTreeType >::root, and DataStructures::QueueLinkedList< QueueType >::Size().

    {
        typename BinarySearchTree::node * current;
        
        if ( ( &original_copy ) == this )
            return *this;
            
        Clear( _FILE_AND_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_AND_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 >

unsigned int DataStructures::BinarySearchTree< BinarySearchTreeType >::Size

(

void

)

Definition at line 376 of file DS_BinarySearchTree.h.

    {
        return BinarySearchTree_size;
    }

---

Member Data Documentation

template<class BinarySearchTreeType>

unsigned int DataStructures::BinarySearchTree< BinarySearchTreeType >::BinarySearchTree_size [protected]

Definition at line 126 of file DS_BinarySearchTree.h.

Referenced by DataStructures::BinarySearchTree< BinarySearchTreeType >::BinarySearchTree(), and DataStructures::BinarySearchTree< BinarySearchTreeType >::operator=().

template<class BinarySearchTreeType>

enum DataStructures::BinarySearchTree::Direction_Types DataStructures::BinarySearchTree< BinarySearchTreeType >::direction [protected]

template<class BinarySearchTreeType>

node* DataStructures::BinarySearchTree< BinarySearchTreeType >::root [protected]

Definition at line 119 of file DS_BinarySearchTree.h.

Referenced by DataStructures::BinarySearchTree< BinarySearchTreeType >::BinarySearchTree(), and DataStructures::BinarySearchTree< BinarySearchTreeType >::operator=().

---

The documentation for this class was generated from the following file:

• DS_BinarySearchTree.h