How to fix segmentation error 11 in c++

Vote count:

0

I am currently writing a binary tree project in c++ and it is giving me some errors that I am struggling to understand. The error in question is a segmentation error that I have no idea how to fix. Below is the code from one one the files where all the functions are written. The function in particular that is giving me an issue is the last one - the print_pre_order_private function.

#include <iostream>
#include <cstdlib>

#include "BT.h"

using namespace std;

BT::BT()
{
    root = NULL;  //makes sure pointer isn't pointing at anything
}

BT::node* BT::create_leaf(int key)
{
    node* n = new node;
    n->key = key;
    n->left = NULL;
    n->right = NULL;

    return n;
}

void BT::add_leaf(int key)
{
    add_leaf_private(key, root);
} 

void BT::add_leaf_private(int key, node* Ptr)
{
    if(root == NULL)
    {
        root = create_leaf(key);
    }

    else if(key < Ptr->key)
    {
        if(Ptr->left != NULL)
        {
             add_leaf_private(key, Ptr->left);
        }
        else
        {
            Ptr->left = create_leaf(key);
        }
    }

    else if(key > Ptr->key)
    {
        if(Ptr->right != NULL)
        {
             add_leaf_private(key, Ptr->right);
        }
        else
        {
            Ptr->right = create_leaf(key);
        }
    }
    else
    {
        cout << "The key " << key << " has already been added to the    tree\n";
    }
}

void BT::print_in_order()
{
    print_in_order_private(root);
}

void BT::print_in_order_private(node* Ptr)
{
    if(root != NULL)
    {
        if(Ptr->left != NULL)
        {
            print_in_order_private(Ptr->left);
        } 
        cout << Ptr->key << " ";
        if(Ptr->right != NULL)
        {
            print_in_order_private(Ptr->right);
        }
    } 
    else
    {
        cout << "The tree is empty\n";
    }
}

BT::node* BT::return_node(int key)
{
    return return_node_private(key, root);
}

BT::node* BT::return_node_private(int key, node* Ptr)
{
    if(Ptr != NULL)
    {
        if(Ptr->key == key)
        {
            return Ptr;
        }

        else
        {
            if(key < Ptr->key)
            {
                return return_node_private(key, Ptr->left);
            }

            else
            {
                return return_node_private(key, Ptr->right);
            }
        }
    }
    else
    {
        return NULL;
    }
}

int BT::return_root_key()
{
    if(root != NULL)
    {
        return root->key;
    }
    else
    {
        return -1;
    }
}

void BT::print_children(int key)
{
   node* Ptr = return_node(key);

    if(Ptr != NULL)
    {
        cout << "Parent Node = " << Ptr->key << endl;

        Ptr->left == NULL ?
        cout << "Left child = NULL\n":
        cout << "Left child = " << Ptr->left->key << endl;

        Ptr->right == NULL ?
        cout << "Right child = NULL\n":
        cout << "Right child = " << Ptr->right->key << endl;
     }
     else
     {
        cout << "Key " << key << " is not in the tree\n";
     }

 }

int BT::find_smallest()
{
    return find_smallest_private(root);
}

int BT::find_smallest_private(node* Ptr)
{
    if(root == NULL)
    {
        cout << "The tree is empty\n";
        return -1;
    }
    else
    {
        if(Ptr->left != NULL)
        {
            return find_smallest_private(Ptr->left);
        }
        else
        {
            return Ptr->key;
        }
    }
}


void BT::remove_node(int key)
{
     remove_node_private(key, root);
}  

void BT::remove_node_private(int key, node* parent)
{
    if(root != NULL)
   {
    if(root->key == key)
    {
        remove_root_match();
    }
    else
    {
        if(key < parent->key && parent->left != NULL)
        {
             parent->left->key == key ?
             remove_match(parent, parent->left, true) :
             remove_node_private(key, parent->left);
        }   
        else if(key < parent->key && parent->right != NULL)
        {
             parent->right->key == key ?
             remove_match(parent, parent->right, true) :
             remove_node_private(key, parent->right);
        }
        else
        {
            cout << "The key " << key << " was not found in the tree\n";
        }
    }
}
else
{
    cout << "The tree is empty\n";
}
}

void BT::remove_root_match()
{
    if(root != NULL)
    {
        node* delPtr = root;
        int root_key = root->key;
        int smallest_right_subtree;

        //case 0 - 0 children
        if(root->left == NULL && root->right == NULL)
        {
            root = NULL;
            delete delPtr;
        }

        //case 1 - 1 child
        else if(root->left == NULL && root->right != NULL)
        {
            root = root->right;
            delPtr->right = NULL;
            delete delPtr;
            cout << "The root node with key " << root_key << " was deleted. " 
            << " The new root contains key " << root->key << endl;

        }
        else if(root->right == NULL && root->left != NULL)
        {
            root = root->left;
            delPtr->left = NULL;
            delete delPtr;
            cout << "The root node with key " << root_key << " was deleted. " 
            << " The new root contains key " << root->key << endl;

        }
        //case 2 - 2 children
        else
        {
            smallest_right_subtree = find_smallest_private(root->right);
            remove_node_private(smallest_right_subtree, root);
            root->key = smallest_right_subtree;
            cout << "The rout key containing key " << root_key
            << " was overwritten with key " << root->key << endl;
        }
   }
    else
    {
        cout << "Cannot remove root. Tree is empty\n";
    }
}

void BT::remove_match(node* parent, node* match, bool left)
{
    if(root != NULL)
    {
        node* delPtr;
        int match_key = match->key;
        int smallest_right_subtree;

        //case 0 - 0 children
        if(match->left == NULL && match->right == NULL)
        {
            delPtr = match;
            left == true ? parent->left = NULL : parent->right = NULL;
            delete delPtr;
            cout << "The node containing key " << match_key << " was removed\n";
        }

        //case 1 - 1 child
        else if(match->left == NULL && match->right != NULL)
        {
            left == true ? parent->left = match->left : parent->right = match->right;
            match->left = NULL;
            delPtr = match;
            delete delPtr;
            cout << "The node containing key " << match_key << " was removed\n";
        }
        //case 2 - 2 children
        else
        {
            smallest_right_subtree = find_smallest_private(match->right);
            remove_node_private(smallest_right_subtree, match);
            match->key = smallest_right_subtree;
        }
    }
    else 
    {
        cout << "Cannot remove match. The tree is empty";
    }
}

void print_pre_order()
{
    print_pre_order_private(root);
}
void print_pre_order_private(node* Ptr)
{
    if(root != NULL)
    {
        cout << Ptr->key << " ";
        print_pre_order_private(Ptr->left);
        print_pre_order_private(Ptr->right);
    }
}

Any help in fixing this situation is greatly appreciated. Thanks in advance. :)

asked 31 secs ago

Jack Waters

1

How to fix segmentation error 11 in c++