#include "tree.h"
//****************************************************************************
//
// Function: Tree()
//
// Purpose: create an empty tree
//
// Parameters:
//
// Calls: none
//
//****************************************************************************
Tree::Tree()
{
root = NULL;
}
//****************************************************************************
//
// Function: set_root
//
// Purpose: searches the vector to find the root
//
// Parameters: holder - container of the nodes
//
// Calls: function begin, new
//
//****************************************************************************
void Tree::set_root(vector <Name>& holder)
{
vector<Name>::iterator iter = holder.begin();
while(iter -> three != "") //worst case run time is if the
{ //iterator had to visit all nodes
++iter; //space complexity is one iterator
}
root = new Bnode(iter -> one, iter -> two);
}
//****************************************************************************
//
// Function: make_tree
//
// Purpose: takes the info in the vector and creates a binary tree
//
// Parameters: the_root - the current root of the tree
// holder - the container of the nodes
//
// Calls: function begin, end, make_tree
//
//****************************************************************************
void Tree::make_tree(Bnode * the_root, vector <Name>& holder)
{
vector<Name>::iterator iter = holder.begin();
while((iter != holder.end()) &&
(iter -> one != the_root -> data))
{ //worst case run time will be twice the number of nodes
++iter; //iterator may have to check n nodes then recursively visit
} //n nodes. space complexity is number of nodes because
//the recursion puts the functions of the runtime stack
if((iter != holder.end()) && (iter -> two != "NULL"))
{
the_root -> left = new Bnode(iter -> two);
make_tree(the_root -> left, holder);
}
if((iter != holder.end()) && (iter -> three != "NULL"))
{
the_root -> right = new Bnode(iter -> three);
make_tree(the_root -> right, holder);
}
}
//****************************************************************************
//
// Function: get_root_at_left
//
// Purpose: returns pointer to the child of the root
//
// Parameters:
//
// Calls: none
//
//****************************************************************************
Bnode* Tree::get_root_at_left()
{
return root -> left;
}
//****************************************************************************
//
// Function: print
//
// Purpose: prints node data as post order traversal
//
// Parameters: the_root - current root of the tree
//
// Calls: function print
//
//****************************************************************************
void Tree::print(Bnode * the_root)
{
if(the_root != NULL) //runtime is number of nodes because each node is
{ //visited once
print(the_root -> left);
print(the_root -> right);
cout << the_root -> data << endl;
}
}
//****************************************************************************
//
// Function: get_depth
//
// Purpose: finds maximum depth of binary tree
//
// Parameters: the_root - current root of the tree
// height - this is the depth of the tree
//
// Calls: function get_depth
//
//****************************************************************************
int Tree::get_depth(Bnode * the_root, int height)
{
if(the_root != NULL) //worst case runtime is number of nodes
{ //space complexity is number of nodes
height = get_depth(the_root -> left, --height);
height = get_depth(the_root -> right, height--);
height++;
}
else
{
if(height <= 0)
{
height = 0;
}
}
return height;
}
//****************************************************************************
//
// Function: get_nary_depth
//
// Purpose: finds depth of n-ary tree
//
// Parameters: the_root - current root of the tree
// height - this is the depth of the tree
//
// Calls: function get_nary_depth
//
//****************************************************************************
int Tree::get_nary_depth(Bnode * the_root, int height)
{
if(the_root == NULL) //worst case runtime is number of nodes
{ //space complexity is number of nodes
return 0;
}
else
{
height = get_nary_depth(the_root -> left, height);
height = get_nary_depth(the_root -> left, height);
height ++;
}
return height;
}