BST< K, V > Class Template Reference

The BST class represents a linked-memory BST Tree. More...

#include <bst.h>

Public Member Functions
	BST ()
	Constructor to create an empty tree. More...
	BST (const BST &other)
	Copy constructor. More...
	~BST ()
	Destructor; frees all nodes associated with this tree. More...
const BST &	operator= (const BST &rhs)
	Assignment operator. More...
void	clear ()
	Frees all nodes associated with this tree and sets it to be empty. More...
int	height () const
void	insert (const K &key, const V &value)
	Inserts a key and value into the BST. More...
void	remove (const K &key)
	Removes a key from the BST. More...
V	find (const K &key)
	Finds an element in the BST tree. More...
void	printFunctionOrder (std::ostream &out=std::cout) const
	Prints the function calls to a stream. More...
void	print (std::ostream &out=std::cout, bool order=true) const
	Prints the BST to a stream. More...
void	setOutput (std::ostream &newOut)
	This function is used for grading. More...
std::vector< K >	getInorderTraversal () const
	Gets the in-order traversal of an BST tree's keys. More...
std::vector< K >	getPreorderTraversal () const
	Gets the pre-order traversal of an BST tree's keys. More...
std::vector< std::string >	getFunctionOrder () const

Detailed Description

template<class K, class V>
class BST< K, V >

The BST class represents a linked-memory BST Tree.

Template Parameters

K	the type of key stored in the tree
V	the type of value stored in the tree

Constructor & Destructor Documentation

BST() [1/2]

template<class K , class V >

BST< K, V >::BST

Constructor to create an empty tree.

BST() [2/2]

template<class K , class V >

BST< K, V >::BST

(

const BST< K, V > &

other

)

Copy constructor.

Parameters

other

The tree to copy

~BST()

template<class K , class V >

BST< K, V >::~BST

Destructor; frees all nodes associated with this tree.

Member Function Documentation

clear()

template<class K , class V >

void BST< K, V >::clear

Frees all nodes associated with this tree and sets it to be empty.

find()

template<class K , class V >

V BST< K, V >::find

(

const K &

key

)

Finds an element in the BST tree.

Parameters

key	The element to search for

Returns

The value stored for that key

getInorderTraversal()

template<class K , class V >

std::vector< K > BST< K, V >::getInorderTraversal

Gets the in-order traversal of an BST tree's keys.

getPreorderTraversal()

template<class K , class V >

std::vector< K > BST< K, V >::getPreorderTraversal

Gets the pre-order traversal of an BST tree's keys.

height()

template<class K , class V >

int BST< K, V >::height

Returns

The height of the binary tree. Recall that the height of a binary tree is just the length of the longest path from the root to a leaf, and that the height of an empty tree is -1.

insert()

template<class K , class V >

void BST< K, V >::insert	(	const K &	key,
		const V &	value
	)

Inserts a key and value into the BST.

Parameters

key	The key to insert
value	The value associated with the key

operator=()

template<class K , class V >

const BST< K, V > & BST< K, V >::operator=

(

const BST< K, V > &

rhs

)

Assignment operator.

Parameters

rhs	The tree to copy

Returns

A reference to the current tree

print()

template<class K , class V >

void BST< K, V >::print	(	std::ostream &	out = std::cout,
		bool	order = true
	)		const

Prints the BST to a stream.

Parameters

out	The stream to print to (default is stdout)

printFunctionOrder()

template<class K , class V >

void BST< K, V >::printFunctionOrder

(

std::ostream &

out = std::cout

)

const

Prints the function calls to a stream.

Parameters

out	The stream to print to (default is stdout)

remove()

template<class K , class V >

void BST< K, V >::remove

(

const K &

key

)

Removes a key from the BST.

The key is assumed to exist in the tree.

Parameters

key	The key to remove

setOutput()

template<class K , class V >

void BST< K, V >::setOutput

(

std::ostream &

newOut

)

This function is used for grading.

Parameters

newOut

The stream to print to

---

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

• base/src/bst.h
• base/src/bst.hpp
• base/src/bst_given.hpp