// Lab Problem 8.3 (a continuation of Problem 8.2)

// CS211 ADS2

// T Naughton, CS NUIM

#include<iostream>



/* This program uses an ordered binary tree to store integers. Integers

** are to be sorted in ascending order.

** The following methods are supported:

** -OrdIntTree::Add // Add an int to the tree at an appropriate pos

** -OrdIntTree::Print // Print out the integers in order

** -OrdIntTree::Contains // Return true/false if an int is in the tree

** -OrdIntTree::Delete // Delete the entire tree

**

** An extra method is included for testing purposes:

** -OrdIntTree::SeqContains // A (wasteful) exhaustive search of the tree

**

** The following methods are new to 8.3

** -OrdIntTree::PrintTree // Print the tree structure on its side

** -OrdIntTree::Remove // Remove an element from the tree

** -OrdIntTree::MinData // The minimum data value in the tree

** -OrdIntTree::RemoveMin // Remove the minimum data value

**

** All methods have recursive implementations.

*/



class BinTreeNode {

  // A very simple class describing each node of the binary tree

 public:

  int data; // data held at each node

  BinTreeNode * left; // pointer to left subtree

  BinTreeNode * right; // pointer to right subtree

};



class OrdIntTree {



  BinTreeNode * root; // a pointer to the root of the tree



 public:

  OrdIntTree(); // constructor

  ~OrdIntTree(); // destructor

  void SetRoot(BinTreeNode * ptr);

  BinTreeNode * GetRoot();



  // methods that act on OrdIntTree (wrapper methods that take

  // care of special cases or extra tasks before calling the

  // private recursive methods that do the real work)

  void Delete(); // delete the entire tree

  bool Contains(int value); // binary search to check if 'value' is in the tree

  void Print(); // print the sorted list of integers to the screen

  void Add(int newdata); // add a new element to the tree such that children

                         // to the left of a parent have lower integers and

                         // children to the right have higher or equal integers.

  bool SeqContains(int value); // a (wasteful) exhastive search of the tree

  void PrintTree(); // Print the tree structure on its side

  void Remove(int sdata); // Remove a given element from the tree whilst

                          // maintaining an ordered list of integers in the tree.

  int MinData(BinTreeNode * current); // Return the min data element in a subtree

  void RemoveMin(); // Remove node containing the min data element in a subtree



 private:

  // recursive implementations of the tasks

  void DeleteRec(BinTreeNode * current);

  bool ContainsRec(BinTreeNode * current, int value);

  void PrintRec(BinTreeNode * current);

  void AddRec(BinTreeNode * current, int newdata);

  bool SeqContainsRec(BinTreeNode * current, int value);

  void PrintTreeRec(BinTreeNode * current, int space);

  bool RemoveRec(BinTreeNode ** current, int sdata);

  void RemoveMinRec(BinTreeNode ** current);

};



OrdIntTree::OrdIntTree(){

  root = NULL; // Initialise the tree (set root to NULL).

}



OrdIntTree::~OrdIntTree(){

  Delete();

}



void OrdIntTree::SetRoot(BinTreeNode * ptr){

  root = ptr;

}



BinTreeNode * OrdIntTree::GetRoot(){

  return root;

}



void OrdIntTree::Delete(){

  // Wrapper method to delete a tree.

  // Although all memory (including that at the root of the tree) will

  // be deallocated correctly, we should also point the root pointer

  // away from this memory location. This means we can safely add new

  // nodes after deleting the tree

  DeleteRec(GetRoot());

  SetRoot(NULL);

}



void OrdIntTree::DeleteRec(BinTreeNode * current){

  // Recursive method to delete a tree. Deletes nodes from the leaves

  // to the root. Starts at rightmost node of lowest leftmost subtree

  if (current != NULL) {

    DeleteRec(current->left);

    DeleteRec(current->right);

    delete current;

  }

}



bool OrdIntTree::Contains(int value){

  // Wrapper method to perform a binary search for an int in the tree.

  // Does nothing extra, but means the user does not have to explicitly

  // pass the root of the tree when calling this method

  return ContainsRec(GetRoot(), value);

}



bool OrdIntTree::ContainsRec(BinTreeNode * current, int value){

  // Recursive method to perform a binary search for an element in an

  // ordered binary tree

  if (current == NULL) {

    return false;

  } else if (value == current->data) {

    return true;

  } else if (value < current->data) {

    return ContainsRec(current->left, value);

  } else {

    // value must be >= current->data

    return ContainsRec(current->right, value);

  }

}



void OrdIntTree::Print(){

  // Wrapper method to print out the integers in sorted order

  cout << endl << "Tree contains:";

  PrintRec(GetRoot());

}



void OrdIntTree::PrintRec(BinTreeNode * current){

  // Recursive method to print out the integers in sorted order

  if (current != NULL) {

    PrintRec(current->left);

    cout << current->data << ' ';

    PrintRec(current->right);

  }

}



void OrdIntTree::Add(int newdata){

  // Wrapper method for adding a node to the tree. The new integer is

  // positioned such that children to the left of a parent have lower

  // int values and children to the right have higher or equal int values.

  // This wrapper takes account of the special case where root==NULL before

  // calling the recursive method

  BinTreeNode * temp;



  if (GetRoot() == NULL) {

    temp = new BinTreeNode;

    temp->data = newdata;

    temp->left = NULL;

    temp->right = NULL;

    SetRoot(temp);



  } else {

    AddRec(GetRoot(), newdata);

  }

}



void OrdIntTree::AddRec(BinTreeNode * current, int newdata){

  // Recursive method for adding a node to the tree. The new integer is

  // positioned such that children to the left of a parent have lower

  // int values and children to the right have higher or equal int values.

  // A wrapper method ensures that current is not NULL

  BinTreeNode * temp;



  if (newdata < current->data) {

    // position to the left of current

    if (current->left == NULL) {

      temp = new BinTreeNode;

      temp->data = newdata;

      temp->left = NULL;

      temp->right = NULL;

      current->left = temp;

    } else {

      AddRec(current->left, newdata);

    }

  } else {

    //position to the right of current

    if (current->right == NULL) {

      temp = new BinTreeNode;

      temp->data = newdata;

      temp->left = NULL;

      temp->right = NULL;

      current->right = temp;

    } else {

      AddRec(current->right, newdata);

    }

  }

}



bool OrdIntTree::SeqContains(int value){

  // Wrapper method to perform a (wasteful) exhaustive search for an int

  // in the tree.

  // Does nothing extra, but means the user does not have to explicitly

  // pass the root of the tree when calling this method

  return SeqContainsRec(GetRoot(), value);

}



bool OrdIntTree::SeqContainsRec(BinTreeNode * current, int value){

  // Recursive method to perform a (wasteful) exhaustive search for an

  // element in a binary tree

  if (current == NULL) {

    return false;

  } else if (value == current->data) {

    return true;

  } else if (SeqContainsRec(current->left, value) ||

             SeqContainsRec(current->right, value)) {

    return true;

  }

}



void OrdIntTree::PrintTree(){

  // Wrapper method for printing the tree structure on its side

  cout << "\nHere is the tree:";

  PrintTreeRec(root, 0);

}



void OrdIntTree::PrintTreeRec(BinTreeNode * current, int space){

  // Print the tree structure on its side. Include symbols to indicate whether a

  // node has a left child (/), a right child (\), or two children (^)

  int count;

  if (current != NULL) {

    PrintTreeRec(current->right, space + 3);

    cout << endl;

    count = 0;

    while (count < space) {

      cout << ' ';

      count++;

    }

    cout << current->data;

    if ((current->left != NULL) && (current->right != NULL)) {

      cout << '<';

    } else if (current->left != NULL) {

      cout << '\\';

    } else if (current->right != NULL) {

      cout << '/';

    } else {

      // nothing for leaves

    }

    PrintTreeRec(current->left, space + 3);

  }

}



void OrdIntTree::Remove(int sdata){

  // Wrapper method for removing all nodes having a particular data value.

  // The recursive method will be called iteratively until no further such

  // data values are found

  while (RemoveRec(&root, sdata)) {

    //keep removing elements

  }

}



bool OrdIntTree::RemoveRec(BinTreeNode ** current, int sdata){

  // Recursive method to remove a node containing 'sdata' from the tree. The

  // five cases are: empty tree, sdata less than current->data, sdata greater

  // than current->data, sdata equal to current->data where current has two

  // children, and sdata equal to current->data where current has less than

  // two children. The address of 'current' is passed to avoid the need to

  // explicitly keep track of current's parent

  BinTreeNode * temp;

  if (*current == NULL) {

    return false;

  } else if (sdata < (*current)->data) {

    RemoveRec(&(*current)->left, sdata);

  } else if (sdata > (*current)->data) {

    RemoveRec(&(*current)->right, sdata);

  } else if (((*current)->left != NULL) && ((*current)->right != NULL)) {

    // two subtrees

    (*current)->data = MinData((*current)->right);

    RemoveMinRec(&(*current)->right);

    return true;

  } else {

    // one or zero subtrees

    temp = *current;

    if ((*current)->left != NULL) {

      *current = (*current)->left;

    } else {

      *current = (*current)->right;

    }

    delete temp;

    return true;

  }

}



int OrdIntTree::MinData(BinTreeNode * current){

  // Return the minimum data element of a given subtree

  if (current == NULL) {

    cout << "\nError: tree is empty.";

  } else if (current->left == NULL) {

    return current->data;

  } else {

    return MinData(current->left);

  }

}



void OrdIntTree::RemoveMin(){

  // Remove the node containing the minimum data value of the tree

  BinTreeNode * temp;

  if (root == NULL) {

    // do nothing

  } else {

    RemoveMinRec(&root);

  }

}



void OrdIntTree::RemoveMinRec(BinTreeNode ** current){

  // Remove the node containing the minimum data value of a given

  // subtree. The address of 'current' is passed to avoid the need

  // to explicitly keep track of current's parent

  BinTreeNode * temp;

  if (*current == NULL) {

    cout << "\nError: no min to delete.";

  } else if ((*current)->left == NULL) {

    temp = *current;

    *current = (*current)->right;

    delete temp;

  } else {

    RemoveMinRec(&(*current)->left);

  }

}



void main(void){



  OrdIntTree tree;



  cout << endl << endl;



  tree.Add(5);

  tree.Add(3);

  tree.Add(7);

  tree.Add(4);

  tree.Add(9);

  tree.Add(11);

  tree.Add(11);//2);

  tree.Add(8);

  tree.Add(1);

  tree.Add(6);

  tree.Add(10);



  tree.Print();

  tree.PrintTree();



  tree.RemoveMin();

  tree.RemoveMin();

  tree.RemoveMin();

  tree.PrintTree();



  tree.Remove(5);

  cout << "\nRemoving 5...";

  tree.PrintTree();

  tree.Remove(11);

  cout << "\nRemoving 11...";

  tree.Print();

  tree.Remove(4);

  cout << "\nRemoving 4...";

  tree.Print();

  tree.Add(1);

  tree.PrintTree();

}