CODEWITHSUNDEEP
c++pointerstreebinary-tree
ESD
ESD

Reputation: 545

binary tree recursive insertion mistake

I have this method to add a node in a binary tree and here in the example, I first add 4 which works right,then when I add 10 I got this : enter image description here

It first detect top != NULL which is correct, because there is 4 and then recall the method with top->droite in parameters(which is top->right). when it doesn't detect top as NULL and skip, its became what you see in the screen shot.As you can see the varibale is NULL.

What am I doing wrong?

Upvotes: 0

Views: 156

Answers (1)

Daniel Fleischman
Daniel Fleischman

Reputation: 657

By looking at the rest of the debug information, we can see that the left and right pointers of the new node are 0xcdcdcdcd, which, as far as I know, is the standard value for uninitiated pointers for debug builds in Visual Studio.

Your error is not initializing the pointers of the new node. Here is what is happening:

At the beginning top is NULL, and you insert the node whose nbr is 4. The new top is a node whose nbr is 4, but with the two pointers pointing to essentially garbage.

When you try to insert 10, it will correctly compare 10 with 4, and try to insert 10 at the right subtree of 4. This right subtree is not initialized, and hence the error.

One way to fix it is to make your code like this:

static void insertion(Noeud *&top, Noeud *newNoeud) {
   if (top == NULL) {
       top = newNoeud;
       top->droite = NULL;
       top->gauche = NULL;
   } else if (newNoeud->nbr < top->nbr)
       insertion(top->gauche, newNoeud);
   else
       insertion(top->droite, newNoeud);
}

Here is a complete example: http://ideone.com/5TDD49

Upvotes: 3

Related Questions