#include <tree.h>
Public Member Functions | |
SuperTree () | |
create empty tree | |
SuperTree (SuperNode *, int) | |
create new tree with passed node as the new main root. | |
~SuperTree () | |
destructor | |
void | insert (int, int, nid, bool) |
insert new node as child of current. | |
void | insert (SuperTree &, SuperTree &) |
overloaded insert fuction | |
void | remove (SuperNode *) |
delete a node and its subtree | |
int | value () const |
value function | |
nid | Id () const |
Id function. | |
void | left () |
navigate the tree go to left child | |
void | right () |
go to right child | |
void | parent () |
go to parent | |
void | reset () |
void | SetCurrent (SuperNode *) |
set the location of the current pointer | |
SuperTree (const SuperTree &) | |
copy constructor | |
SuperNode * | pointer_left () const |
return subtree (node) pointers returns pointer to left child | |
SuperNode * | pointer_right () const |
returns pointer to right child | |
SuperNode * | pointer_parent () const |
returns pointer to parent | |
SuperNode * | pointer_current () const |
returns current pointer | |
SuperNode * | root () const |
returns pointer to main_root | |
int | peek_left () const |
return values of children and parent without leaving current node return taxa of left child | |
int | peek_right () const |
return taxa of right child | |
int | peek_parent () const |
return taxa of parent | |
void | DisplayInorder (SuperNode *) const |
print the tree or a subtree. do an "in-order" traversal | |
void | DisplayPreorder (SuperNode *) const |
do a "pre-order" traversal | |
void | DisplayPostorder (SuperNode *) const |
void | Newick (list< string > &, SuperNode *) |
displays newick format of tree | |
void | clear () |
delete all nodes in the tree | |
bool | IsEmpty () const |
checks to see if a tree is empty | |
bool | IsFull () const |
checks to see if the tree is full | |
bool | IsInternal () const |
checks to see the current node is an internal node | |
Private Member Functions | |
SuperNode * | CopyTree (SuperNode *, SuperNode *) const |
create a new copy of a subtree if passed to the constructor | |
SuperNode * | CopyTree (SuperNode *, SuperNode *, int) const |
CopyTree created for personal devices. | |
Private Attributes | |
SuperNode * | current |
pointer to current node | |
SuperNode * | main_root |
pointer to root node | |
bool | subtree |
does it reference a part of a larger object? |
SuperTree::SuperTree | ( | ) |
create empty tree
creates empty tree with default root node which has no value. set current to main root node.
SuperTree::SuperTree | ( | SuperNode * | , | |
int | ||||
) |
create new tree with passed node as the new main root.
set current to main root.
SuperNode* | node to set as root of tree | |
int | indicates where object should point to (0: node of original tree 1: new copy of the subtree |
SuperTree::~SuperTree | ( | ) |
destructor
< delete all nodes
SuperTree::SuperTree | ( | const SuperTree & | ) |
void SuperTree::clear | ( | ) |
delete all nodes in the tree
< use the remove function on the main root
< since there are no more items, set main_root to NULL
CopyTree created for personal devices.
Does same thing as the one above, accept is created for own devices sets the ids of all the internal nodes to -1
root | pointer to root of SuperTree | |
parent | pointer to parent of SuperNode | |
dummy | just a dummy value to indicate a new function (boo! bad coding practice!) |
< base case - if the node doesn't exist, return NULL.
< make a new location in memory
< make a copy of the node's data
< set the new node's parent
< copy the left subtree of the current node. pass the current node as the subtree's parent
< do the same with the right subtree
< what makes this function different from the other one!
< return a pointer to the newly created node.
create a new copy of a subtree if passed to the constructor
The second parameter is a pointer to the parent of the subtree being passed. Since parent of the main root is always NULL, we pass NULL as the second parameter in the class constructor
< base case - if the node doesn't exist, return NULL.
< make a new location in memory
< make a copy of the node's data
< set the new node's parent
< copy the left subtree of the current node. pass the current node as the subtree's parent
< do the same with the right subtree
< return a pointer to the newly created node.
void SuperTree::DisplayPostorder | ( | SuperNode * | ) | const |
do a "post-order" traversal
nid SuperTree::Id | ( | ) | const |
Id function.
overloaded insert fuction
inserts a right and left supertree as subtrees
< if the tree has no nodes, make a root node, disregard pos.
< node created, exit the function
right | insert left and right subtrees |
void SuperTree::insert | ( | int | , | |
int | , | |||
nid | , | |||
bool | ||||
) |
insert new node as child of current.
insert new taxa into supertree:
int | taxa (-1 or 0 if it is an internal node) | |
int | location to insert (0=left 1=right 2 = parent) | |
nid | id of Node to be inserted (-1 if is an internal node) | |
bool | indicates whether or not the node is internal |
if the tree has no nodes, make a root node, disregard pos.
< node created, exit the function
< if new node is a left child of current
< if child already exists, replace value
< if it is a left child, copy the id of the parent
< else if new node is a right child of current
< if child already exists, replace value
< if it is a right child, copy the id of the parent
bool SuperTree::IsEmpty | ( | ) | const |
checks to see if a tree is empty
< If there aren't any nodes in the tree, main_root points to NULL
void SuperTree::Newick | ( | list< string > & | , | |
SuperNode * | ||||
) |
displays newick format of tree
recrusively outputs the tree in Newick format
list<string>& | contains tree so far in Newick format | |
SuperNode* | pointer to root of tree we want to output in Newick format |
int SuperTree::peek_left | ( | ) | const |
return values of children and parent without leaving current node return taxa of left child
advantage: we don't have to leave the node! (self-explanatory)
void SuperTree::remove | ( | SuperNode * | ) |
delete a node and its subtree
recursively deletes the node pointed to by SuperNode and all the nodes in its subtree
SuperNode* | indicates root of tree to be deleted |
< base case - if the root doesn't exist, do nothing
< perform the remove operation on the nodes left subtree first
< perform the remove operation on the nodes right subtree first
< if the main root is being deleted, main_root must be set to NULL
< make sure the parent of the subtree's root points to NULL, since the node no longer exists
< set current to the parent of the subtree removed.
void SuperTree::reset | ( | ) |
go to main_root
void SuperTree::SetCurrent | ( | SuperNode * | ) |
set the location of the current pointer
SuperNode* | location that current pointer should be set to |
int SuperTree::value | ( | ) | const |
value function