lab_trees
Tempestuous Trees
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 >:
[legend]

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 BinaryTreeoperator= (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...
 
NodegetRoot () 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

Noderoot
 

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...
 
Nodecopy (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
subRootThe 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
subRootThe 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
subRootThe 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
treeVectorstores 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
subRootThe current node in the recursion
treeVectorstores nodes in order

◆ insert() [1/2]

template<typename T >
void BinaryTree< T >::insert ( const T &  elem)

Inserts into the BinaryTree in BST order.

Parameters
elemThe 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
nodeThe current node in the recursion
elemThe 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
elemThe element to insert
rngThe 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
nodeThe current node in the recursion
elemThe element to insert
rngThe 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
rhsThe 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
subRootThe current node in the recursion
subRoot

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