Linked list binary tree..

I have this binary tree struct declaration:

Code:

typedef struct _bnode{ char *name; int value; struct _bnode *left; //left child struct _bnode *right; //right child struct _bnode *prev; struct _bnode *next; } BNODE;

I need to add a sentinal node so this is how i did it.. not sure if im doing it right..

Code:

typedef struct _sent{ struct _bnode *sent; } SENT;

I need the linked list part of the struct to point to all "values" in sorted order.. the binary tree part points to different nodes.. so im really confused..

Here is my insert function:

Code:

BNODE *tree_insert(char *key, void *value, void *tree){ BNODE *root = (BNODE *)tree; //cast the given void tree to a BNODE if(root == NULL){ root = (BNODE *)malloc(sizeof(BNODE)); if(root != NULL) { root->name = strdup(key); root->left = NULL; root->right = NULL; } }else if(root->name == NULL){ root->left = tree_insert(key, value, root->left); }else{ if(strcmp(key, root->name) < 0){ root->left = tree_insert(key, value, root->left); }else if(strcmp(key, root->name) > 0){ root->right = tree_insert(key, value, root->right); }else if(strcmp(key, root->name) == 0){ root->name = strdup(key); } } return root; }

somewhere in that function.. i need to set my pointers for the linked list part and i really dont know how to.. im so lost.. please help?

Any particular reason for combining a binary tree and a doubly linked list in the same node especially since the binary tree is sorted.

Quote:

Originally Posted by itCbitC

Any particular reason for combining a binary tree and a doubly linked list in the same node especially since the binary tree is sorted.

was asked to do it this way.. :(

So, you're writing a fully threaded tree...

One idea is to write two functions. The first one is recursive and doesn't actually do the insert, it instead finds either a node with the same key, or the closest matching node, and it returns the node it found. (or null if the tree is empty)
Then your other function is responsible for calling the recursive one and then it uses the ndoe returned from that, to insert the new node both into the tree and the list simultaneously.

To do that, you:
Work out which side of the node function 1 found. Lets assume it has to go on the right. Find it's right neighbour by following that node's existing next link.
Okay, now insertion into the list is easy, allocate your new item and set up its prev an next links to those two nodes, and adjust those two nodes to point to the new one.
Then since in this case it goes on the right of the node you found you can set the right link of that node to point to your new node.
Your new node's left and right will be NULL of course.
Make sense?
You can work out the special case for when the root is NULL.

E.g.

Code:

4 / \ 2 6 / \ \ 1 3 7

Say you want to insert 5.
You go right of 4 because 5 is greater, then you look at 6 and see that 5 would be left of there but the left pointer is NULL, so you return that node. Now follow 6's prev pointer and that'll get you to node 4. Then adjust 4's next to point to 5, and adjust 6's prev to point to 5. Actually I'm sure you get the idea by now...

Actually, you can do the first part iteratively and then put the whole thing in one function. It should be more efficient that way.

The sentinel is needed for when you went to insert say 0 or 8 into this data structure. You'd follow 1's prev and that has to be a real node (not just a pointer) so you can set it's next pointer. You use the same sentinel node at BOTH ends of the list.

Quote:

Originally Posted by iMalc

So, you're writing a fully threaded tree...

One idea is to write two functions. The first one is recursive and doesn't actually do the insert, it instead finds either a node with the same key, or the closest matching node that does not have two children, and it reuturns the node it found. (or null if the tree is empty)
Then your other function is responsible for calling the recursive one and then it uses the ndoe returned from that, to insert the new node both into the tree and the list simultaneously.

To do that, you:
Work out which side of the node function 1 found. Lets assume it has to go on the right. Find it's right neighbour by following that node's existing next link.
Okay, now insertion into the list is easy, allocate your new item and set up its prev an next links to those two nodes, and adjust those two nodes to point to the new one.
Then since in this case it goes on the right of the node you found you can set the right link of that node to point to your new node.
Your new node's left and right will be NULL of course.
Make sense?
You can work out the special case for when the root is NULL.

E.g.

Code:

4 / \ 2 6 / \ \ 1 3 7

Say you want to insert 5.
You go right of 4 because 5 is greater, then you look at 6 and see that one of its children is NULL, so you return that node. Now follow 6's prev pointer and that'll get you to node 4. Then adjust 4's next to point to 5, and adjust 6's prev to point to 5. Actually I'm sure you get the idea by now...

The sentinel is needed for when you went to insert say 0 or 8 into this data structure. You'd follow 1's prev and that has to be a real node (not just a pointer) so you can set it's next pointer. You use the same sentinel node at BOTH ends of the list.

doesnt my insert function do what you are describing in the second part?
what about this for the first part.. this is my find function:

Code:

BNODE *tree_find(char *key, void *tree){ BNODE *root = (BNODE *)tree; if(root == NULL){ return 0; }else if(root->name == NULL) return tree_find(key, root->left); else if(strcmp(key, root->name) < 0){ return tree_find(key, root->left); //look in the left side }else if(strcmp(key, root->name) > 0){ return tree_find(key, root->right);//look in the right side }else{ return root; } }

so do I call the find function in my insert function?
how do i set the sentinel node and the next/prev pointers???

Quote:

Originally Posted by scarlet00014

doesnt my insert function do what you are describing in the second part?

No, it's more like the first part, but it wont do because it returns NULL when the item is not found and the tree is not empty. You'd need it to return the node that the new one will hang off instead. Thinking about it more, I'd now recommend writing the insert function to make it iterative instead of recursive. Recursion is useful when you're going down more than one branch, such as when you're printing out the whole tree, or when you need to do something on your way back up the tree. Neither of those are the case here. You simply find your way down through the tree and then when you reach the node that needs to have a child attached to it, you attach the node and then stop treating the tree as a tree and start treating it as a doubly-linked list, of which you have a node from, and can go forwards and backwards from, at will.

Quote:

what about this for the first part.. this is my find function:

Code:

BNODE *tree_find(char *key, void *tree){ BNODE *root = (BNODE *)tree; if(root == NULL){ return 0; }else if(root->name == NULL) return tree_find(key, root->left); else if(strcmp(key, root->name) < 0){ return tree_find(key, root->left); //look in the left side }else if(strcmp(key, root->name) > 0){ return tree_find(key, root->right);//look in the right side }else{ return root; } }

so do I call the find function in my insert function?
how do i set the sentinel node and the next/prev pointers???

You set up the sentinel node when you insert the first item. At that point, both prev and next from the sentinel point to the node you inserted, and the prev and next of the node you inserted both point to the sentinel. That's it! Once you do that, the rest of the list insertion just works, and doesn't even have to know the sentinel exists.

Your find function would be more efficient if it was iterative as well btw.

Oh, this isn't a self-balancing binary tree is it?

Quote:

Originally Posted by iMalc

You set up the sentinel node when you insert the first item.

like in the actual program? do i send in the sentinel node? or should i send in the sent->next's node

Quote:

Oh, this isn't a self-balancing binary tree is it

i dont think so.. not really sure

Quote:

Originally Posted by scarlet00014

like in the actual program? do i send in the sentinel node? or should i send in the sent->next's node

Okay it wont be a self-balancing binary tree. Those are a lot harder anyway!

You don't need to pass in the sentinel node. It's something you access from your insert function as if it were a global. You could perhaps make it a static variable in the insert function later, but for now just access it like a global. If this were C++ it would be part of the class.
You can just set it up like this, and these are the only lines of code that know anything about sent besides where it is declared. Remember sent should be an actual BNODE, not just a pointer.

Code:

root = malloc(sizeof(BNODE)); if(root != NULL) { root->name = strdup(key); root->left = root->right = NULL; root->prev = root->next = &sent; sent.prev = sent.next = root; }

Quote:

Originally Posted by iMalc

Remember sent should be an actual BNODE, not just a pointer.

Ok im a little lost.. how is sent declared if its just a BNODE.. is it declared in the program or inside that particular function? how do i send it in?

Quote:

Originally Posted by scarlet00014

Ok im a little lost.. how is sent declared if its just a BNODE.. is it declared in the program or inside that particular function? how do i send it in?

A global variable is one that is not declared inside a function. You could do it that way, and then you don't need to pass it in.
However that does prevent you from constructing more than one tree easily, so if you really want to pass it in, you can pass in the address of it to a pointer parameter. It probably just makes things more cluttered like that though.
Either way, when it's declared you probably just want it to be "BNODE sent;" as dynamically allocating it doesn't really give you any advantage.