// Lab Problem 8.2 (contains solutions to Problems 7.3 and 8.1)

// 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

**

** 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



 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);

};



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 main(void){



  OrdIntTree tree;



  cout << endl << endl;



  tree.Add(5);

  tree.Add(4);

  tree.Add(7);

  tree.Add(4);

  tree.Add(4);

  tree.Add(5);

  tree.Add(5);



  tree.Print();



  cout << endl << "Tree does ";

  if (!tree.Contains(4)) { cout << "not "; }

  cout << "contain 4.";

  cout << endl << "Tree does ";

  if (!tree.SeqContains(4)) { cout << "not "; }

  cout << "contain 4.";



  cout << endl << "Tree does ";

  if (!tree.Contains(45)) { cout << "not "; }

  cout << "contain 45.";

  cout << endl << "Tree does ";

  if (!tree.SeqContains(45)) { cout << "not "; }

  cout << "contain 45.";



  tree.Delete();

  tree.Print();

  tree.Add(7);

  tree.Add(6);

  tree.Print();

}