BST< ElemType > Class Template Reference

#include "bst.h"

List of all members.

Public Member Functions
	BST (int(cmpFn)(ElemType one, ElemType two)=OperatorCmp)
	~BST ()
int	size ()
bool	isEmpty ()
ElemType *	find (ElemType key)
bool	add (ElemType elem)
bool	remove (ElemType key)
void	clear ()
void	mapAll (void(fn)(ElemType elem))
template<typename ClientDataType>
void	mapAll (void(fn)(ElemType elem, ClientDataType &data), ClientDataType &data)
const BST &	operator= (const BST &rhs)
	BST (const BST &rhs)
template<typename ElemType>
void	mapAll (void(fn)(ElemType))
template<typename ClientDataType>
void	mapAll (void(fn)(ElemType, ClientDataType &), ClientDataType &data)
Classes
struct	nodeT

---

Detailed Description

template<typename ElemType>
class BST< ElemType >

This interface defines a class template for a binary search tree. For maximum generality, the BST is supplied as a class template. The element type is set by the client. The client specializes the tree for specific type, e.g. BST<int> or BST<studentT>. The one requirement on the element type is that the client must supply a comparison fn that compares two elements (or be willing to use the default comparison function that relies on < and ==).

---

Constructor & Destructor Documentation

template<typename ElemType>

BST< ElemType >::BST

(

int(cmpFn)(ElemType one, ElemType two)

= OperatorCmp

)

The constructor initializes a new empty binary search tree. The one argument is a comparison function, which is called to compare data values. This argument is optional, if not given, the OperatorCmp function from cmpfn.h is used, which applies the built-in operator < to its operands. If the behavior of < on your ElemType is defined and sufficient, you do not need to supply your own comparison function.

template<typename ElemType>

BST< ElemType >::~BST

(

)

The destructor deallocates storage for this tree.

template<typename ElemType>

BST< ElemType >::BST

(

const BST< ElemType > &

rhs

)

---

Member Function Documentation

template<typename ElemType>

int BST< ElemType >::size

(

)

This member function returns the number of elements in this tree.

template<typename ElemType>

bool BST< ElemType >::isEmpty

(

)

This member function returns true if this tree contains no elements, false otherwise.

template<typename ElemType>

ElemType * BST< ElemType >::find

(

ElemType

key

)

This member function applies the binary search algorithm to find a particular key in this tree. The second argument is the key to use for comparison. If a node matching key appears in the tree, find returns a pointer to the data in that node; otherwise, find returns NULL.

template<typename ElemType>

bool BST< ElemType >::add

(

ElemType

elem

)

This member function adds a new node to this tree. The elem argument is compared with the data in existing nodes to find the proper position. If a node with the same value already exists, the contents are overwritten with the new copy and false is returned. If no matching node is found, a new node is allocated and added to the tree, true is returned.

template<typename ElemType>

bool BST< ElemType >::remove

(

ElemType

key

)

This member function removes a node in this tree that matches the specified key. If a node matching key is found, the node is removed from the tree and true is returned. If no match is found, no changes are made and false is returned.

template<typename ElemType>

void BST< ElemType >::clear

(

)

This member function removes all elements from this tree. The tree is made empty and will have no nodes after being cleared.

template<typename ElemType>

void BST< ElemType >::mapAll

(

void(fn)(ElemType elem)

)

This member function iterates through this tree and calls the function fn once for each element. The order is determined by an InOrder walk of the tree.

template<typename ElemType>

template<typename ClientDataType>

void BST< ElemType >::mapAll	(	void(fn)(ElemType elem, ClientDataType &data)	,
		ClientDataType &	data
	)

This member function iterates through this tree con and calls the function fn once for each element, passing the element and the client's data. That data can be of whatever type is needed for the client's callback. The order of calls is determined by an InOrder walk of the tree.

template<typename ElemType>

const BST< ElemType > & BST< ElemType >::operator=

(

const BST< ElemType > &

rhs

)

This copy constructor and operator= are defined to make a deep copy, making it possible to pass/return trees by value and assign from one tree to another. The entire contents of the tree, including all elements, are copied. Each tree element is copied from the original tree to the copy using assignment (operator=). Making copies is generally avoided because of the expense and thus, trees are typically passed by reference, however, when a copy is needed, these operations are supported.

template<typename ElemType>

template<typename ElemType>

void BST< ElemType >::mapAll

(

void(fn)(ElemType)

)

The mapAll function is implemented as a wrapper to the recursive function recMapAll, which does the actual work of calling the function on all values during an InOrder walk.

template<typename ElemType>

template<typename ClientDataType>

void BST< ElemType >::mapAll	(	void(fn)(ElemType, ClientDataType &)	,
		ClientDataType &	data
	)

---

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

• bst.h

---