#include <tree.h>
Public Member Functions | |
Tree () | |
create empty tree | |
Tree (Node *, int) | |
create new tree with passed node as the new main root. | |
~Tree () | |
destructor | |
void | insert (const elements &, int) |
inserts a new node as child of current | |
void | remove (Node *) |
deletes a node and its subtree | |
Tree (const Tree &) | |
copy constructor | |
elements | value () const |
value function | |
nid | Id () const |
Id function. | |
void | left () |
navigate the tree go left | |
void | right () |
go right | |
void | parent () |
go the the parent | |
void | reset () |
void | SetCurrent (Node *) |
set placement of the current pointer | |
Node * | pointer_left () const |
return subtree (node) pointers returns pointer to left child | |
Node * | pointer_right () const |
returns pointer to right child | |
Node * | pointer_parent () const |
returns pointer to parent | |
Node * | pointer_current () const |
returns current pointer | |
Node * | root () const |
returns pointer to root of Tree | |
elements | peek_left () const |
return values of children and parent without leaving current node returns elements of left child | |
elements | peek_right () const |
returns elements of right child | |
elements | peek_parent () const |
returns elements of parent | |
void | DisplayInorder (Node *) const |
print the tree or a subtree. print an "in-order" traversal | |
void | DisplayPreorder (Node *) const |
print a "pre-order" traversal | |
void | DisplayPostorder (Node *) const |
print a "post-order" traversal | |
void | clear () |
delete all nodes in the tree | |
bool | IsEmpty () const |
check to see if the tree is empty or full | |
bool | IsFull () const |
checks to see if tree is full | |
Private Member Functions | |
Node * | CopyTree (Node *, Node *) const |
create a new copy of a subtree if passed to the constructor | |
Private Attributes | |
Node * | current |
pointer to current Node | |
Node * | main_root |
pointer to the root of the Tree | |
bool | subtree |
does it reference a part of a larger object? |
Tree::Tree | ( | ) |
create empty tree
creates tree with default root node which has no value. set current to main root node.
Tree::Tree | ( | Node * | , | |
int | ||||
) |
create new tree with passed node as the new main root.
set current to main root. if the second parameter is 0, the new object simply points to the node of the original tree. If the second parameter is 1, a new copy of the subtree is created, which the object points to.
Node* | indicates root location | |
int | indicates where object points to (0: node of original tree, 1: new subtree) |
Tree::~Tree | ( | ) |
destructor
calls the clear function to recursively remove subtrees
< delete all nodes
Tree::Tree | ( | const Tree & | ) |
void Tree::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
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
root | pointer to root of tree | |
parent | pointer to parent of Node |
< 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.
nid Tree::Id | ( | ) | const |
void Tree::insert | ( | const elements & | , | |
int | ||||
) |
inserts a new node as child of current
inserts a new element into tree at desired position.
elements& | list<element> that should be inserted into tree | |
int | indicates position that node should be inserted (0: left 1:right) |
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 is left child, copy the id of the parent
< push_back the value one (we're creating a new level)
< else, 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
< increment the last element by one (we're on the same level)
pos | insert as child of current 0=left 1=right. if item already exists, replace it |
bool Tree::IsEmpty | ( | ) | const |
check to see if the tree is empty or full
< If there aren't any nodes in the tree, main_root points to NULL
elements Tree::peek_left | ( | ) | const |
return values of children and parent without leaving current node returns elements of left child
advantage: we don't have to leave the node! (self-explanatory)
void Tree::remove | ( | Node * | ) |
deletes a node and its subtree
recursively removes the node pointed to by Node* and all of its subtress
Node* | points to root of tree that is 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 Tree::reset | ( | ) |
go to main_root
void Tree::SetCurrent | ( | Node * | ) |
set placement of the current pointer
Node* | points to location that current should be set to |