The BinaryTree class represents a templated linked-memory tree data structure.
More...
#include "binarytree.h"
|
| 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 |
|
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...
|
|
|
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...
|
|
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, vector< T > &treeVector) |
| Private helper function for the public inOrder function. More...
|
|
template<typename T>
class BinaryTree< T >
The BinaryTree class represents a templated linked-memory tree data structure.
Constructor to create an empty tree.
Destructor; frees all nodes associated by this tree.
Assignment operator.
- Parameters
-
rhs | The tree to make a copy of |
- Returns
- A reference to the current tree
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. |
Prints the contents of the tree to stdout.
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.
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.
Flips the tree over a vertical axis, modifying the tree itself (not creating a flipped copy).
- 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 |
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 |
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
-
- Returns
- The height of the subtree
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. |
Helper function for operator= and cctor.
- Parameters
-
subRoot | The current node in the recursion |
Private helper function for clear that clears beneath the parameter node.
- Parameters
-
subRoot | The current node in the recursion |
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: