C++

Forum

 
Pointer initialized to 0 doesn't change after dynamic allocation

Hotice (154)
I am trying to make a binary search tree. I have a struct for nodes of a tree defined as such:

1
2
3
4
5
6
7
8
9
10
11
 
struct node
{
    node()
    {
        //making leftNode, rightNode null by default
        leftNode = 0;
        rightNode = 0;
    }
    node * leftNode, *rightNode;
    int value;
};


My buildBST(node*) is defined as:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
void BSTTest::buildBST(node * pointer, int n)
{
    if (index < vectorSize)
    {
        //base case
        if ((pointer == 0) || (n == 0))
        {
            if (pointer == 0) pointer = new (std::nothrow) node();
            //assigning the current spot in the data to pointer->value and incrementing the index (on the same line)
            std::cout << "Adding value " << (pointer->value = data[index++]) << " to the tree." << std::endl;
            //test statements
            std::cout << "pointer->leftNode == " << pointer->leftNode << std::endl;
            std::cout << "pointer->rightNode == " << pointer->rightNode << std::endl;
            if (n > 0) std::cout << "pointer == " << pointer << std::endl;
            //calling this function again, with the incremented index
            buildBST(tree, index);
        }
        else
        {
            //if the data value is less than that of the current node
            if (data[index] < pointer->value)
            {
                //pointer->leftNode = new (std::nothrow) node;
                buildBST(pointer->leftNode, index);    //check the leftNode
            }
            else
            {
                if (data[index] > pointer->value)
                {
                    //pointer->rightNode = new(std::nothrow) node;
                    buildBST(pointer->rightNode, index);   //if it is greater, check the rightNode
                }
                else
                {
                    //in the case that the two values are equal, we not only discard the equal value, but decrement vectorSize as well
                    data.erase(data.begin() + index);
                    vectorSize--;
                }
            }
        }
    }
}


which seems to initialize the root node and all the child nodes that are to be used, but for some reason, when I call my printBST (given below):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
void BSTTest::printNode(node * ptr)
{
    //from here, we are using in-order traversal and assume that the garbage value will NEVER appear in the data vector
    if(ptr != 0)
    {
        printNode(ptr->leftNode);   //first, we visit the leftNode (if it doesn't have that garbageValue for its value
        std::cout << ptr->value << " ";    //then, we print the character that is already there (again, assuming its value is not the garbageValue)
        printNode(ptr->rightNode);  //and then conclude with visiting the rightNode
    }
}

void BSTTest::printBST()
{
    //This is for testing...
    std::cout << "this->data.size() == " << this->data.size() << std::endl;
    std::cout << "tree->leftNode == " << tree->leftNode << std::endl;
    std::cout << "tree->rightNode == " << tree->rightNode << std::endl;
    //printing tree
    std::cout << "The generated binary search tree looks like this (using in-order traversal):\n" << std::endl;
    printNode(tree);
}

only one node gets printed and it seems as if all other nodes are still null! Don't null pointers get assigned a non-zero value when dynamically allocated? (NOTE: I could have checked if(pointer == NULL), but NULL is a macro that simply expands to 0: http://www.cplusplus.com/reference/cstddef/NULL/?kw=NULL .)

Where did I go wrong?
Last edited on
closed account (28poGNh0)
Can you give us the whole code?
closed account (o1vk4iN6)
How do you call buildBST ? If you don't pass a valid object to it, you won't get anything. The function prone to memory leaks for that case.

1
2
3
4
5
 

Node* node = nullptr;

buildBst(node, 0); // won't work, node will stay nullptr


Also you shouldn't use 0 to set a pointer, NULL is better to give context to someone else reading your code. If you are using C++11 or above a new keyword "nullptr" was introduced to avoid some problems caused by having a macro simply define an integer.
Last edited on
Hotice (154)
Can you give us the whole code?


Sure. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
#include "include\BSTTest.h"
#include <iostream>
#include <new>
#include <vector>

BSTTest::BSTTest(std::vector<int> data)
{
    //passing data into the class
    this->data = data;
    //initializing all variables
    index = 0;
    vectorSize = data.size();
    //attempt to call private function from inside the constructor
    //tree = new(std::nothrow) node;
    tree = new (std::nothrow) node();
    buildBST(tree, index);
}

void BSTTest::buildBST(node * pointer, int n)
{
    if (index < vectorSize)
    {
        //base case
        if ((pointer == 0) || (n == 0))
        {
            if (pointer == 0) pointer = new (std::nothrow) node();
            //assigning the current spot in the data to pointer->value and incrementing the index (on the same line)
            std::cout << "Adding value " << (pointer->value = data[index++]) << " to the tree." << std::endl;
            //test statements
            std::cout << "pointer->leftNode == " << pointer->leftNode << std::endl;
            std::cout << "pointer->rightNode == " << pointer->rightNode << std::endl;
            if (n > 0) std::cout << "pointer == " << pointer << std::endl;
            //calling this function again, with the incremented index
            buildBST(tree, index);
        }
        else
        {
            //if the data value is less than that of the current node
            if (data[index] < pointer->value)
            {
                //pointer->leftNode = new (std::nothrow) node;
                buildBST(pointer->leftNode, index);    //check the leftNode
            }
            else
            {
                if (data[index] > pointer->value)
                {
                    //pointer->rightNode = new(std::nothrow) node;
                    buildBST(pointer->rightNode, index);   //if it is greater, check the rightNode
                }
                else
                {
                    //in the case that the two values are equal, we not only discard the equal value, but decrement vectorSize as well
                    data.erase(data.begin() + index);
                    vectorSize--;
                }
            }
        }
    }
}

void BSTTest::printNode(node * ptr)
{
    //from here, we are using in-order traversal and assume that the garbage value will NEVER appear in the data vector
    if(ptr != 0)
    {
        printNode(ptr->leftNode);   //first, we visit the leftNode (if it doesn't have that garbageValue for its value
        std::cout << ptr->value << " ";    //then, we print the character that is already there (again, assuming its value is not the garbageValue)
        printNode(ptr->rightNode);  //and then conclude with visiting the rightNode
    }
}

void BSTTest::printBST()
{
    //This is for testing...
    std::cout << "this->data.size() == " << this->data.size() << std::endl;
    std::cout << "tree->leftNode == " << tree->leftNode << std::endl;
    std::cout << "tree->rightNode == " << tree->rightNode << std::endl;
    //printing tree
    std::cout << "The generated binary search tree looks like this (using in-order traversal):\n" << std::endl;
    printNode(tree);
}

void BSTTest::destroyTree()
{
    std::cout << "\nPerforming garbage collection..." << std::endl;
    //call private helper function that deletes the leaves first
    destroyTree(tree);
    std::cout << "Garbage collection completed successfully." << std::endl;
}

void BSTTest::destroyTree(node * leaf)
{
    if (leaf != 0)
    {
        destroyTree(leaf->leftNode);
        destroyTree(leaf->rightNode);
        delete leaf;
    }
}


The relevant code in my main() is simply:
1
2
3
4
 
//make a binary search tree of all this 
BSTTest test(data);
test.printBST();    //print the data
test.destroyTree(); //perform garbage collection


I am thinking that (and I have done this in the past, in a BST program that didn't use classes) I could simply test for the null pointer. //It worked for me in the past, and I have no idea why it isn't working now.

How do you call buildBST ? If you don't pass a valid object to it, you won't get anything. The function prone to memory leaks for that case.

1
2
3
 
Node* node = nullptr;

buildBst(node, 0); // won't work, node will stay nullptr


Also you shouldn't use 0 to set a pointer, NULL is better to give context to someone else reading your code. If you are using C++11 or above a new keyword "nullptr" was introduced to avoid some problems caused by having a macro simply define an integer.


Then how am I supposed to check if the value is a fresh value (and that I should even insert anything there)? Values? Using values would give my code a chance to be error-prone. //what if the data I insert just so happened to have the same value as that new node where I am trying to insert it?
closed account (o1vk4iN6)
Using values would give my code a chance to be error-prone.

It already is error prone in the example I gave, lots of ways the function you created can cause memory leaks and even with checking the input you can still create memory leaks. Not the best interface.


Anyway looking at the code again saw something I missed before:

1
2
3
4
5
6
7
8
9
10
11
 
        if ((pointer == 0) || (n == 0))
        {
            if (pointer == 0) pointer = new (std::nothrow) node();
            std::cout << "Adding value " << (pointer->value = data[index++]) << " to the tree." << std::endl;

            std::cout << "pointer->leftNode == " << pointer->leftNode << std::endl;
            std::cout << "pointer->rightNode == " << pointer->rightNode << std::endl;
            if (n > 0) std::cout << "pointer == " << pointer << std::endl;

            buildBST(tree, index); // <------ being called with tree, think you meant to put pointer here.
        }

Hotice (154)
If I used buildBST(pointer, index);, wouldn't that mean that, for the next value searched, it would start at pointer, and then work its way down to the subnodes? What if, for example the data looked like {24, 48, 16}, index == 2, and then we pass pointer as argument? Then the address of the node whose value is 48 would be used, which means that a node whose value is 16 would be assigned as the left subnode of that! This is clearly NOT what a binary search tree should look like! In-order traversal of a binary search tree should sort the data...

Oh, and I am not using C++11.
keskiverto (10363)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
void foo( int * pointer )
{
  pointer = new int;
  *pointer = 7;
}

void bar(  int * pointer )
{
  *pointer = 42;
}

int main()
{
  int a = 0;
  int *b = &a;
  bar( b );
  assert( 42 == a );

  int *p = 0;
  foo( p );
  assert( 0 == p );  // This is not the memory location you were looking for
}

Edit: If you still wonder why:
The foo() takes a parameter. That parameter is a local variable of foo and it is a pointer. It is initialized by the caller with a memory address. A copy of address. You can dereference the pointer to adjust the value in that memory location, but you cannot manipulate the variable in the caller that the address was copied from.

If you want to modify a pointer variable of the caller, then you have to make a reference (or pointer) to that pointer.
Last edited on
Hotice (154)
Reference to pointer solved the problem! Thank you very much!! //Now, I can get to making a parsing tree!!

I will leave this, http://www.codeproject.com/Articles/4894/Pointer-to-Pointer-and-Reference-to-Pointer , here in case any other newbs view this thread.
Topic archived. No new replies allowed.