BinaryTree< T > Class Template Reference

The BinaryTree class represents a templated linked-memory tree data structure. More...

#include <binarytree.h>

Collaboration diagram for BinaryTree< T >:

Classes
struct	Node
	Represents a tree node; that is, an element in a BinaryTree. More...

Public Member Functions
	BinaryTree ()
	Constructor to create an empty tree. More...
	BinaryTree (Node *heapNode)
	Constructor that wraps raw nodes as a BinaryTree class. More...
	BinaryTree (const BinaryTree &other)
	Copy constructor. More...
virtual	~BinaryTree ()
	Destructor; frees all nodes associated by this tree. More...
const BinaryTree &	operator= (const BinaryTree &rhs)
	Assignment operator. More...
void	clear ()
	Frees all nodes associated with this tree and sets it to be empty. More...
void	insert (const T &elem)
	Inserts into the BinaryTree in BST order. More...
void	insertRandom (const T &elem, std::mt19937 &rng)
	Inserts the given value into the BinaryTree, taking a random path to the leaf where it is inserted. More...
void	print () const
	Prints the contents of the tree to stdout. More...
Node *	getRoot () const
int	height () const
	This lab deals with the following six helper functions: More...
void	printLeftToRight () const
	Prints out the values of the nodes of a binary tree in order. More...
void	mirror ()
	Flips the tree over a vertical axis, modifying the tree itself (not creating a flipped copy). More...
bool	isOrderedIterative () const
	isOrdered() function iterative version More...
bool	isOrderedRecursive () const
	isOrdered() function recursive version More...
void	inOrder (std::vector< T > &treeVector)
	Uses vector to store values of the nodes of a binary tree in order. More...

Protected Attributes
Node *	root

Private Member Functions
int	height (const Node *subRoot) const
	Put your own private helper functions here. More...
void	printLeftToRight (const Node *subRoot) const
	Private helper function for the public printLeftToRight function. More...
void	insert (Node *&node, const T &elem)
	Private helper function for the sorted public insert function. More...
void	insertRandom (Node *&node, const T &elem, std::mt19937 &rng)
	Private helper function for the random public insert function. More...
Node *	copy (const Node *subRoot)
	Helper function for operator= and cctor. More...
void	clear (Node *subRoot)
	Private helper function for clear that clears beneath the parameter node. More...
void	inOrder (Node *subRoot, std::vector< T > &treeVector)
	Private helper function for the public inOrder function. More...

Detailed Description

template<typename T>
class BinaryTree< T >

The BinaryTree class represents a templated linked-memory tree data structure.

Constructor & Destructor Documentation

BinaryTree() [1/3]

template<typename T >

BinaryTree< T >::BinaryTree

(

)

Constructor to create an empty tree.

BinaryTree() [2/3]

template<typename T >

BinaryTree< T >::BinaryTree

(

Node *

heapNode

)

Constructor that wraps raw nodes as a BinaryTree class.

BinaryTree() [3/3]

template<typename T >

BinaryTree< T >::BinaryTree

(

const BinaryTree< T > &

other

)

Copy constructor.

~BinaryTree()

template<typename T >

BinaryTree< T >::~BinaryTree ( )

virtual

Destructor; frees all nodes associated by this tree.

Member Function Documentation

clear() [1/2]

template<typename T >

void BinaryTree< T >::clear

(

)

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

clear() [2/2]

template<typename T >

void BinaryTree< T >::clear ( BinaryTree< T >::Node *  subRoot )

private

Private helper function for clear that clears beneath the parameter node.

Parameters

subRoot

The current node in the recursion

copy()

template<typename T >

BinaryTree< T >::Node * BinaryTree< T >::copy ( const Node *  subRoot )

private

Helper function for operator= and cctor.

Parameters

subRoot

The current node in the recursion

getRoot()

template<typename T >

BinaryTree< T >::Node * BinaryTree< T >::getRoot

(

)

const

Returns

The root of the binary tree

The root of the binary tree.

height() [1/2]

template<typename T >

int BinaryTree< T >::height

(

)

const

This lab deals with the following six helper functions:

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.

height() [2/2]

template<typename T >

int BinaryTree< T >::height ( const Node *  subRoot ) const

private

Put your own private helper functions here.

Private helper function for the public height function.

Look at the private helpers for height and printLeftToRight as examples.Private helper function for the public height function.

Parameters

subRoot

The current node in the recursion

Returns

The height of the subtree

Parameters

subRoot

Returns

The height of the subtree

inOrder() [1/2]

template<typename T >

void BinaryTree< T >::inOrder

(

std::vector< T > &

treeVector

)

Uses vector to store values of the nodes of a binary tree in order.

That is, everything to the left of a node will be pushed before that node itself, and everything to the right of a node will be pushed after that node.

Parameters

treeVector

stores nodes in order

inOrder() [2/2]

template<typename T >

void BinaryTree< T >::inOrder ( BinaryTree< T >::Node *  subRoot, std::vector< T > &  treeVector  )

private

Private helper function for the public inOrder function.

Parameters

subRoot	The current node in the recursion
treeVector	stores nodes in order

insert() [1/2]

template<typename T >

void BinaryTree< T >::insert

(

const T &

elem

)

Inserts into the BinaryTree in BST order.

Parameters

elem	The element to insert

insert() [2/2]

template<typename T >

void BinaryTree< T >::insert ( Node *&  node, const T &  elem  )

private

Private helper function for the sorted public insert function.

Parameters

node	The current node in the recursion
elem	The element to insert

insertRandom() [1/2]

template<typename T >

void BinaryTree< T >::insertRandom	(	const T &	elem,
		std::mt19937 &	rng
	)

Inserts the given value into the BinaryTree, taking a random path to the leaf where it is inserted.

Parameters

elem	The element to insert
rng	The random number generator used to compute the path

insertRandom() [2/2]

template<typename T >

void BinaryTree< T >::insertRandom ( Node *&  node, const T &  elem, std::mt19937 &  rng  )

private

Private helper function for the random public insert function.

Parameters

node	The current node in the recursion
elem	The element to insert
rng	The random number generator used to compute the path

isOrderedIterative()

template<typename T >

bool BinaryTree< T >::isOrderedIterative

(

)

const

isOrdered() function iterative version

Returns

True if an in-order traversal of the tree would produce a nondecreasing list output values, and false otherwise. This is also the criterion for a binary tree to be a binary search tree.

isOrderedRecursive()

template<typename T >

bool BinaryTree< T >::isOrderedRecursive

(

)

const

isOrdered() function recursive version

Returns

True if an in-order traversal of the tree would produce a nondecreasing list output values, and false otherwise. This is also the criterion for a binary tree to be a binary search tree.

mirror()

template<typename T >

void BinaryTree< T >::mirror

(

)

Flips the tree over a vertical axis, modifying the tree itself (not creating a flipped copy).

operator=()

template<typename T >

const BinaryTree< T > & BinaryTree< T >::operator=

(

const BinaryTree< T > &

rhs

)

Assignment operator.

Parameters

rhs	The tree to make a copy of

Returns

A reference to the current tree

print()

template<typename T >

void BinaryTree< T >::print

(

)

const

Prints the contents of the tree to stdout.

printLeftToRight() [1/2]

template<typename T >

void BinaryTree< T >::printLeftToRight

(

)

const

Prints out the values of the nodes of a binary tree in order.

That is, everything to the left of a node will be printed out before that node itself, and everything to the right of a node will be printed out after that node.

printLeftToRight() [2/2]

template<typename T >

void BinaryTree< T >::printLeftToRight ( const Node *  subRoot ) const

private

Private helper function for the public printLeftToRight function.

Parameters

subRoot	The current node in the recursion
subRoot

---

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

• binarytree.h
• binarytree.cpp
• binarytree_given.cpp