How to delete what my shared pointer is pointing to?

Question

When I run my main methods the functions makeEmpty and remove do not work. I am converting this code from using pointers to using shared pointers and I am not very familiar with shared pointers yet. Any insight on how to do this or any solutions would be extremely helpful. The main function is:

int main() {
    BinarySearchTree<int> me;

    me.insert (20);
    me.insert (30);
    me.insert (-2);
    me.insert (10);
    me.insert (7);
    me.insert (35);
    me.insert (24);
    me.printTree();
    me.findMin();
    me.findMax();
    me.contains(35);
    me.contains(36);
    me.remove(-2);
    me.printTree();
    me.makeEmpty();
    me.isEmpty();
    me.printTree();
    return 0;
}

This outputs :

-2 7 10 20 24 30 35

-2

35

True

False

-2 7 10 20 24 30 35

False

-2 7 10 20 24 30 35

using namespace std;

template <typename E>    
class BinarySearchTree {
public:
/**
 * Default constructor
 */
BinarySearchTree() {
}

/**
 * Destructor
 */
~BinarySearchTree() {
    purge(root);
}

int findMin(){
    return findMin(root) -> data;
}

int findMax(){
    return findMax(root) -> data;
}

bool contains(const E & x) const{
    if(contains(x, root))
        cout << "True" << endl;
    else
        cout << "False" <<endl;
}

bool isEmpty(){
    if(isEmpty(root))
        cout << "True" << endl;
    else
        cout << "False" <<endl;
}

void makeEmpty(){
    makeEmpty(root);
}

void remove(const E & x){
    remove(x, root);
}

void insert (E item) {
    insert (item, root);
}

void printTree(ostream& out = cout) const {
    print (out, root);
    cout << endl;
}

private:
struct Node {
    E data;
    shared_ptr<Node> left, right;
};

shared_ptr<Node> root;

void print (ostream& out, shared_ptr<Node> ptr) const {
    /* in order traversal */
    if (ptr != nullptr) {
        print (out, ptr->left);
        out << ptr->data << " ";
        print (out, ptr->right);
    }
}

void insert (E item, shared_ptr<Node>& ptr) const {
    if (ptr == nullptr) {
        ptr = make_shared<Node>();
        ptr->data = item;
    } else if (item < ptr->data) {
        insert(item, ptr->left);
    } else if (item > ptr->data) {
        insert(item, ptr->right);
    } else {
        // attempt to insert a duplicate item
    }
}

void purge (shared_ptr<Node> ptr) {
    if (ptr != nullptr) {
        purge (ptr->left);
        purge (ptr->right);
        ptr.reset();
    }
}

bool contains(const E & x, shared_ptr<Node> t) const{
    if(t == nullptr){
        return false;
    }
    else if( x < t-> data){
        return contains(x, t->left);
    }
    else if(t-> data < x){
        return contains(x, t->right);
    }
    else{
        return true;
    }
}

shared_ptr<Node>  findMin(shared_ptr<Node> t) const{
    if (t != nullptr){
        while(t-> left != nullptr){
            t = t->left;
        }
    }
    cout << t->data << endl;
    return t;
}

shared_ptr<Node> findMax(shared_ptr<Node> t) const{
    if (t != nullptr){
        while(t-> right != nullptr){
            t = t->right;
        }
    }
    cout << t->data << endl;
    return t;
}

void remove(const E & x, shared_ptr<Node> t){
    if(t == nullptr){
        return;
    }
    if (x > t-> data){
        remove(x, t-> left);
    }
    else if(t->data > x){
        remove(x, t-> right);
    }
    else if( t-> left != nullptr && t->right != nullptr){
        t-> data = findMin(t-> right) -> data;
        remove(t->data, t-> right);
    }
    else {
      t.reset();
    }
}

void makeEmpty(shared_ptr<Node> t){
    if ( t != nullptr ){
        makeEmpty(t -> left);
        makeEmpty(t-> right);
        t.reset();
    }
}

bool isEmpty(shared_ptr<Node> t) const{
    if( t = nullptr){
        return true;
    }
    else
        return false;
}



};

"Do not work" doesn't work. "Expected output:A Actual output: B" works, and only that works in programming. — iksemyonov, Oct 22 '17 at 19:13
your `isEmpty` has `if( t = nullptr)`. You probably want `==` but I don't suspect that'll solve your problemm — kmdreko, Oct 22 '17 at 19:15
Side note: please don't use `using namespace std` in a header. See: https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice. — AVH, Oct 22 '17 at 22:21

score 1 · Answer 1 · answered Oct 23 '17 at 02:04

There are many bugs of your code.

As @ytoledano commented, you should passing shared pointer as ref instead of by val.
isEmpty has if (t = nullptr) which should be (t == nullptr)
method contains and isEmpty didn't return bool, so this codes have compile error.

your remove method has logic error, your code will only find a child node to replace the deleted node when this node has both left and right. correct way should looks like that:

void remove(const E & x, shared_ptr<Node> &t){
    if(t == nullptr){
        return;
    }
    if (x < t-> data){
        remove(x, t-> left);
    }
    else if(t->data < x){
        remove(x, t-> right);
    }
    else if( t-> left != nullptr) {
        t-> data = findMax(t-> right) -> data;
        remove(t->data, t-> left);
    }
    else if(t->right != nullptr) {
        t-> data = findMin(t-> right) -> data;
        remove(t->data, t-> right);
    }
    else {
        t.reset();
    }
}

How to delete what my shared pointer is pointing to?

1 Answers1