Acces Violation binary search tree template

Question

im pretty new with C++ , I've recently received a project to create my own Binary Search Tree using a Template. The goal is for the Binary Tree to be able to take in any kind of data type. I've created 2 classes , Node(h,cpp) ,Tree(h,cpp) , and a main cpp. for some reason i get all the time acces violation (probaly from of the destructor , it is getting a corrupted value).

... here is my code(its the whole thing so it whould be easier..) . thanks...

template <typename T>
std::ostream& operator<<(std::ostream& output, const Tree<T>& tree)
{
    if (!tree.getRoot())
        return output;
    Node<T> * temp=tree.getRoot();

    Tree<T>  tempL(temp->getL());
    output<<tempL;

    output<<temp->getValue();
    output<<endl;


    Tree<T> tempR(temp->getR());
    output<<tempR;


    return output;
}

#endif

#include "Tree.h"

void main ()
{
    Node<int> *no=new Node<int>(7);
    Tree<int> IntTree(no);
    IntTree.insert(new Node<int> (5));
    IntTree.insert(new Node<int> (0));
    IntTree.insert(new Node<int> (4));
    IntTree.insert(new Node<int> (5));
    IntTree.insert(new Node<int> (12));
    IntTree.insert(new Node<int> (7));
    IntTree.insert(new Node<int> (1));
    IntTree.insert(new Node<int> (14));
    IntTree.insert(new Node<int> (7));
    IntTree.insert(new Node<int> (51));
        if(IntTree.exists(5.1))
        cout<<IntTree;

}

Hint: Get the tree working with a fixed data type, such as `int`, then convert to template. A lot easier to **debug**. — Thomas Matthews, Jan 03 '17 at 18:13
When you used the debugger, which statement is causing the issue? — Thomas Matthews, Jan 03 '17 at 18:13
removeTree(node->getL()); get the debugger to stop... @ThomasMatthews Ive done it without before and it did worked... — user2323232, Jan 03 '17 at 18:16
When we are asking for [mcve], we are **not** asking you to do `Ctrl+A` followed by `Ctrl+C`. — Algirdas Preidžius, Jan 03 '17 at 18:20
@AlgirdasPreidžius I gave the whole could so it whould be easier for everyone who think can find the answer... — user2323232, Jan 03 '17 at 18:21
You do `removeTree(node->getL());` twice, instead of also removing the right subtree. — Bo Persson, Jan 03 '17 at 18:21
@user152711 Did you click the link in my comment? We are asking you to **manufacture** **minimal** yet complete, and verifiable example. If you don't put any effort into investigating the problem, or **manufacturing** said example, why should we? — Algirdas Preidžius, Jan 03 '17 at 18:24
@AlgirdasPreidžius dear friend, ive put 4 hours of trying to solve that issue, I explained the issue , and gave the whole code(it could be much easier to copy only that part since its 5 files!), so i did wroked on it.. — user2323232, Jan 03 '17 at 18:26
@user152711 Yet I don't see **manufactured** example that is both **minmal**, and complete. We don't need the whole code, since, typically, ~90-ish percent of such "example" isn't even called, and the real issue gets lost among that code. You may _say_ that you spent 4 hours, but I don't see any effort. — Algirdas Preidžius, Jan 03 '17 at 18:30
Also, in the output operator you create copies of the tree. That will create duplicates of the root pointers and then delete them in the destructors. That will delete the same pointer value several times. Generally, if you store raw pointers in objects, you must also have copy constructors and assignment operators that create deep copies of the things pointed to. See [The rule of three](http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three) — Bo Persson, Jan 03 '17 at 18:30

François Andrieux · Accepted Answer · 2017-01-03T18:44:56.067

It looks like the problem is nodes getting deleted twice. Inside operator<< for Tree<T> you create two trees named tempL and tempR. At the end of the operator's body those trees are destroyed. Those trees' destructors delete the nodes that were given to them. However, these nodes are not theirs to destroy as they also belong to the tree object that was given to operator<<. At the end of the operator call, whatever tree object was streamed now points to deleted nodes. I've annotated the operator's body to illustrate what I mean :

template <typename T>
std::ostream& operator<<(std::ostream& output, const Tree<T>& tree)
{
    if (!tree.getRoot())
        return output;
    Node<T> * temp=tree.getRoot();  // temp->getRoot() wil be deleted temp is destroyed
                                    // this will also destroy temp->getL() and temp->getR()
                                    // because of Node<T>'s destructor

    Tree<T>  tempL(temp->getL());   // will delete temp->getL() when tempL is destroyed
    output<<tempL;

    output<<temp->getValue();
    output<<endl;


    Tree<T> tempR(temp->getR());    // will delete temp->getL() when tempR is destroyed
    output<<tempR;


    // tempL and tempR are destroyed
    return output;
}

To solve this issue you should avoid making temporary trees in operator<<. Additionally, consider using smart pointers like std::shared_ptr and std::unique_ptr to avoid these kinds of headache.

Acces Violation binary search tree template

1 Answers1