Untitled

#include <iostream>
#include <string>
#include "BinaryTree.h"

using namespace std;

/**
* Constructor.
* Binary tree is initialized.
*/
template <class T>
BinaryTree<T>::BinaryTree() {
    root = NULL;
    length = 0;
}

/**
* Destructor.
* All node pointers freed and root points to NULL.
*/
template <class T>
BinaryTree<T>::~BinaryTree() {
    freeNodes(root);
}

/**
 * freeNodes.
 * Delete tree nodes recursively.
 * Helper method for ~BinaryTree().
 */
template <class T>
void BinaryTree<T>::freeNodes(NodeType<T>* &tree) {
    if (tree != NULL) {
        freeNodes(tree->left);
        freeNodes(tree->right);
        delete tree;
    }
}

/**
 * insert.
 * Insert a node with the value of key into the tree.
 * No duplicates are allowed.
 */


template <class T>
void BinaryTree<T>::insert(T &key) {
        insertNode(root, key);
        length++;
}


/**
 * insertNode.
 * insert a Node into the right position recursively.
 * Helper method for insert
 */


template <class T>
void BinaryTree<T>::insertNode(NodeType<T>* &tree, T &key) {
    if (tree == NULL) {
        tree = new NodeType<T>;
        tree->right = NULL;
        tree->left = NULL;
        tree->key = key;
    } else if (key < tree->key) {
        insertNode(tree->left, key);
    } else {
        insertNode(tree->right, key);
    }
}



/**
 * deleteItem
 * Remove a node with a key value equal to the parameters key value
 * Otherwise leave the tree unchanged
 * In situations where the node has to be deleted has two children.
 * replace the deletedNode with its immediate predecessor or successor
 */


template <class T>
void BinaryTree<T>::deleteItem(T &key) {
    bool found;
    retrieve(root, key, found);

    if (!found) {
        cout << "Item is not found!" << endl;
        return;
    } else {
        if (key < root->key) {
            deleteNode(root->left, key);
        } else if (key > root->key) {
            deleteNode(root->right, key);
        } else {
            deleteNode(root, key);
        }
        length--;
    }
}



template<class T>
void BinaryTree<T>::getPredecessor(NodeType<T>* &tree, T &item) {
    while (tree->right != NULL) {
        tree = tree->right;
    }
    item = tree->key;
}

template<class T>
void BinaryTree<T>::deleteNode(NodeType<T>* &tree, T &item) {
    T tempItem;
    NodeType<T>* 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, tempItem);
        tree->key = tempItem;
        deleteNode(tree->left, tempItem);
    }
}



/**
 * Item should refer to a key of a Node n in the tree where the value of
 * n.key is equal to the value of item
 * Found is true if n exists otherwise false
 */


template<class T>
void BinaryTree<T>::retrieve(NodeType<T>* &tree, T &item, bool &found) const {
    if (tree == NULL) {
        found = false;
    } else if (item < tree->key) {
        retrieve(tree->left, item, found);
    } else if (item > tree->key) {
        retrieve(tree->right, item, found);
    } else {
        item = tree->key;
        found = true;
    }
}


template<class T>
void BinaryTree<T>::preOrder() const {

}

template<class T>
void BinaryTree<T>::inOrder() const {

}

template<class T>
void BinaryTree<T>::postOrder() const {

}

template<class T>
int BinaryTree<T>::getLength() const {
    return length;
}

template class BinaryTree<int>;
template class BinaryTree<float>;
template class BinaryTree<std::string>;