treetype.cpp

#include <iostream>
#include <vector>
#include "TreeType.h"
#include "QueType.h"
using namespace std;

void Destroy(TreeNode*& tree);
void Retrieve(TreeNode* tree, ItemType& item, bool& found);
void Insert(TreeNode*& tree, ItemType item);
void Delete(TreeNode*& tree, ItemType item);
void DeleteNode(TreeNode*& tree);
int CountNodes(TreeNode* root);
void PrintTree(TreeNode* tree, std::ofstream& outFile);
void PreOrder(TreeNode*, QueType&); // Enqueues tree items in preorder.
void InOrder(TreeNode*, QueType&); // Enqueues tree items in inorder.
void PostOrder(TreeNode*, QueType&); // Enqueues tree items in postorder.
void CopyTree(TreeNode*& copy, const TreeNode* originalTree);
bool IsFullTreeHelper(TreeNode * root);
int GetNodesHelper (TreeNode * root, vector<ItemType> itemArray, int level);
void PrintAncestorsHelper(TreeNode * root,ItemType value);
bool IsBSTHelper(TreeNode * root);
void GetSmallestHelper(TreeNode * root, ItemType & smallest);

struct TreeNode
{
  ItemType info;
  TreeNode* left;
  TreeNode* right;
};


TreeType::TreeType()
{
}


TreeType::~TreeType()
// Calls recursive function Destroy to destroy the tree.
{
  Destroy(root);
}



ItemType TreeType::GetItem(ItemType item, bool& found)
// Calls recursive function Retrieve to search the tree for item.
{
  Retrieve(root, item, found);
  return item;
}

void Retrieve(TreeNode* tree, ItemType& item, bool& found)
// Recursively searches tree for item.
// Post: If there is an element someItem whose key matches item's,
//       found is true and item is set to a copy of someItem;
//       otherwise found is false and item is unchanged.
{
  if (tree == NULL)
    found = false;                     // item is not found.
  else if (item < tree->info)
    Retrieve(tree->left, item, found); // Search left subtree.
  else if (item > tree->info)
    Retrieve(tree->right, item, found);// Search right subtree.
  else
  {
    item = tree->info;                 // item is found.
    found = true;
   }
}


void TreeType::PutItem(ItemType item)
// Calls recursive function Insert to insert item into tree.
{
  Insert(root, item);
}

void Insert(TreeNode*& tree, ItemType item)
// Inserts item into tree.
// Post:  item is in tree; search property is maintained.
{
  if (tree == NULL)
  {// Insertion place found.
    tree = new TreeNode;
    tree->right = NULL;
    tree->left = NULL;
    tree->info = item;
  }
  else if (item < tree->info)
    Insert(tree->left, item);    // Insert in left subtree.
  else
    Insert(tree->right, item);   // Insert in right subtree.
}

void TreeType::DeleteItem(ItemType item)
// Calls recursive function Delete to delete item from tree.
{
  Delete(root, item);
}


void Delete(TreeNode*& tree, ItemType item)
// Deletes item from tree.
// Post:  item is not in tree.
{
  if (item < tree->info)
    Delete(tree->left, item);   // Look in left subtree.
  else if (item > tree->info)
    Delete(tree->right, item);  // Look in right subtree.
  else
    DeleteNode(tree);           // Node found; call DeleteNode.
}

void GetSuccessor(TreeNode* tree, ItemType& data)
// Sets data to the info member of the right-most node in tree.
{
  while (tree->left != NULL)
    tree = tree->left;
  data = tree->info;
}

void DeleteNode(TreeNode*& tree)
// Deletes the node pointed to by tree.
// Post: The user's data in the node pointed to by tree is no
//       longer in the tree.  If tree is a leaf node or has only
//       non-NULL child pointer the node pointed to by tree is
//       deleted; otherwise, the user's data is replaced by its
//       logical predecessor and the predecessor's node is deleted.
{
  ItemType data;
  TreeNode* tempPtr;

  tempPtr = tree;
  if (tree->left == NULL)
  {
    tree = tree->right;
    delete tempPtr;
  }
  else if (tree->right == NULL)
  {
    tree = tree->left;
    delete tempPtr;
  }
  else
  {
//    GetPredecessor(tree->left, data);
  //  tree->info = data;
    //Delete(tree->left, data);  // Delete predecessor node.
    GetSuccessor(tree->right, data);
    tree->info = data;
    Delete(tree->right, data);


  }
}

int TreeType::GetLength() const
// Calls recursive function CountNodes to count the
// nodes in the tree.
{

  return CountNodes(root);
}

int CountNodes(TreeNode* tree)

// Post: returns the number of nodes in the tree.

{

  if (tree == NULL)

    return 0;

  else

    return CountNodes(tree->left) + CountNodes(tree->right) + 1;

}

bool TreeType::IsEmpty() const
// Returns true if the tree is empty; false otherwise.
{
  return root == NULL;
}

bool TreeType::IsFull() const
// Returns true if there is no room for another item
//  on the free store; false otherwise.
{
  TreeNode* location;
  try
  {
    location = new TreeNode;
    delete location;
    return false;
  }
  catch(std::bad_alloc exception)
  {
    return true;
  }
}

void TreeType::Print(std::ofstream& outFile) const
// Calls recursive function Print to print items in the tree.
{
  PrintTree(root, outFile);
}

void PrintTree(TreeNode* tree, std::ofstream& outFile)
// Prints info member of items in tree in sorted order on outFile.
{
  if (tree != NULL)
  {
    PrintTree(tree->left, outFile);   // Print left subtree.
    outFile << tree->info;
    PrintTree(tree->right, outFile);  // Print right subtree.
  }
}



void TreeType::ResetTree(OrderType order)
// Calls function to create a queue of the tree elements in
// the desired order.
{
  switch (order)
  {
    case PRE_ORDER : PreOrder(root, preQue);
                     break;
    case IN_ORDER  : InOrder(root, inQue);
                     break;
    case POST_ORDER: PostOrder(root, postQue);
                     break;
  }
}

void PreOrder(TreeNode* tree, QueType& preQue)
// Post: preQue contains the tree items in preorder.
{
  if (tree != NULL)
  {
    preQue.Enqueue(tree->info);
    PreOrder(tree->left, preQue);
    PreOrder(tree->right, preQue);
  }
}


void InOrder(TreeNode* tree, QueType& inQue)
// Post: inQue contains the tree items in inorder.
{
  if (tree != NULL)
  {
    InOrder(tree->left, inQue);
    inQue.Enqueue(tree->info);
    InOrder(tree->right, inQue);
  }
}

void PostOrder(TreeNode* tree, QueType& postQue)
// Post: postQue contains the tree items in postorder.
{
  if (tree != NULL)
  {
    PostOrder(tree->left, postQue);
    PostOrder(tree->right, postQue);
    postQue.Enqueue(tree->info);
  }
}

ItemType TreeType::GetNextItem(OrderType order, bool& finished)
// Returns the next item in the desired order.
// Post: For the desired order, item is the next item in the queue.
//       If item is the last one in the queue, finished is true;
//       otherwise finished is false.
{
  finished = false;
  ItemType item;
  switch (order)
  {
    case PRE_ORDER  : preQue.Dequeue(item);
                      if (preQue.IsEmpty())
                        finished = true;
                      break;
    case IN_ORDER   : inQue.Dequeue(item);
                      if (inQue.IsEmpty())
                        finished = true;
                      break;
    case  POST_ORDER: postQue.Dequeue(item);
                      if (postQue.IsEmpty())
                        finished = true;
                      break;
  }
  return item;
}

void Destroy(TreeNode*& tree)
// Post: tree is empty; nodes have been deallocated.
{
  if (tree != NULL)
  {
    Destroy(tree->left);
    Destroy(tree->right);
    delete tree;
  }
}

void TreeType::MakeEmpty()
{
  Destroy(root);
  root = NULL;
}

TreeType::TreeType(const TreeType& originalTree)
// Calls recursive function CopyTree to copy originalTree
//  into root.
{
  CopyTree(root, originalTree.root);
}

void TreeType::operator= (const TreeType& originalTree)
// Calls recursive function CopyTree to copy originalTree
// into root.
{
  {
  if (&originalTree == this)
    return;             // Ignore assigning self to self
  Destroy(root);      // Deallocate existing tree nodes
  CopyTree(root, originalTree.root);
  }

}
void CopyTree(TreeNode*& copy, const TreeNode* originalTree)
// Post: copy is the root of a tree that is a duplicate
//       of originalTree.
{
  if (originalTree == NULL)
    copy = NULL;
  else
  {
    copy = new TreeNode;
    copy->info = originalTree->info;
    CopyTree(copy->left, originalTree->left);
    CopyTree(copy->right, originalTree->right);
  }
}

bool TreeType::IsFullTree()
{
    IsFullTreeHelper(root);
}

bool IsFullTreeHelper(TreeNode * root)
{
    // If empty tree
    if (root == NULL)
        return true;

    // If leaf node
    if (root->left == NULL && root->right == NULL)
        return true;

    // If both left and right are not NULL, and left & right subtrees
    // are full
    if ((root->left) && (root->right))
        return (IsFullTreeHelper(root->left) && IsFullTreeHelper(root->right));

    // We reach here when none of the above if conditions work
    return false;
}

bool IsBSTHelper(TreeNode * root)
{
    static TreeNode *prev = NULL;

    // traverse the tree in inorder fashion
    // and keep track of prev node
    if (root)
    {
        if (!IsBSTHelper(root->left))
        return false;

        // Allows only distinct valued nodes
        if (prev != NULL &&
            root->info <= prev->info)
        return false;

        prev = root;

        return IsBSTHelper(root->right);
    }

    return true;
}

bool TreeType::IsBST()
{
    IsBSTHelper(root);
}

/* return the number of nodes in the given level, itemArray[0...] stores the items values
 precondition: level >= 0
 //itemarray must be already allocated
*/

int GetNodesHelper (TreeNode * root, vector<ItemType> itemArray, int level)
{
    if(level == 0 )
    {
        //itemArray
        itemArray.push_back(root->info);
        for(int i = 0; i<=itemArray.size(); i++)
        {
            cout<<itemArray[i];
        }

        return 1;
    }
    else
    {
        level--;
       return GetNodesHelper(root->left, itemArray, level) + GetNodesHelper(root->right, itemArray, level);
    }
}

int TreeType::GetNodesAtLevel (vector<ItemType> itemArray, int level)
{
    GetNodesHelper(root, itemArray, level);
}


//Display the items stored in the parent of the node, the grandparent, and so on
//starting from root (ancestor of all nodes), ... all the way to the parent of the node
void PrintAncestorsHelper (TreeNode * root,ItemType value) //helper function
{
    if (root == NULL)
    {
        cout<<"tree is empty";
        return;
    }

    if (root->info == value)
    {
        cout << root->info << " ";
        return;
    }

    PrintAncestorsHelper(root->left, value);
    PrintAncestorsHelper(root->right, value);
}

void TreeType::PrintAncestors(ItemType value)
{
    PrintAncestorsHelper(root, value);
}

//Add this helper function if you want to implement the walking recursively
//this is a static member function (which does not have calling object).
void TreeType::GetSmallest (ItemType & smallest) //this is the helper function
{
    GetSmallestHelper(root, smallest);
}

void GetSmallestHelper(TreeNode * root, ItemType & smallest)
{
    TreeNode* current =root;
   /* loop down to find the leftmost leaf */
   while (current->left != NULL)
    {
        current = current->left;
    }
    smallest = current->info;
    cout<<smallest<<" ";

}