Insert struct data to bst node

**Vsky** · 01-02-2016

Code:

BstNode *insertData(BstNode *root, NodeData *data) {
    if(root == NULL) {
        root = NewBstNode(data);
    } else {
        if(memcpy(data->name, root->data->name, 1) <= 0) {
            root->left = insertData(root->left, data);
        } else {
            root->right = insertData(root->right, data);
        }
    }
    return root;
}

When program goes in to the code above it stops working and returns to -1073741819. First I thought it was about memcpy I deleted it and wrote 1 still got the error so I think problem is at 6th line where function calls itself. What might be the problem?

BstNode and NodeData:

Code:

struct NodeData {
    char name[99];
};


struct BstNode {
    NodeData *data;
    BstNode *left;
    BstNode *right;
};

**whiteflags** · 01-02-2016

Can you please paste a small, complete program that we can compile, which still exemplifies the problem? I'm becoming concerned because you have several snippets of code on different forums. I don't want to fix one version of the source code only for you to think you are working on the same version, but you actually have something different in the editor. We need to fix something that has a main() so that we're both working on common ground. Short, Self Contained, Correct Example

Another reason I am asking is because it is helpful to see how you are using the code you have shown so far. There may be other problems which you are not aware of.

**Vsky** · 01-02-2016

Originally Posted by whiteflags

Can you please paste a small, complete program that we can compile, which still exemplifies the problem? I'm becoming concerned because you have several snippets of code on different forums. I don't want to fix one version of the source code only for you to think you are working on the same version, but you actually have something different in the editor. We need to fix something that has a main() so that we're both working on common ground. Short, Self Contained, Correct Example

Another reason I am asking is because it is helpful to see how you are using the code you have shown so far. There may be other problems which you are not aware of.

The only reason I don't share full code is that I don't want to make post more complicated than intended. So I only share the part of code which causes problem. But since you asked here a code you can compile:

Code:

#include <iostream>
#include <stdio.h>
#include <string.h>


using namespace std;


struct NodeData {
    char name[99];
};


struct BstNode {
    NodeData *data;
    BstNode *left;
    BstNode *right;
};


BstNode *NewBstNode(NodeData*);
BstNode *insertData(BstNode*, NodeData*);
void serialize(BstNode*, FILE*);
void deSerialize(BstNode*&, FILE*);
bool searchData(BstNode*, NodeData*);


int main() {
    BstNode *root = NULL;
    NodeData *data = NULL;
    cin>>data->name;
    insertData(root, data);
    cin>>data->name;
    insertData(root, data);
    FILE *fp = fopen("db.bin", "w");
    serialize(root, fp);
    return 0;
}


BstNode *NewBstNode(NodeData *data) {
    BstNode *newNode = new BstNode();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}


BstNode *insertData(BstNode *root, NodeData *data) {
    if(root == NULL) {
        root = NewBstNode(data);
    } else {
        if(memcpy(data->name, root->data->name, 1) <= 0) {
            root->left = insertData(root->left, data);
        } else {
            root->right = insertData(root->right, data);
        }
    }
    return root;
}


void serialize(BstNode *root, FILE *fp) {
    fwrite(root, sizeof(struct BstNode), 1, fp);
    serialize(root->left, fp);
    serialize(root->right, fp);
}
void deSerialize(BstNode *&root, FILE *fp) {
    NodeData *data = NULL;
    if(!fread(data, sizeof(struct BstNode), 1, fp))
        return;
    root = NewBstNode(data);
    deSerialize(root->left, fp);
    deSerialize(root->right, fp);
}


bool searchData(BstNode*, NodeData*) {
    return false;
}

I didn't start writing search function yet. Inside main when you get to the line "insertData(root, data);" it goes to that function and at 6th line in that function program stops. So I thought there is something I did wrong with pointers and references at that line hence shared only that function.

**whiteflags** · 01-02-2016

Well the program segfaults here:

Code:

int main() {
    BstNode *root = NULL;
    NodeData *data = NULL;
    cin>>data->name;

In GDB I get a segmentation fault after typing:

Code:

Breakpoint 1, main () at sandbox.cpp:30
(gdb) s
(gdb) s
foobar

Program received signal SIGSEGV, Segmentation fault.
0x6fcb4ec9 in libstdc++-6!_ZStrsIcSt11char_traitsIcEERSt13basic_istreamIT_T0_ES6_PS3_ () from C:\TDM-GCC-32\bin\libstdc++-6.dll

cin cannot read data into a NULL pointer. After you actually allocate the tree, if the problem is gone, then we are done here.

Edited to add:
Although I can clearly see that there will be more problems in the serialize function.

deserialize is actually a good reference, considering the next problem. You should not be calling functions that create nodes in serialization. Use the root you were given. It should be non-NULL by the time you serialize.

In fact, you may be making several missteps by not writing strings, and pointed to objects directly. Do not end up with an address in your binary file. It will not work the next time around - when you go to read the binary file.

A good way to serialize strings is actually just to write them after their size.

Code:

size_t n = sizeof node->data;
fwrite(&n, sizeof n, 1, fp);
fwrite(data->name, sizeof(data->name), 1, fp);

Yes, it makes things a little tedious by unpacking your struct, but the left and right pointers are also trouble. Don't even bother. You might want to just traverse the tree in a breadth-first fashion, though, so the tree maintains its shape in the file. It makes it easier to use the file when you read it back.

**Vsky** · 01-02-2016

So I'm going to change

cin with scanf
and
root = NewBstNode(data); with root->data = data; ?

I don't see the difference btw. root = NewBstNode(data); should work too it's creating new node at another function and returns it to root so practically aren't they same ?

**Salem** · 01-02-2016

> if(memcpy(data->name, root->data->name, 1) <= 0)
Perhaps you meant memcmp() and not memcpy()

> #include <stdio.h>
> #include <string.h>
This is C++, so use the namespace enabled versions
#include <cstdio>
#include <cstring>

**Vsky** · 01-02-2016

Okay I fixed the code a lot. At least right now it compiles and works. Just doesn't work as intended. I have problem with serialize and deserialize functions. I don't know which one is wrong this pointer, reference things really messed my head since the morning. This is the last code:

https://ideone.com/J4xKVu

I entered example for serializing and deserializing inside the main. I guess I am not sending the actual values into db.bin but sending pointer. But I tried changing it couldn't succeeded. Any idea ?

**whiteflags** · 01-02-2016

Originally Posted by Vsky

So I'm going to change

cin with scanf

This will not fix the problem.

You need to actually make a tree.

Code:

NodeData *newData = new NodeData;
cin >> setw(99) >> newData->name;

Only after something like this will you be able to read in a name.

In general, you seem to be new with pointers. I really recommend watching this video so that you understand what you are doing wrong. Your lack of understanding in pointers is really sabotaging your attempt at making a working binary tree.

and
root = NewBstNode(data); with root->data = data; ?

I don't see the difference btw. root = NewBstNode(data); should work too it's creating new node at another function and returns it to root so practically aren't they same ?

No, they are absolutely not the same. I will start with the problem.

You are passing around a bunch of NULL pointers to your functions. The problem is that you cannot do much interesting with a NULL pointer. It cannot be dereferenced without causing a segmentation fault. This is why I think you need to watch the video, it will show you that pointers need to be allocated. (Perhaps the linked resources on binary trees will help you too. They are good resources.)

Still, the NewBstNode(data) line needs to be removed. If you do:

root = NewBstNode(data);

inside serialize() you will only run into more trouble. The original tree is lost, and instead root would point to a solitary node. So, it really runs contrary to the idea of serialize() - to write an existing tree to a file.

**Vsky** · 01-02-2016

@whiteflags

I changed most of the things this is current form:

https://ideone.com/J4xKVu

I've seen that there were a lot of errors. Right now program I can create tree and get to its leaves. You can try adding couple datas and printing them root->data->name, root->left->data->name etc. I've seen no problem so far. But serialize and deserialize functions doesn't work or at least one of them. I can't really print the actualy leaves into file. Output is some pointless ANSII characters when I try to deserialize and print root->data->name to screen.

**whiteflags** · 01-02-2016

I saw that you posted new code... but in general, the problem with the pointer use is remaining. If I were you, I would still watch the video. There are many things wrong and I still think an outside voice would be able to take it slower than I will, and that alone will probably help you more.

Your code:

Code:

BstNode *NewBstNode(NodeData *data) {
    BstNode *newNode = new BstNode();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Can you make the function like this? It is unclear to me where the data comes from.

Code:

#include <algorithm>
#include <cstring>

BstNode *NewBstNode(const char *buffer) {
   BstNode *newNode = new BstNode;
   std::copy(buffer, &buffer[std::strlen(buffer) + 1], newNode->data);
   newNode->left = newNode->right = NULL;
   return newNode;
}

That's at least a little better--we aren't quite going in circles the way we were before. Using the new function, you would be prevented from calling it with no input at all. I don't mean to cause problems by using copy() - feel free to use strncpy() if you must. I'm trying to infuse more C++ as this is supposed to be the C++ board. And generally, writing C++ like this is not the greatest thing in the world. You're learning a programming style from the 1980s - before C++ was standardized.

The insert function I have problems with:

Code:

BstNode *insertData(BstNode *root, NodeData *data) {
    NodeData *realdata = new NodeData();
    *realdata = *data;
    // ...
}

So you passed in a perfectly good node, data, and for some reason, you create an entirely new node.

Code:

BstNode *insertData(BstNode *root, NodeData *data) {
    if(root == NULL) {
        root = data;
    } else {
        if(memcmp(data->name, root->data->name, 1) <= 0) {
            root->left = insertData(root->left, data);
        } else {
            root->right = insertData(root->right, data);
        }
    }
    return root;
}

// in main:
root = insertData(root, BstNewNode("some string"));

Code such as this would work okay I believe.

**whiteflags** · 01-02-2016

You read real fast, so I hope my edits made it in time...

**Vsky** · 01-02-2016

Your code:

Code:

BstNode *NewBstNode(NodeData *data) {
    BstNode *newNode = new BstNode();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Can you make the function like this? It is unclear to me where the data comes from.

Data comes from where ever I call this function. This function looks simple to me I didn't understand which part looked unclear to you or maybe I wrote it wrong but this is my point of view: You get data as parameter which is actually another struct then create newnode and assign data you took with parameter to the newnode's data. Also make left and right values NULL then return the node. I didn't encounter any problem while using this but maybe I should use newNode->data = *data; ??

Code:

#include <algorithm>
#include <cstring>

BstNode *NewBstNode(const char *buffer) {
   BstNode *newNode = new BstNode;
   std::copy(buffer, &buffer[std::strlen(buffer) + 1], newNode->data);
   newNode->left = newNode->right = NULL;
   return newNode;
}

I didn't understand what you did here. NewBstNode function's job should be creating a new node and giving its data. At this function you are taking char as a parameter. Note that my data is not char but another struct. It currently has only char name[99] but I will add other arrays there I kept it small for testing purposes.

The insert function I have problems with:

Code:

BstNode *insertData(BstNode *root, NodeData *data) {
    NodeData *realdata = new NodeData();
    *realdata = *data;
    // ...
}

So you passed in a perfectly good node, data, and for some reason, you create an entirely new node.

I didn't create new node here. Notice that it isn't new node but new data. I am doing this because instead of creating new data inside main, I created only 1 data inside main that I use as buffer and then create 2nd one inside insertData function. Basically when you have 50 entries instead of creating 50 new data inside main I choose to create 1 inside main and 50 inside insertData function. An extra 1 struct isn't problem and makes the code much clearer for me.

Code:

// in main:
root = insertData(root, BstNewNode("some string"));

Code such as this would work okay I believe.

As I said my data isn't char array but another struct that contains char array in it for the moment. So I cannot use this.

Gathering all up I still don't see what I'm doing wrong. Maybe I should use

Code:

newNode->data = *data;

instead of

Code:

newNode->data = data;

I'll try that in a sec now but don't think it will solve anything as I said aside from serialize, deserialize thingy program works at least worked at my tests. I used insertData couple times to create nodes then used search to find those and result was positive. I'll watch the video too btw. Also thanks for being patient with me

Edit: Cannot make newNode->data = *data; gives error also I tested the code again it's working. These are the steps I took to test it:

Code:

    BstNode *root = NULL;
    NodeData *data = new NodeData();


    cin>>data->name;
    root = insertData(root, data);
    cin>>data->name;
    root = insertData(root, data);
    cout<<root->right->data->name;

2 stdin 1 stdout
boo,foo = foo
boo,aoo = CRASH (since there is nothing at right because aoo goes to left)

So there is no problem. But the problem is if I serialize this tree then deserialize it after cleaning the main all I see is random ANSII chars if I cout<<root->right->data->name;

That is why I am thinking there is problem with serialize or deSerialize function.

Edit 2:

I found major mistake inside deSerialize

Code:

void deSerialize(BstNode *&root, FILE *fp) {
    NodeData *data = new NodeData;
    if(!fread(data, sizeof(struct BstNode), 1, fp))
        return;
    root = NewBstNode(data);
    deSerialize(root->left, fp);
    deSerialize(root->right, fp);
}

Well this is just so stupid. I am really beginner not to mention didn't use c++ often and on top of those trying to make this over hours can cause stupid mistakes like this :P First of all I am trying to read data here. I even entered sizeof(struct BstNode) but still put there NodeData. I gotta read root not data so deleted first line and that root = NewBstNode(data) line. Also changed data with root so I'm left with.

Code:

void deSerialize(BstNode *&root, FILE *fp) {
    if(!fread(root, sizeof(struct BstNode), 1, fp))
        return;
    deSerialize(root->left, fp);
    deSerialize(root->right, fp);
}

And program crashes while trying to deSerialize now. I guess the problem is here and if I fix this part it'll work as intended.

**whiteflags** · 01-02-2016

I didn't create new node here. Notice that it isn't new node but new data. I am doing this because instead of creating new data inside main, I created only 1 data inside main that I use as buffer and then create 2nd one inside insertData function. Basically when you have 50 entries instead of creating 50 new data inside main I choose to create 1 inside main and 50 inside insertData function. An extra 1 struct isn't problem and makes the code much clearer for me.

I see. I didn't really understand this from before and it's mostly my fault. In my defense, the example I asked you for segfaulted right away when it should have done enough to demonstrate the original problem with serialize and deserialize. Basically, you removed too much.

If you say that it works in testing then I will stop looking for problems with the tree itself.

Gathering all up I still don't see what I'm doing wrong. Maybe I should use [...]

No, the stuff about the tree itself is a red herring. Instead I'd like you to follow the advice that I said about serialize and deserialize that I said from earlier (post #4), which hasn't been done as far as I can tell.

Currently you are writing BstNode down onto a binary file. This is bad because BstNode is just a bunch of memory addresses. Look at the declaration.

Code:

struct BstNode {
    NodeData *data;
    BstNode *left;
    BstNode *right;
};

While the data is useful, a pointer only stores the object's address. It does not actually contain the name and other items (in effect you need to dereference before you get to these items). You would not want to write down addresses. Memory will not be consistent between runs of your program, so in effect, you will not be saving anything useful. The same goes for left and right pointers. The addresses to nodes may not be consistent between runs, so don't bother saving these.

Rather, you need to do a big rewrite on the serialize function. As I explained before:

A good way to serialize strings is actually just to write them after their size.

Code:

size_t n = sizeof node->data;
fwrite(&n, sizeof n, 1, fp);
fwrite(data->name, sizeof(data->name), 1, fp);

Yes, it makes things a little tedious by unpacking your struct, but the left and right pointers are also trouble. Don't even bother. You might want to just traverse the tree in a breadth-first fashion, though, so the tree maintains its shape in the file. It makes it easier to use the file when you read it back

It must be realized that serialize and deserialize are not doing enough work.

You could simply write NodeData down to the file, but that would mean that the declaration of NodeData should not change - basically, files generated with different versions of NodeData would not be compatible. That is very inflexible.

**Vsky** · 01-03-2016

@whiteflag

Thanks for the answer. It took me longer than it should to figure that out but finally I understood. I'll just send the data 1 by 1 into text file I guess. I was avoiding it because right now there is only char name[99] inside NodeData but I'll put at least 10 more arrays there so saving them all at once could be a lot easier. After talking with some people on c++ irc channels they told me that saving struct is not portable and not good thing to do ever. I don't know why our teachers thought us that, or at least why they didn't warn about the portability problems. So currently I'll be writing code from scratch and see what happens. Thanks for your patience.

Thread: Insert struct data to bst node

Thread Tools

Search Thread

Display

Insert struct data to bst node

Similar Threads

linked list insert node between two nodes.

Insert a node into the end of a linked list

Insert node in a linked list.

correct order to insert new node?

Insert node and delete problem <HURRY!!> <pls HELP>>