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

## 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 (const BinaryTree &other)
Copy constructor. More...

~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, bool sorted=false)
Inserts into the BinaryTree. 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 printPaths (vector< vector< T > > &paths) const
creates vectors of all the possible paths from the root of the tree to any leaf node and adds it to another vector. More...

int sumDistances () const
Each node in a tree has a distance from the root node - the depth of that node, or the number of edges along the path from that node to the root. More...

void inOrder (vector< T > &treeVector)
Uses vector to store values of the nodes of a binary tree in order. More...

## 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, bool sorted)
Private helper function for the 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, 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

template<typename T >
 BinaryTree< T >::BinaryTree ( )

Constructor to create an empty tree.

template<typename T >
 BinaryTree< T >::BinaryTree ( const BinaryTree< T > & other )

Copy constructor.

template<typename T >
 BinaryTree< T >::~BinaryTree ( )

Destructor; frees all nodes associated by this tree.

## Member Function Documentation

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
template<typename T >
 void BinaryTree< T >::clear ( )

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

template<typename T >
 void BinaryTree< T >::insert ( const T & elem, bool sorted = false )

Inserts into the BinaryTree.

Parameters
 elem The element to insert sorted By default, this parameter is false. That means that the element takes a pseudo-random path to a leaf where it is inserted. If true, the insert function will act like it does in a BST.
template<typename T >
 void BinaryTree< T >::print ( ) const

Prints the contents of the tree to stdout.

template<typename T >
 BinaryTree< T >::Node * BinaryTree< T >::getRoot ( ) const
Returns
The root of the binary tree
The root of the binary tree.
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.
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.

template<typename T >
 void BinaryTree< T >::mirror ( )

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

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.
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.
template<typename T >
 void BinaryTree< T >::printPaths ( vector< vector< T > > & paths ) const

creates vectors of all the possible paths from the root of the tree to any leaf node and adds it to another vector.

Path is, all sequences starting at the root node and continuing downwards, ending at a leaf node. Paths ending in a left node should be added before paths ending in a node further to the right.

Parameters
 paths vector of vectors that contains path of nodes
template<typename T >
 int BinaryTree< T >::sumDistances ( ) const

Each node in a tree has a distance from the root node - the depth of that node, or the number of edges along the path from that node to the root.

This function returns the sum of the distances of all nodes to the root node (the sum of the depths of all the nodes). Your solution should take O(n) time, where n is the number of nodes in the tree.

Returns
The sum of the distances of all nodes to the root
template<typename T >
 void BinaryTree< T >::inOrder ( 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
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
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
template<typename T >
 void BinaryTree< T >::insert ( Node *& node, const T & elem, bool sorted )
private

Private helper function for the public insert function.

Parameters
 node The current node in the recursion elem The element to insert sorted By default, this parameter is false. That means that the element takes a pseudo-random path to a leaf where it is inserted. If true, the insert function will act like it does in a BST.
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
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
template<typename T >
 void BinaryTree< T >::inOrder ( Node * subRoot, 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

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