BinarySearchTree.h - VTC C++ Binary Search Tree

/**
 * [BinarySearchTree.h]
 * The BinarySearchTree class declaration/specification.
 */

#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

#include "LinkedQueue.h"
#include <iostream>

/**
 * OrderType ENUM:
 * Used to specify the order in which the tree must be traversed:
 *
 * Pre-order traversal:
 * The node itself is visited first, then all the nodes in the left sub-tree, then all the nodes in
 * the right sub-tree.
 *
 * In-order traversal:
 * All the nodes in the left sub-tree are visited first, then the node itself, then all the nodes in
 * the right sub-tree.
 *
 * Post-order traversal:
 * All the nodes in the left sub-tree are visited first, then all the nodes in the right sub-tree,
 * then the node itself.
 */
enum OrderType { PRE_ORDER, IN_ORDER, POST_ORDER };

/**
 * TreeNode STRUCTURE:
 * Used to created nodes for the tree.
 */
template <class ItemType>
struct TreeNode
{
    ItemType    element;
    TreeNode    *left;
    TreeNode    *right;
};


template <class ItemType>
class BinarySearchTree
{
    /**
     * Everything under public can be accessed by all other programs or classes.
     */
    public:
        /**
         * Constructor(s):
         */
        BinarySearchTree();

        /**
         * Destructor:
         */
        ~BinarySearchTree();

        /**
         * Mutators:
         */
        void InsertItem(ItemType);
        void DeleteItem(ItemType);

        /**
         * Accessors:
         */
        void RetrieveItem(ItemType &, bool &);
        void GetNextItem(ItemType &, OrderType, bool &);

        /**
         * General Use:
         */
        void MakeEmpty(void);
        bool IsEmpty(void);
        bool IsFull(void);
        int NumberOfNodes(void);
        void ResetTree(OrderType order);
        void PrintTree(void);


    /**
     * Everything under protected can be accessed only by the class itself or (derived) subclasses,
     * as in the case of inheritance.
     */
    protected:


    /**
     * (Private) DATA MEMBERS/PROPERTIES:
     *
     * Everything under private can only be accessed by the class itself (the code in the
     * implementation file).
     */
    private:
        TreeNode<ItemType>      *root;
        LinkedQueue<ItemType>   preQueue;
        LinkedQueue<ItemType>   postQueue;
        LinkedQueue<ItemType>   inQueue;
};

#endif // BINARYSEARCHTREE_H


/**
 * The BinarySearchTree class definition/implementation.
 */

/**
 * BinarySearchTree CLASS CONSTRUCTOR(s):
 */
template <class ItemType>
BinarySearchTree<ItemType>::BinarySearchTree()
{
    root = 0;   // nullifies the root of the tree
}


/**
 * BinarySearchTree CLASS MUTATORS:
 */
template <class ItemType>
void BinarySearchTree<ItemType>::InsertItem(ItemType item)
{
    /**
     * To insert an item into the tree, code will be implemented to do a recursive search, starting
     * at its root, and check if the item is bigger or smaller than each item therein.
     *
     * While the item is still smaller, the search will continue to the left, until the condition is
     * false (a null value is found), then the item will be inserted.
     */
    Insert(root, item);
}

template <class ItemType>
void BinarySearchTree<ItemType>::DeleteItem(ItemType item)
{
    /**
     * To delete an item from the tree, code will be implemented to do a recursive search, starting
     * at its root, and check if the item is bigger or smaller than each item therein.
     *
     * While the item is still smaller, the search will continue on the left, until the condition is
     * is met (either the items are equal or the item is not found (the item is not longer smaller
     * or a null value is reached)).
     *
     * The same technique will be used to search on the right side of the tree if the item is larger.
     *
     * If the item is found, the tree will be passed to an auxiliary function that will perform the
     * deletion (of the node containing the found item).
     */
    Delete(root, item);
}


/**
 * BinarySearchTree CLASS ACCESSORS:
 */
template <class ItemType>
void BinarySearchTree<ItemType>::RetrieveItem(ItemType &item, bool &found)
{
    /**
     * To retrieve an item from the tree, code will be implemented to do a recursive search, starting
     * at it its root, and check if the item either exists, is bigger or smaller than each item in
     * the tree, or, in the case where only one item exists in the tree, if it is equal to the item
     * being searched for.
     *
     * While the item is still smaller, the search will continue to the left, until the condition is
     * if it is found.  In such a case, the founded item and the true boolean variable will be
     * returned.  Otherwise, false will be returned.
     */
    Retrieve(root, item, found);
}

template <class ItemType>
void BinarySearchTree<ItemType>::GetNextItem(ItemType &item, OrderType order, bool &done)
{
    done = false;   // logical

        switch(order)
        {
            case PRE_ORDER:     // if the item must be retrieved using the pre-order method...
                preQueue.Dequeue(item); // ...get the item from the pre-queue

                    if(preQueue.IsEmpty()) done = true;     // if the pre-queue is empty (the item is not found), set 'done' to true as an indication
                break;

            case IN_ORDER:      // if the item must be retrieved using the in-order method...
                inQueue.Dequeue(item);  // ...get the item from the in-queue

                    if(inQueue.IsEmpty()) done = true;      // if the in-queue is empty (the item is not found), set 'done' to true as an indication
                break;

            case POST_ORDER:    // if the item must be retrieved using the post-order method...
                postQueue.Dequeue(item);    // ...get the item from the post-queue

                    if(postQueue.IsEmpty()) done = true;    // if the post-queue is empty (the item is not found), set 'done' to true as an indication
                break;

            default:
                break;
        }
}


/**
 * BinarySearchTree CLASS GENERAL USE FUNCTIONS:
 */
template <class ItemType>
void BinarySearchTree<ItemType>::MakeEmpty(void)
{
    Destroy(root);      // the tree is simply destroyed.  Make careful note that this implementation, per se, is in no way identical to the destruction of the object itself.
}

template <class ItemType>
bool BinarySearchTree<ItemType>::IsEmpty(void)
{
    return (root == 0); // if the root is null, then the tree is empty... (DUH!  Such are the laws of nature my friend.)
}

template <class ItemType>
bool BinarySearchTree<ItemType>::IsFull(void)
{
    TreeNode<ItemType>  *pTemp = new TreeNode<ItemType>();  // attempt to allocate some memory for a new tree node

        if(pTemp == 0)  // if the previous attempted memory allocation failed a.k.a. if the temporary pointer is null...
        {
            return true;    // ...true is returned, indicating, more or less, a full tree
        }
        else            // ...
        {
            delete pTemp;   // ...free up the allocated memory location

            return false;   // ...return false, indicating a 'not-full' tree
        }
}

template <class ItemType>
int BinarySearchTree<ItemType>::NumberOfNodes(void)
{
    /**
     * NOTE:
     * To count the number of nodes in the tree, code can be implemented to add the root node, plus
     * the count of nodes on the left, plus the count of nodes on the right together. (1 + nL + nR)
     *
     * In order to achieve this, the tree will be recursed, and each sub-node will be added as 1 until
     * no sub-node is left (a leaf is reached).
     */

    return CountNodes(root);    // returns the result returned by the CountNodes() auxiliary function (which recursively counts the number of nodes in the tree)
}

template <class ItemType>
void BinarySearchTree<ItemType>::ResetTree(OrderType order)
{
    /**
     * Check the tree traverse order type and call the relative function:
     */
    switch(order)
    {
        case PRE_ORDER:
            PreOrder(root, preQueue);
            break;
        case IN_ORDER:
            InOrder(root, inQueue);
            break;
        case POST_ORDER:
            PostOrder(root, postQueue);
            break;
        default:
            break;
    }
}

template <class ItemType>
void BinarySearchTree<ItemType>::PrintTree(void)
{
    Print(root);
}


/**
 * BinarySearchTree CLASS DESTRUCTOR(s):
 */
template <class ItemType>
BinarySearchTree<ItemType>::~BinarySearchTree()
{
    /**
     * NOTE:
     * The implementation of the destructor will exploit the idea that the structure of the tree is
     * recursive, so in order to destroy the tree, the action can start from the root, move to the
     * left side, take the left side's first item as a root, then process the sub-tree, take another
     * sub-tree until the leaf is reached, then finally destroy the leaf.
     */

    /**
     * Auxiliary Function (to destroy tree root):
     */
    Destroy(root);
}


/**
 * AUXILIARY FUNCTION IMPLEMENTATIONS:
 */

/**
 * Destroy() AUXILIARY FUNCTION:
 */
template <class ItemType>
void Destroy(TreeNode<ItemType> *&tree)
{
    if(tree != 0)   // if the tree is not null...
    {
        Destroy(tree->left);    // ...first, destroy the left side of the tree (passed in as reference)
        Destroy(tree->right);   // ...then, destroy the right side of the tree

        delete tree;            // provides a base to stop the preceding recursive actions
        /**
         * NOTE:
         * After the tree is deleted, only a leaf will be left.
         */
    }
}

/**
 * CountNodes() AUXILIARY FUNCTION:
 */
template <class ItemType>
int CountNodes(TreeNode<ItemType> *tree)    // only a pointer is used because the structure of the tree is only going to be recursed and not changed
{
    if(tree == 0)   // if the tree is empty...
    {
        return 0;       // ...report accordingly
    }
    else            // ...
    {
        /**
         * ...return the count of nodes on the left, added to the count of nodes on the right, plus
         * the actual node itself.
         *
         * NOTE:
         * Pay careful attention to the fact that this action is done recursively.
         */
        return(CountNodes(tree->left) + CountNodes(tree->right) + 1);
    }
}

/**
 * Insert() AUXILIARY FUNCTION:
 */
template <class ItemType>
void Insert(TreeNode<ItemType> *&tree, ItemType item)
{
    /**
     * NOTE:
     * The TreeNode<ItemType> pointer is provided by reference, because the operations performed in
     * this functions will change it.
     *
     * The result will yield the same tree with the new item (being inserted) added to it.
     */

    /**
     * If this is the first item being inserted into the tree, or a point is reached where the item
     * can be inserted:
     */
    if(tree == 0)
    {
        tree = new TreeNode<ItemType>();
        tree->element = item;
        tree->left = 0;                     // because its a leaf
        tree->right = 0;                    // "
    }
    else if(item < tree->element)   // ...
        Insert(tree->left, item);       // ...recursively search for the place on the left side of the tree to insert the item until it's found, then do accordingly
    else                            // the item being inserted is still bigger than the items on the left of the tree...
        Insert(tree->right, item);      // ...recursively search for the place on the right side of the tree to insert the item until it's found, then do accordingly

    /**
     * NOTE:
     * In the preceding algorithm, items were inserted into the tree as leaves.  This is not the best
     * approaching.  A better alternative is to work on 'balanced search trees', which will require
     * the implementation of a more complex algorithm.
     *
     * The problem with the aforementioned approach is that, whenever the code searches for an item,
     * because there are more levels, the search will take longer.
     */
}

/**
 * Retrieve() AUXILIARY FUNCTION:
 */
template <class ItemType>
void Retrieve(TreeNode<ItemType> *tree, ItemType &item, bool &found)
{
    if(tree == 0)                   // if the tree is empty...
        found = false;                          // ...set the value for found accordingly
    else if(item < tree->element)   // if the item is smaller than the current tree element...
        Retrieve(tree->left, item, found);      // ...recurse on the left side of the tree until the item is found
    else if(item > tree->element)   // if the item is larger than the current tree element...
        Retrieve(tree->right, item, found);     // ...recurse on the right side of the tree until the item is found
    else                            // if the item is equal to the tree element...
    {
        item = tree->element;                   // store its value in the item variable
        found = true;                           // ...
    }
}

/**
 * Delete() AUXILIARY FUNCTION:
 */
template <class ItemType>
void Delete(TreeNode<ItemType> *&tree, ItemType item)
{
    if(item < tree->element)        // if the item is smaller than the current tree element...
        Delete(tree->left, item);       // ...recursively search on the left side of the tree until the item is found
    else if(item > tree->element)   // if the item is greater than the current tree element...
        Delete(tree->right, item);      // ...recursively search on the right side of the tree until the item is found
    else                            // if the item is equal to the tree element (if the item is found)...
        DeleteNode(tree);               // ...pass the tree to the DeleteNode() auxiliary function to do the job
}

/**
 * DeleteNode() AUXILIARY FUNCTION:
 */
template <class ItemType>
void DeleteNode(TreeNode<ItemType> *&tree)
{
    /**
     * NOTE:
     * To delete a node from the tree, code will be implemented to:
     * - simply delete a node if it has no predecessor/child.
     *
     * - replace a node with its predecessor/child, if it has only one predecessor/child (either a
     * left or right one (but not both)).
     *
     * - replace the node with its left predecessor/child that has the greatest value, making
     * everything on the left still smaller, and everything on the right still larger.
     */

    ItemType            data;
    TreeNode<ItemType>  *pTemp = tree;  // create a temporary pointer and make it point to the tree being manipulated

        /**
         * if the tree has only 1 child on either side
         */
        if(tree->left == 0)         // if the left part of the tree is null...
        {
            tree = tree->right;                 // ...point the tree to its right child

            delete pTemp;                       // ...delete the temporary pointer, deleting the previous tree root
        }
        else if(tree->right == 0)   // if the right part of the tree is null...
        {
            tree = tree->left;                  // ...point the tree to its left child

            delete pTemp;                       // ...delete the temporary pointer, deleting the previous tree root
        }
        else                        // if the tree has both children...
        {
            GetPredecessor(tree->left, data);   // ...get the left predecessor of the tree and store its value in the data variable

            tree->element = data;               // ...replace the item to be deleted with the data acquired from the tree's predecessor

            Delete(tree->left, data);           // ...delete the predecessor containing the previously acquired data
        }
}

/**
 * GetPredecessor() AUXILIARY FUNCTION:
 */
template <class ItemType>
void GetPredecessor(TreeNode<ItemType> *tree, ItemType &data)
{
        while(tree->right != 0)     // while the tree has a right node...
            tree = tree->right;         // ...continue to the rightmost node

    data = tree->element;           // assign the value of the element of the rightmost node of the tree to the data variable
}

/**
 * PreOrder AUXILIARY FUNCTION:
 */
template <class ItemType>
void PreOrder(TreeNode<ItemType> *tree, LinkedQueue<ItemType> &preQueue)
{
    /**
     * NOTE:
     * The code implemented in the PreOrder() function will allow the function to visit the current
     * node first, then all the nodes on the left sub-tree, then all the nodes on the right sub-tree.
     * The process will halt when the tree is null (a null value is reached).
     */
    if(tree != 0)
    {
        preQueue.Enqueue(tree->element);    // add the current element to the linked queue
        PreOrder(tree->left, preQueue);     // (recursively) visit and add all of the items on the left sub-tree to the linked queue
        PreOrder(tree->right, preQueue);    // (recursively) visit and add all of the items on the right sub-tree to the linked queue
    }
}

/**
 * InOrder AUXILIARY FUNCTION:
 */
template <class ItemType>
void InOrder(TreeNode<ItemType> *tree, LinkedQueue<ItemType> &inQueue)
{
    /**
     * NOTE:
     * The code implemented in the InOrder() function will allow the function to visit all the nodes
     * on the left sub-tree first, then the current node, then all the nodes on the right sub-tree.
     * The process will halt when the tree is null (a null value is reached).
     */
    if(tree != 0)
    {
        InOrder(tree->left, inQueue);       // (recursively) visit and add all of the items on the left sub-tree to the linked queue
        inQueue.Enqueue(tree->element);     // add the current element to the linked queue
        InOrder(tree->right, inQueue);      // (recursively) visit and add all of the items on the right sub-tree to the linked queue
    }
}

/**
 * PostOrder AUXILIARY FUNCTION:
 */
template <class ItemType>
void PostOrder(TreeNode<ItemType> *tree, LinkedQueue<ItemType> &postQueue)
{
    /**
     * NOTE:
     * The code implemented in the PostOrder() function will allow the function to visit all the nodes
     * on the left sub-tree first, then all the nodes on the right sub-tree, then the current node.
     * The process will halt when the tree is null (a null value is reached).
     */
    if(tree != 0)
    {
        PostOrder(tree->left, postQueue);   // (recursively) visit and add all of the items on the left sub-tree to the linked queue
        PostOrder(tree->right, postQueue);  // (recursively) visit and add all of the items on the right sub-tree to the linked queue
        postQueue.Enqueue(tree->element);   // add the current element to the linked queue
    }
}

/**
 * Print() AUXILIARY FUNCTION:
 */
template <class ItemType>
void Print(TreeNode<ItemType> *tree)
{
    /**
     * NOTE:
     * To print a tree, the whole left side will be printed first, then the whole right side.  This
     * method is called in-order traverse, and will be implemented using recursion.
     */
    if(tree != 0)
    {
        Print(tree->left);

        std::cout << tree->element << std::endl;

        Print(tree->right);
    }
}