CODEWITHSUNDEEP
c++pointersdata-structuresbinary-tree
daniel gratzer
daniel gratzer

Reputation: 53881

Errors with Pointers

I have been working on a simple binary search tree for a larger project. I understand the concept of a binary search tree and am simply having troubles with syntax of implementing in C++. I am deliberately not using boost's tree containers. My code for the tree is as follows.

  struct Tree{
int nodeValue;
Tree *nodeChild1;
Tree *nodeChild2;
Tree(int userProvidedValue){
    nodeValue = userProvidedValue;
    nodeChild1 = NULL;
    nodeChild2 = NULL;
}
static void placeValue(Tree &parent, int value);
static Tree findValue(Tree parent, int value);
static void crawl(Tree parent);
~Tree(){

    delete nodeChild1;
    delete nodeChild2;
}
};

 void Tree::placeValue(Tree &parent, int value){
Tree node = Tree(value);
cout<<"made node"<<endl;
if(value>parent.nodeValue){
    cout<<"eval node child 2"<<endl;
    if(parent.nodeChild2 ==NULL){
        cout<<"reaching this";
        parent.nodeChild2 = &node;
    }
    else{
        placeValue(*parent.nodeChild2, value);
    }
}
if(value<=parent.nodeValue){
    cout<<"eval node child 1"<<endl;
    if(!parent.nodeChild1){
                cout<<"assigning"<<endl;
                parent.nodeChild1 = &node;
    }
            else{
                        placeValue(*parent.nodeChild1, value);
            }
        }
}

However whenever I construct a tree with Tree parent = Tree(5) then add another node to it with Tree::placeValue(parent, 4) it compiles fine but a message pops up telling me that the exe has crashed.

Can anyone please help me understand where this crashing is coming from? Thanks in advance.

The code to crawl through the tree looks like this:

void Tree::crawl(Tree parent){
cout<<parent.nodeValue<<endl;
if(NULL!=parent.nodeChild1){
    crawl(*parent.nodeChild1);
}
if(NULL!=parent.nodeChild2){
    crawl(*parent.nodeChild2);
}
}

Bonus Question: When Tree::crawl takes the argument of Tree &parent instead of Tree parent it runs fine. However without the & however it fails. Can anyone please explain why this is so?

Upvotes: 1

Views: 130

Answers (3)

Dmitriy Kachko
Dmitriy Kachko

Reputation: 2914

Tree node = Tree(value);

The node has scope of the program block it was declared in. It will be automatically deleled after exit out of the Tree::placeValue. When you get pointer on it (parent.nodeChild2 = &node;) it will point to nothing after the exit and attempt to dereference it will cause an undefined behavior. Create it dynamically like this:

Tree * node = new Tree(value);

Upvotes: 0

mfontanini
mfontanini

Reputation: 21900

You have to allocate Tree(s) on the heap.

Tree node = Tree(value);

Here you are allocating a Tree on the stack. This variable's address will be disposed after getting out of scope. In order to allocate it on the heap, just use the new operator:

Tree *node = new Tree(value);

And then assign it as a child of the parent:

parent.nodeChild2 = node;

Regarding the Tree::crawl error, it is based on the same error. You keep allocating Tree(s) on the stack, therefore once it goes out of scope its destructor is called, delete(ing) nodeChild1 and nodeChild2. You should manage these kinds of structures by either using pointers, or always using references, so that when a function ends, the Tree's destructor is not called. Therefore:

void Tree::crawl(const Tree &parent){
  cout<<parent.nodeValue<<endl;
  if(NULL!=parent.nodeChild1){
      crawl(*parent.nodeChild1);
  }
  if(NULL!=parent.nodeChild2){
      crawl(*parent.nodeChild2);
  }
}

This should do it. Remember to do the same on Tree::findValue, you should use this signature for that function:

static Tree findValue(const Tree &parent, int value);

Upvotes: 3

liwp
liwp

Reputation: 6926

You allocate your Tree() instance containing the new value on the stack, i.e. Tree node = Tree(value);. When the function call returns, that instance is destroyed, so when you try to access it later on, the program crashes.

Also, your destructor calls delete on both its children, so presumably you should allocate the Tree instance on the heap to fix your issue: Tree* node = new Tree(value);

Upvotes: 3

Related Questions