CSCI 340 assignfive.h

#ifndef ASSIGNMENT5
#define ASSIGNMENT5
//Terina burr
//Assignment 5
//section 1
//due 10/18/15
#include <iostream>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
using namespace std;
//--------------------------
// You need to add definition of the Node class
//--------------------------
class Node {
friend class binTree ;
public:
int data;
 Node * left;
 Node * right;
public:
Node (int x = 0){ data = x; left = right = NULL; }

};

class binTree {
    public:
        binTree();
        virtual void insert( int );
        int height() const;
        int size() const;
        void inorder( void(*)(int) );
        void preorder( void(*)(int) );
        void postorder( void(*)(int) );

    protected:
        Node* root;
    private:
        void insert( Node*&, int );
        int height( Node* ) const;
        int size( Node* ) const;
    void inorder( Node*, void(*)(int) );
    void preorder( Node*, void(*)(int) );
    void postorder( Node*, void(*)(int) );
};


/***************************************************************
Function: binTree

Use:      it is a constructor it initializes the tree sets root to null

Arguments: none

Returns:   nothing
***************************************************************/


binTree::binTree( )
{
    root = NULL; // initialize root
}
/***************************************************************
Function: size

Use:      it calls the function size recursively

Arguments: none

Returns:   the size of the tree
***************************************************************/


int binTree ::size( ) const
{
    return size( root ); // call recursive
}

/***************************************************************
Function: height

Use:      it calls the function height recursively

Arguments: none

Returns:   the height of the tree
***************************************************************/

// returns height of tree

int binTree ::height( ) const
{
    return height( root ); // call recursive
}

/***************************************************************
Function: insert

Use:      it inserts a node of the tree calling the function insert recursively

Arguments: 1. x: the item that is inserted into tree


Returns:  none
***************************************************************/

    // inserts a node in shortest subtree

void binTree ::insert( int x )
{
    insert( root, x ); // call recursive
}

/***************************************************************
Function: inorder

Use:      calls inorder recursively

Arguments: 1. fn: pointer to a function accepting one int argument and returning void

Returns:   none
***************************************************************/

    // inorder traversal of tree

void binTree  ::inorder( void ( *fn ) (int) )
{
    inorder( root, fn ); // call recursive
}


/***************************************************************
Function: preorder

Use:      calls preorder recursively

Arguments: 1. fn: pointer to a function accepting one int argument and returning void

Returns:   none
***************************************************************/


    // preorder traversal of tree
void binTree ::preorder( void ( *fn ) (int ) )
{
    preorder( root, fn ); // call recursive
}

/***************************************************************
Function: postorder

Use:      calls postorder recursively

Arguments: 1. fn: pointer to a function accepting one int argument and returning void

Returns:   none
***************************************************************/

    // postorder traversal of tree

void binTree ::postorder( void ( *fn ) ( int ) )
{
    postorder( root, fn ); // call recursive
}


    // private version of size
/***************************************************************
Function: size

Use:      private version of size it finds the size of a tree

Arguments: 1. Ptr: pointer to tree

Returns:   the size of the tree
***************************************************************/

int binTree ::size( Node * ptr ) const
{
    if( ptr != 0 ) // if not empty
    {
        return 1 + size( ptr->left ) + size( ptr->right );
    }
    else
    {
        return 0; // emtpy tree
    }
}

/***************************************************************
Function: height

Use:      private version of height it finds the height of a tree

Arguments: 1. Ptr: pointer to tree

Returns:   the height of the tree
***************************************************************/

    // private version of height

int binTree ::height( Node * ptr ) const
{
    if( ptr == 0 )
    {
        return 0; // empty tree
    }
    else
    {
        int lHeight = height( ptr->left ); // left side
        int rHeight = height( ptr->right ); // right side

        if( lHeight > rHeight ) // which is greater
        {
            return 1 + lHeight; // return left
        }
        else
        {
            return 1 + rHeight; // return right
        }
    }
}


    // private version of insert
/***************************************************************
Function: insert

Use:      private version of insert it inserts a node of the tree

Arguments: 1. p: reference pointer to a tree
           2. v: what is being inserted into the tree


Returns:  none
***************************************************************/

void binTree ::insert( Node * & p, int  v )
{
    if( p == 0 ) //if the node is empty
    {
        Node  * newNode;
        newNode = new Node ( v ); // new node with new value
        p = newNode; // set ptr to new node
    }
    else
    {
        int lHeight = height( p->left );//get hight of left
        int rHeight = height( p->right );//get height of right

        if( lHeight <= rHeight )//if left height less than or equal to right
        {
            insert( p->left, v );//insert v on left node
        }
        else
        {
            insert( p->right, v ); //insert v on right node
        }
    }
}


    // private version of inOrder
/***************************************************************
Function: inorder

Use:      puts tree in the inorder version first traverse the left subtree then visit the root and then traverse the right subtree

Arguments: 1. fn: pointer to a function accepting one int argument and returning void
           2. p: pointer to a node


Returns:   none
***************************************************************/

void binTree ::inorder( Node * p, void ( *fn ) (int ) )
{
    if( p != NULL )//if it is not null
    {
        inorder( p->left, fn );//traverse left
        fn( p->data );//traverse root
        inorder( p->right, fn );//traverse right
    }
}
/***************************************************************
Function: preorder

Use:      puts tree in preorder version visit the root traverse the left subtree traverse the right subtree

Arguments: 1. fn: pointer to a function accepting one int argument and returning void
           2. p: pointer to a node

Returns:   none
***************************************************************/


// private version of preOrder

void binTree ::preorder( Node * p, void ( *fn ) ( int ) )
{
    if( p != NULL )
    {
        fn( p->data ); //traverse root
        preorder( p->left, fn ); //traverse left
        preorder( p->right, fn );// traverse rightt
    }
}


// private version of postOrder

/***************************************************************
Function: postorder

Use:      puts tree in post order    traverse the left subtree then traverse the right subtree then visit the root

Arguments: 1. fn: pointer to a function accepting one int argument and returning void

Returns:   none
***************************************************************/



void binTree ::postorder( Node * p, void ( *fn ) ( int ) )
{
    if( p != NULL ) // if the node not empty
    {
        postorder( p->left, fn ); ///traverse left
        postorder( p->right, fn ); //traverse right
        fn( p->data ); //traverse root
    }
}









#endif