CSCI 340 assignmentsix.cc

#include <iostream>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
//Terina Burr
//Section One
//Due 10/30/15
//Assignment 6

#include "assignment5.h"
#include "assignment6.h"
using namespace std;
/***************************************************************
Function: BST

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

Arguments: none

Returns:   nothing
***************************************************************/
//BST:: binTree( )
//{
//   root= NULL;
//}

/***************************************************************
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
***************************************************************/
void BST::insert (  int x )

{
    insert( this->root, x );
}

// searches leaf with value x
/***************************************************************
Function: search

Use:      it searches for the data x of the tree calling the function search recursively

Arguments: 1. x: the item that is searched for


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

bool BST::search (  int x )
{
    return search(this-> root, x );
}

// removes leaf with value x
/***************************************************************
Function: remove

Use:      it removes  x from the  tree calling the function remove recursively

Arguments: 1. x: the item that is removed


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

bool BST::remove (  int x )
{
    if(root!=0)
        return  remove(this->root,x );

    return false;
}
// 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 BST::insert ( Node *& p,  int v )
{
    if(p == 0)
    {
        p = new Node( v );
    }
    else if( v < p->data)
    {
        insert( p->left, v );
    }
    else if( v > p->data )
    {
        insert( p->right, v );
    }
    else
    {
        return; // duplicate
    }
}

// private version of search
/***************************************************************
Function: search

Use:      private version of search it searches for v in the tree p

Arguments: 1. p: reference pointer to a tree
           2. v: what is being searched for


Returns:  true of false if in the tree
***************************************************************/

bool BST::search (Node *&p, int v )
{


    if( p == NULL )
         return false;
     else
        {
        if( v == p->data )
                {
//                      if(p->left == NULL)
            return true;
//          if( p->right == NULL) return true;
  //                      else return false;
             }
        else if( v < p->data )
                        return search( p->left, v );
        else
            return search( p->right, v );
}

}
/***************************************************************
Function: remove

Use:      private version of remove it removes an item in the tree

Arguments: 1. node: reference pointer to a tree
           2. x: what is being removed
***************************************************************/
bool BST:: remove(Node *& node, int x)
{
if( node == 0)//if the node is empty
        return false;
    else    if(node->data == x ) //if the node equals the one being asked and it is a leaf then
    {
        if(node->left==NULL && node->right!=NULL)   //only has left child
        {
            Node *p = node;
            node =node->right;
            p->left=NULL;  // Done for safety
                p->right=NULL; // Done for safety
                delete p;
            return true;
        }
        else if (node->right==NULL && node->left!=NULL)//only has right child
        {
            Node *p = node;
                        node =node->left;
                        p->left=NULL;  // Done for safety
                        p->right=NULL; // Done for safety
                        delete p;
                        return true;
        }
else              if(node->left == NULL && node->right==NULL){//is a leaf
                        delete node;

                        node = NULL;//can delete later
return true;
            }

        else
        {
            return true;
        }
    }
    else if (x < node->data)//
        return  remove (node->left, x);
    else if (x > node-> data)
        return  remove (node->right, x);
  else // if (node->right!=NULL &&node->left!=NULL) //jhas both children
                        {
                                Node *temp = node->left;
                                while(temp->right)
                                temp = temp->right;
                Node*pred= temp;
                                pred = node;
                                return  remove(node->left,pred->data);
                        }

}
/***************************************************************
Function: print left leaves

Use:      it prints left leaves  of the tree calling the function print left leaves recursively

Arguments: none


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

void BST::printLeftLeaves()
{
                printLeftLeaves(root->left);
}
void BST:: sumAncestors(int x, int &y)
{
if(sumAncestors(root->left,x,y)||sumAncestors(root->right,x,y))
{
        y = y+ root->data;
}
}

/**************************************************************
Function: print left leaves

Use:      it prints left leaves  of the tree

Arguments: 1. *p: pointer to node that is going to be printed

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


void BST:: printLeftLeaves(Node* p )
{
        if(p!=0)//if node isnt null
        {
        //  printLeftLeaves(p->left);
            if(p->left == NULL && p->right==NULL)//     if(!(p->left) && !(p->right)
                printLeftLeaves(p->left);
            cout << p->data << ",";
//          printLeftLeaves(p->left);
        }
}
bool BST:: sumAncestors(Node *p,int x,int&y )
{
    if (p == 0)//if p is null
        return false;
    if(p->data == x )//if the data in p maches what is searching for
        return true;

if(sumAncestors(p->left,x,y)||sumAncestors(p->right,x,y)) //if there is dATA IN the right or left subtree
{
    y = y+ p->data;//then the sum = the data lus the sum
    return true;
}
return false;
}