// Lab Problem 11.1 (contains 11A.1, 11B.1, 11C.1)

// CS211 ADS2

// T Naughton, CS NUIM

// 28 Apr 2000

#include<iostream>



/* This program contains solutions (sometimes multiple solutions) to

** lab exam problems 11A.1, 11B.1, and 11C.1.

** In order to test the solutions I use a basic binary tree class.

**

** The lab exam questions were as follows:

** 11A.1 Write a method for an ordered binary tree that returns the depth of

** the smallest element in the tree.

** 11B.1 Write a method for an ordered binary tree that returns the number of

** leaf nodes in the tree.

** 11C.1 Write a method for an ordered binary tree that returns the contents

** of the leaf node with the highest value.

*/



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

  void Delete(); // delete the entire tree

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

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

  int SmHtA(); // 11A.1

  int SmHtB(); // 11A.1

  int SmHtC(); // 11A.1

  int NumLf(); // 11B.1

  void HiLf(); // 11C.1

 private:

  // recursive implementations of the tasks

  void DeleteRec(BinTreeNode * current);

  void AddRec(BinTreeNode * current, int newdata);

  void PrintTreeRec(BinTreeNode * current, int depth);

  int SmHtARec(BinTreeNode * current, int height); // 11A.1

  int SmHtBRec(BinTreeNode * current); // 11A.1

  int SmHtCRec(BinTreeNode * current); // 11A.1

  int NumLfRec(BinTreeNode * current); // 11B.1

  int HiLfRec(BinTreeNode * current); // 11C.1

};

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;

  }

}

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

    }

  }

}

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 depth){

  // 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, depth + 1);

    cout << endl;

    count = 0;

    while (count < (depth * 3)) {

      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, depth + 1);

  }

}





/*

** Here are three possible solutions to 11A.1, labelled A, B, and C

*/

int OrdIntTree::SmHtA(){

  if (root == NULL) {

    return 0;

  } else {

    return SmHtARec(root, 0);

  }

}

int OrdIntTree::SmHtARec(BinTreeNode * current, int height){

  if (current->left == NULL) {

    return height;

  } else {

    return SmHtARec(current->left, height + 1);

  }

}



int OrdIntTree::SmHtB(){

  if (root == NULL) {

    return 0;

  } else {

    return SmHtCRec(root);

  }

}

int OrdIntTree::SmHtBRec(BinTreeNode * current){

  if (current->left == NULL) {

    return 0;

  } else {

    return (1 + SmHtBRec(current->left));

  }

}



int OrdIntTree::SmHtC(){

  return SmHtCRec(root);

}

int OrdIntTree::SmHtCRec(BinTreeNode * current){

  if (current == NULL) {

    return 0;

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

    return 0;

  } else {

    return (1 + SmHtCRec(current->left));

  }

}



/*

** Here is a solution to 11B.1

*/

int OrdIntTree::NumLf(){

  return NumLfRec(root);

}

int OrdIntTree::NumLfRec(BinTreeNode * current){

  if (current == NULL) {

    return 0;

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

    return 1;

  } else {

    return (NumLfRec(current->left) + NumLfRec(current->right));

  }

}



/*

** Here is a solution 11C.1

*/

void OrdIntTree::HiLf(){

  if (root == NULL) {

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

  } else {

    cout << "\nHighest leaf value is " << HiLfRec(root);

  }

}

int OrdIntTree::HiLfRec(BinTreeNode * current){

  // Traverse tree from right to left and halt when the first leaf is

  // encountered

  if (current == NULL) {

    //do nothing

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

    return current->data;

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

    return HiLfRec(current->left);

  } else {

    return HiLfRec(current->right);

  }

}



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

  tree.Add(8);

  tree.Add(1);

//  tree.Add(6);

//  tree.Add(10);



  tree.PrintTree();

  cout << "\nHeight of smallest is: ";

  cout << tree.SmHtA() << ' ' << tree.SmHtB() << ' ' << tree.SmHtC();



  cout << "\nNumber of leaves is: " << tree.NumLf();



  tree.HiLf();

}