BinaryTree< T > Class Template Reference

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

#include "binarytree.h"

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 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, bool sorted=false)
	Inserts into the BinaryTree. More...
void	print () const
	Prints the contents of the tree to stdout. More...
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	isOrdered () const
	Private helper function for the public isOrdered function. More...
void	printPaths () const
	Prints out all the possible paths from the root of the tree to any leaf node. 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...

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 >

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 >

BinaryTree< T >::Node * BinaryTree< T >::mirror

(

)

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

Private helper function for the public mirror function.

Parameters

subRoot

The current node in the recursion

template<typename T >

bool BinaryTree< T >::isOrdered

(

)

const

Private helper function for the public isOrdered function.

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.

Parameters

subRoot

Returns

Whether the subtree is ordered or not

template<typename T >

void BinaryTree< T >::printPaths

(

)

const

Prints out all the possible paths from the root of the tree to any leaf node.

Private helper function for the public printPaths function.

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

Parameters

node	The current node in the recursion
path	An aggregated path to the current node

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.

Private helper function for the public sumDistances function.

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

Parameters

node	The current node in the recursion
numchildren	Used to count how many children there are in a subtree.

---

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

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