binarytree delete

binarytree.cpp

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

// global function declaration
bool checkPrime(int input);

binarytree::binarytree() {
    root = nullptr;
    mSize = 0;
    

}



// copy constructor
binarytree::binarytree(binarytree*& copyMe) {
    // call copyTree
    copyTree(this->root, copyMe->root);
    
}

// deconstructor
binarytree::~binarytree() {
    deleteTree(root);
}






void binarytree::print() const {
    print_aux(root);
}






void binarytree::insert(int item) {
    insert_aux(root, item);
    mSize++;
}




int binarytree::numPrimes() {
    
    // nothing in the tree, so no primes
    return numPrimes_aux(root);
    
}


/* function converts binarytree to linked list object
   list is sorted in increasing order
 */
LL<int> binarytree::toLL() {
    
    // declare list object
    LL<int> newList;
    
    toLL_aux(root, newList);

    return newList;
    
}


// aux function for using recursion for conversion to linked list
/* TODO: needs to be sorted in descending order */
void toLL_aux(binarytree::treenode* root, LL<int>& list) {
    
    
    if (root == nullptr) {
        return;
    } else {
        toLL_aux(root->right, list);
        list.push_front(root->data);
        toLL_aux(root->left, list);
    }
 

}


int numPrimes_aux(binarytree::treenode* root) {
    
    if (root == nullptr) {
        return 0;
    } else if (checkPrime(root->data)) {

        return numPrimes_aux(root->left)
        + numPrimes_aux(root->right) + 1;

    } else {
        return numPrimes_aux(root->left) + numPrimes_aux(root->right);
    }
    
}





// helper global function to check if a passed in int is prime
bool checkPrime(int input) {
    
    if (input <= 3) {
        return input > 1;
    } else if (input % 2 == 0 || input % 3 == 0) {
        return false;
    } else {
        for (int i = 5; i * i <= input; i += 6) {
            if (input % i == 0 || input % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
    
}


binarytree::size_type binarytree::size() const {
//    return size_aux(root);
    return mSize;
}



int binarytree::find(int target, bool& found) const{
    return find_aux(root, target, found);
}


void binarytree::del(int target, bool& found) {
    del_aux(root, target, found);

}



// helper function to remove the whole tree
void deleteTree(binarytree::treenode* root) {
    
    
    if (root == nullptr) {
        // it's empty, there is nothing to delete
        return;
        
     } else {
        
        deleteTree(root->left);
        deleteTree(root->right);
        
        delete root;
    
    }
    
}


// helper function to copy a binarytree
void copyTree(binarytree::treenode* root, binarytree::treenode*& coRoot) {
    
    /* TODO: memleak below */
    // copy origin data from root
    
    if (root == nullptr) {
        return;
    }
    
    root->data = coRoot->data;

    if (root->left != nullptr) {
        copyTree(root->left, coRoot->left);
        
    } else if (root->right != nullptr) {
        
        copyTree(root->right, coRoot->right);
    }
    

    
}




void del_aux(binarytree::treenode*& root,
             int target,
             bool& found) {
    
    if (root == nullptr) {
        found = false;
        
    } else if (target < root -> data) {
        del_aux(root -> left, target, found);
        
    } else if (target > root -> data) {
        del_aux(root -> right, target, found);
        
    } else if (root -> left == nullptr) {
        
        binarytree::treenode* tempptr = root;
        root = root -> right;
        delete tempptr;
        found = true;
        
        
    } else {
        int max;
        remove_max(root -> left, max);
        root -> data = max;
        found = true;
    }
    
}






// pre: root != nullptr

void remove_max(binarytree::treenode*& root, int& max) {
    
    if (root -> right == nullptr) {
        max = root -> data;
        binarytree::treenode* tempptr = root;
        root = root -> left;
        delete tempptr;
        
    } else {
        
        remove_max(root -> right, max);
    }
}




int find_aux(binarytree::treenode* root,
             int target,
             bool& found) {
    
    if (root == nullptr) {
        
        found = false;
        return 0;
    } else if (target == root -> data) {
        
        found = true;
        return root -> data;
    } else if (target < root -> data) {
        
        return find_aux(root -> left, target, found);
    } else {
        
        return find_aux(root -> right, target, found);
    }
}



binarytree::size_type size_aux(binarytree::treenode* root) {
    
    if (root == nullptr) {
        return 0;
    } else {
        
        return size_aux(root -> left)
        + size_aux(root -> right)
        + 1;
    }
}


void insert_aux(binarytree::treenode*& root, int item) {
    if (root == nullptr) {
        
        // root = new treenode(item, nullptr, nullptr);
        root = new binarytree::treenode;
        root -> data = item;
        root -> left = nullptr;
        root -> right = nullptr;
    } else if (item <= root -> data) {
        
        insert_aux(root -> left, item);
    } else {
        
        insert_aux(root -> right, item);
    }
}


void print_aux(binarytree::treenode* root) {
    
    if (root != nullptr) {
        
        print_aux(root -> left);
        std::cout << root -> data << " ";
        print_aux(root -> right);
    }
}


// overloaded equals operator
binarytree binarytree::operator=(const binarytree*& rightTree) {
    
    deleteTree(this->root);
    copyTree(rightTree->root, this->root);
    return *this;
    
    
    
}

binarytree.h

#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <cstdlib>	// for size_t
#include "LL.h"


    class binarytree {
        
    public:
        typedef std::size_t size_type;
        binarytree();
        void insert(int item);
        void print() const;
        
        
        // copy constructor
        binarytree(binarytree*& copyMe);
        
        // deconstructor
        ~binarytree();
        
        // operator
        binarytree operator = (const binarytree*& rightTree);
        

        
        // returns number of nodes that contain prime integers
        int numPrimes();
        
        // returns mSize
        size_type size() const;
        int find(int target, bool& found) const;
        void del(int target, bool& found);
        
        // convert binarytree to linked list
        LL<int> toLL();
        
        /* DEBUG TEMP */
        bool checkPrime(int input);

        
    private:

        
        
        // stores the size of the tree
        size_type mSize;
        
        int numPrime;
        
        struct treenode {
            int data;
            treenode* left;
            treenode* right;
        };
        
        treenode* root;
        

        friend int numPrimes_aux(treenode* root);
        friend void insert_aux(treenode*& root, int item);
        friend void print_aux(treenode* root);
        friend size_type size_aux(treenode* root);
        friend int find_aux(treenode* root, int target, bool& found);
        friend void del_aux(treenode*& root, int target, bool& found);
        friend void remove_max(treenode*& root, int& max);
        
        
        
        // aux function for converting to linked list
        friend void toLL_aux(treenode* root, LL<int>& list);
        
        // deletes the whole binary tree
        friend void deleteTree(treenode* root);
        
        // aux function for recursively copying a binarytree
        friend void copyTree(treenode* root, treenode*& coRoot);
    };





#endif

LL.cpp

#include <cassert>
#include <iostream>
using namespace std;


template <class T>
void LL<T>::delete_after(iterator& position) {
    assert (position.link() -> next != NULL);
    node* tempptr = position.link();
    position.link() -> next = position.link() -> next -> next;
    delete tempptr;
}



template <class T>
void LL<T>::insert_after(iterator& position, const value_type& insertMe) {
    node* newnode = new node;
    newnode -> data = insertMe;
    newnode -> next = position.link() -> next;
    position.link() -> next = newnode;
    position.link() = newnode;
}



// void pop_front(): removes the first item in the list. Watch for memory leaks!
template <class T>
void LL<T>::pop_front() {
    if (empty())
    {
        throw Empty_List_Error();
    } else {
        node* deleteMe = list;
        list = list->next;
        delete deleteMe;
    }
    
}





// returns a reference to the front item in the LL object.
template <class T>
typename LL<T>::value_type& LL<T>::front() {
    if (empty())
    {
        throw Empty_List_Error();
    } else {
        return list->data;
    }
}





// same, but for use by const LL objects.
template <class T>
const typename LL<T>::value_type& LL<T>::front()  const {
    if (empty())
    {
        throw Empty_List_Error();
    } else {
        return list->data;
    }
}





// assignment operator overload (one of Big Four)
template <class T>
LL<T>  LL<T>::operator=(const LL<T> & listToAssign) {
    if (this != &listToAssign) {
        clear();
        copyList(listToAssign);
    }
    return *this;
}





// makes the LL object empty. Watch for memory leaks!
template <class T>
void LL<T>::clear() {
    node * deleteMe;
    while (list != NULL) {
        deleteMe = list;
        list = list->next;
        delete deleteMe;
    }
}





template <class T>
void LL<T>::copyList(const LL<T> & listToCopy)
{
    node* sourcePtr = listToCopy.list;
    if (sourcePtr != NULL) {
        list = new node;
        node* curptr = list;
        curptr->data = sourcePtr->data;
        sourcePtr = sourcePtr->next;
        while (sourcePtr != NULL) {
            curptr->next = new node;
            curptr = curptr->next;
            curptr->data = sourcePtr->data;
            sourcePtr = sourcePtr->next;
        }
        curptr->next = NULL;
    } else {
        list = NULL;
    }
}





// returns the number of items in the LL object.
template <class T>
typename LL<T>::size_type LL<T>::size() const {
    typename LL<T>::size_type numberOfItems = 0;
    node* currptr = list;
    while (currptr != NULL) {
        ++numberOfItems;
        currptr = currptr->next;
    }
    return numberOfItems;
}





// returns true if the LL object is empty, false otherwise.
template <class T>
bool LL<T>::empty() const {
    return list == NULL;
}





// insert x at the front of the LL object.
template <class T>
void LL<T>::push_front(const value_type& x) {
    node* newFirstPtr = list;
    list = new node;
    list->next = newFirstPtr;
    list->data = x;
}





// Default constructor.  One of the Big Four.  Creates an empty LL object.
template <class T>
LL<T>::LL () {
    list = NULL;
}





// copy constructor (one of the Big Four)
template <class T>
LL<T>::LL (const LL<T> & listToCopy) {
    copyList(listToCopy);
}





// destructor (one of Big Four)
template <class T>
LL<T>::~LL() {
    clear();
}

LL.h

//  This is the file LL.h


#ifndef LL_h
#define LL_h

#include <cstdio>

template <class T>
class LL {
public:
    typedef size_t size_type;
    typedef T value_type;
    
private:
    void copyList(const LL& listToCopy);
    struct node {
        value_type data;
        node* next;
    };
    node* list;
    
    
public:
    class iterator {
    public:
        iterator(node* initial = NULL) {
            current = initial;
        }
        
        value_type& operator*() const {
            return current->data;
        }
        
        iterator& operator++() {
            current = current->next;
            return *this;
        }
        
        iterator operator++(int) {
            iterator original(current);
            current = current->next;
            return original;
        }
        
        bool operator==(iterator other) const {
            return current == other.current;
        }
        
        bool operator !=(iterator other) const {
            return current != other.current;
        }
        
        const node* link() const {
            return current;
        }
        
        node*& link() {
            return current;
        }
        
    private:
        node* current;
    };
    
    
    class const_iterator  {
    public:
        const_iterator(const node* initial = NULL) {
            current = initial;
        }
        
        const value_type& operator*() const {
            return current->data;
        }
        
        const_iterator& operator++() {
            current = current->next;
            return *this;
        }
        
        const_iterator operator++(int) {
            const_iterator original(current);
            current = current->next;
            return original;
        }
        
        bool operator==(const const_iterator other) const {
            return current == other.current;
        }
        
        bool operator !=(const const_iterator other) const {
            return current != other.current;
        }
        
        const node* link() const {
            return current;
        }
        
        node*& link() {
            return current;
        }
    private:
        const node* current;
    };  // end of iterator class declarations.  LL class continues below.
    
    iterator begin() {
        return iterator(list);
    }
    
    iterator end() {
        return iterator();
    }
    
    const_iterator begin() const {
        return const_iterator(list);
    }
    
    const_iterator end() const {
        return const_iterator();
    }
    
    class Empty_List_Error{};
    LL();
    LL(const LL& listToCopy);
    LL operator=(const LL& listToAssign);
    ~LL();
    bool empty() const;
    size_type size() const;
    void clear();
    void pop_front();
    void push_front(const value_type& x);
    value_type& front();
    const value_type& front() const;
    void insert_after(iterator& position, const value_type& insertMe);
    void delete_after(iterator& position);
};


#include "LL.cpp"
#endif

lldb

(lldb) bt
* thread #1: tid = 0x4a5fb3, 0x0000000100000e10 assignment14.1`deleteTree(root=0xc18c00007fffa63a) + 32 at binarytree.cpp:157, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
  * frame #0: 0x0000000100000e10 assignment14.1`deleteTree(root=0xc18c00007fffa63a) + 32 at binarytree.cpp:157
    frame #1: 0x0000000100000e19 assignment14.1`deleteTree(root=0x0000000100400002) + 41 at binarytree.cpp:157
    frame #2: 0x0000000100000e26 assignment14.1`deleteTree(root=0x0000000100301ed0) + 54 at binarytree.cpp:158
    frame #3: 0x0000000100000e26 assignment14.1`deleteTree(root=0x0000000100500000) + 54 at binarytree.cpp:158
    frame #4: 0x0000000100000e26 assignment14.1`deleteTree(root=0x0000000100301eb0) + 54 at binarytree.cpp:158
    frame #5: 0x0000000100000dd5 assignment14.1`binarytree::~binarytree(this=0x00007fff5fbff178) + 21 at binarytree.cpp:25
    frame #6: 0x0000000100000e75 assignment14.1`binarytree::~binarytree(this=0x00007fff5fbff178) + 21 at binarytree.cpp:24
    frame #7: 0x00000001000033dc assignment14.1`main + 4604 at main.cpp:166
    frame #8: 0x00007fffa6150255 libdyld.dylib`start + 1
(lldb) 

main.cpp

#include <iostream>
#include "binarytree.h"
#include "LL.h"
using namespace std;

int main() {
    binarytree list;
    
    int num;
    bool found;
    
    cout << "enter number to insert (negative to quit): ";
    cin >> num;
    while (num >= 0){
        list.insert(num);
        cout << "enter number to insert (negative to quit): ";
        cin >> num;
    }
    
    list.print();
    cout << endl;
    
    binarytree::size_type numItems;
    numItems = list.size();
    cout << "There are " << numItems << " items." << endl;
    
    
    
    cout << "enter a number to find (negative to quit): ";
    cin >> num;
    while (num >= 0) {
        int result = list.find(num, found);
        if (!found) {
            cout << "not found" << endl;
        } else {
            cout << "found.  The data is " << result << endl;
        }
        cout << "enter a number to find (negative to quit): ";
        cin >> num;
    }
    
    
    cout << "enter a number to delete (negative to quit): ";
    cin >> num;
    while (num >= 0) {
        list.del(num, found);
        if (found) {
            cout << "the list is now ";
            list.print();
            cout << endl;
        } else {
            cout << num << " is not in the list." << endl;
        }
        cout << "enter a number to delete (negative to quit): ";
        cin >> num;
    }
    
    
    binarytree list2(list);
    
    cout << "Now list 2 should be a copy of list.  Here it is: ";
    list2.print();
    cout << endl;
    
    
    list2.del(3, found);
    
    
    cout << "After deleting a 3 from list2, list2 is now: ";
    list2.print();
    cout << endl << "list should be unchanged.  Here it is: ";
    list.print();
    cout << endl;
    
    list = list2;
    
    cout << "Now list has been assigned list2 so it should match list2.  Here it is: ";
    list.print();
    cout << endl;
    
    list.del(4, found);
    
    cout << "After deleting a 4 from list, list is now: ";
    list.print();
    cout << endl << "list2 should be unchanged.  Here it is: ";
    list2.print();
    cout << endl;
    
    
    
    
    /* NUM PRIMES */
    
    cout << endl;
    cout << "CHECKING PRIMES: " << endl;
    cout << "NUMBER OF PRIMES IN LIST : " << list.numPrimes() << endl;
    
    /* SIZE */
    
    cout << endl;
    cout << "CHECKING SIZE: " << endl;
    cout << "SIZE OF LIST: " <<  list.size() << endl;
    
    /* COPY CONSTRUCTOR */
    cout << endl;
    cout << "CREATING A BLANK LIST & COPYING: " << endl;
    binarytree newList(list);
    
    cout << "CHECKING DATA - ORIGIN LIST: " << endl;
    list.print();
    cout << "COPIED LIST: " << endl;
    newList.print();
    
    /* OPERATOR */
    cout << "CREATING NEW TREE w/ 5, 10 IN TREE: " << endl;
    binarytree testList;
    testList.insert(5);
    testList.insert(10);
    
    cout << "TEST LIST CONTENTS: " << endl;
    testList.print();
    cout << endl;
    
    cout << "SETTING testList equal to list" << endl;
    testList = list;
    
    cout << "CHECKING..." << endl;
    cout << "ORIGIN LIST: " << endl;
    list.print();
    cout << "TESTLIST: " << endl;
    testList.print();
    
    
    /* delete */

    

    
    /* LINKED LISTS */
    cout << endl;
    cout << "CONVERTING BINARY TREE TO LIST: " << endl;
    LL<int> linkedList;
    binarytree testTree;
    for (int i = 1; i <= 10; i++) {
        testTree.insert(i);
    }

    cout << endl;
    cout << "TREE BEING CONVERTED: ";
    testTree.print();
    linkedList = testTree.toLL();
    


    cout << "Linkedlist: ";
    for (LL<int>::iterator i = linkedList.begin(); i != linkedList.end(); i++) {
        cout << *i << " ";
    }
    cout << endl;
    


    
    
}