CODEWITHSUNDEEP
cbinary-search-tree
Jo Jo
Jo Jo

Reputation: 67

How would I declare a new struct in this case?

This is what I have right now for my code (just a simple BST) 

typedef struct bsn{
    int val;
    struct bsn *left, *right;
} bsn_t;

typedef struct bst{
    bsn_t *root;
    int size;
} bst_t;

My question is that for the functions which I'll use, the input is an address like this

void init( bst_t * tree )

How would I use this? This is what I have right now but I'm not sure if it's correct or not

tree->size = 0;
tree->root = NULL;

Also for other functions like 

bool insert( bst_t *tree, int val )

I want to declare a temp node to use. Does this work?

bsn_t temp = (bsn_t *) malloc (sizeof (bsn_t));

And my last question is that how would I check if a node is null or not. I tried

bsn_t visitor = (bsn_t*)malloc(sizeof(bsn_t));
visitor = *tree->root;

Then doing 

if (visitor != NULL)

But when I compile it says that

'!=': illegal for struct

Please help..

Upvotes: 0

Views: 71

Answers (3)

user4434329
user4434329

Reputation:

How would I use this? This is what I have right now but I'm not sure if it's correct or not tree->size = 0; tree->root = NULL;

Yes this is the right way to use it. If you have a pointer you can access the struct elements with(->) operator otherwise, use . (dot) operator.

bsn_t temp = (bsn_t *) malloc (sizeof (bsn_t));

Yes this is the right way as well but you are missing a '*' before temp on left hand side which states that this is a pointer type variable. Remember, it will allocate the object in heap so you have to explicitly free that memory when you no longer need it. Also, note that casting the newly allocated memory to (bsn_t *) is optional, if you don't do, compiler will implicitly do it for you depending upon your l-value type.

bsn_t visitor = (bsn_t*)malloc(sizeof(bsn_t));

Again, it should be bsn_t *visitor on your left hand side.

visitor = *tree->root; Following that it should be *visitor = *tree->root; Also, try to make your code more readable by writing *(temp->root) instead of *temp->root.

if (visitor != NULL) Now you should be able to use this since visitor is a pointer now.

Upvotes: 0

M Oehm
M Oehm

Reputation: 29136

In your tree, the connections between the nodes and the connection from outside, i.e the root, are all pointers. They point to nodes that are allocated on the heap with malloc.

If you define a local variable like:

bsn_t temp;

you get a node on the stack that will be invalid after the returning from the function. In your case, you should never need to create nodes on the stack. You should work with pointers to nodes throughout, which point to existing nodes, to frshly allocated nodes or to nothing (NULL).

So:

bsn_t *temp = malloc (sizeof (bsn_t));

(I've removed the cast to (bsn_t *). It is strange that in the original code, you have cast the return value from malloc to a pointer type when assigning to a struct.)

As for your second question, your code:

bsn_t visitor = (bsn_t*)malloc(sizeof(bsn_t));
visitor = *tree->root;

is wrong in several places. First, as above, the visitor should be a pointer to a node, not a node struct.

Then the visitor is supposed to travel from the root down the tree. By doing so, it does not create any new nodes, so there is no need to malloc at all. Remember, malloc gives you new memory on the heap, in effect creating a node. The visitor just points to existing objects. One object can have more pointers pointing to them.

Even if malloc were the right ting to do, you shouldn't malloc and then overwrite the pointer that holds the (so far only) handle to the ne memory.

You've also got the * wrong. The visitor is a pointer ans tree->root is a pointer, too, so there's no need to dereference. What you have done is to copy the contents of the root to your local struct.

What you want to do is someting like this:

bsn_t *visitor = tree->root;

while (visitor != NULL) {
    // Do stuff

    visitor = visitor->right;    // or left, whatever
}

The use of asterisks in declaration and use may be confusing. In a declaration, you use a start to make a thing a pointer:

bsn_t node;      // uninitialised node struct on the stack
bsn_t *pnode;    // uninitialised pointer to node

After that, when you use the pointer variable, the unadorned name refers to the the pointer. An asterisk means that you dereference it to get at what the pointer points to. When you work with structures, you usually won't see many stars, because the -> syntax is preferred, but node->left is essentially the same as (*node).left.

Upvotes: 2

Amit
Amit

Reputation: 46361

You can't assign memory addresses (The return value from a malloc call) to struct typed variables. You need to assign these to pointer typed variables.

bsn_t *temp = (bsn_t *) malloc (sizeof (bsn_t));

bsn_t *visitor = (bsn_t*)malloc(sizeof(bsn_t));

Then you won't have compile time errors.

Upvotes: 0

Related Questions