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) {
        cout << "Cannot insert a duplicate. Item is already in tree" << endl;
        return;
    } 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);
        } else if (key > root->key) {
            deleteNode(root->right);
        } else if (key == root->key){
            deleteNode(root);
        } */

        Delete(root, key);
        length--;
        return;
    }

}

template<class T>
void BinaryTree<T>::Delete(NodeType<T>* tree, T &item) {
    if (tree == NULL) {
        cout << "Cannot delete from an empty list." << endl;
        return;
    }
    if (item < tree->key) {
        Delete(tree->left, item);
    } else if (item > tree->key) {
        Delete(tree->right, item);
    } else {
        deleteNode(tree);
    }
}



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 data;
    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, data);
        tree->key = data;
        Delete(tree->left, data);
    }

}



/**
 * 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>::getRetrieve(T &key) {
    bool found;
    retrieve(root, key, found);

    if (!found) {
        cout << "Item not in tree." << endl;
    } else {
        cout << "Item found in tree." << endl;
    }
}

template<class T>
void BinaryTree<T>::preOrder() const {
    cout << "Pre-Order: ";
    preOrderPrint(root);
    cout << endl;
}

template<class T>
void BinaryTree<T>::preOrderPrint(NodeType<T>* tree) const {
    if (tree != NULL) {
        cout << tree->key << " ";
        preOrderPrint(tree->left);
        preOrderPrint(tree->right);
    }
}

template<class T>
void BinaryTree<T>::inOrder() const {
    cout << "In-Order: ";
    inOrderPrint(root);
    cout << endl;
}

template<class T>
void BinaryTree<T>::inOrderPrint(NodeType<T>* tree) const {
    if (tree != NULL) {
        inOrderPrint(tree->left);
        cout << tree->key << " ";
        inOrderPrint(tree->right);
    }
}

template<class T>
void BinaryTree<T>::postOrder() const {
    cout << "Post-order: ";
    postOrderPrint(root);
    cout << endl;
}

template<class T>
void BinaryTree<T>::postOrderPrint(NodeType<T>* tree) const {
    if (tree != NULL) {
        postOrderPrint(tree->left);
        postOrderPrint(tree->right);
        cout << tree->key << " ";
    }
}

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


template<class T>
int BinaryTree<T>::getNumSingleParent() {
    return getNumSingleParentHelper(root);
}

template<class T>
int BinaryTree<T>::getNumSingleParentHelper(NodeType<T>* tree) {
    int count = 0;
    if (tree != NULL) {
        if ((tree->left == NULL && tree->right != NULL) ||  (tree->left != NULL && tree->right == NULL)) {
            count++;
        }
        count = count + getNumSingleParentHelper(tree->right);
        count = count + getNumSingleParentHelper(tree->left);
    }
    return count;
}

template<class T>
int BinaryTree<T>::getNumLeafNodes() const {
    return getNumLeafNodesHelper(root);
}

template<class T>
int BinaryTree<T>::getNumLeafNodesHelper(NodeType<T>* tree) const {
    int count = 0;
    if (tree != NULL) {
        if (tree->right == NULL && tree->left == NULL) {
            count++;
        } else if (tree->right == NULL) {
            count = getNumLeafNodesHelper(tree->left);
        } else if (tree->left == NULL) {
            count = getNumLeafNodesHelper(tree->right);
        } else {
            count = count + getNumLeafNodesHelper(tree->right);
            count = count + getNumLeafNodesHelper(tree->left);
        }
    }
    return count;
}

/*
template <class T>
void BinaryTree<T>::getSumOfSubTrees(T &item) const {
    bool found;
    retrieve(root, item, found);

    if (!found) {
        cout << "Item is not in tree." << endl;
    } else {
        return getSumOfSubTreesHelper(root, item, 0);
    }
    return getSumOfSubTreesHelper(root, item, 0);
}
 */

/*
template <class T>
int BinaryTree<T>::getSumOfSubTreesHelper(NodeType<T>* tree, T &item, int count) const {
    if (tree != NULL) {
        int left = 0;
        int right = 0;
        left = getSumOfSubTreesHelper(tree->left, item, count);
        right = getSumOfSubTreesHelper(tree->right, item, count);
        int count = left + right;
        return count;
    }
    return 0;
}
 */


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