Thread: Linked list binary tree..

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    58

    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?

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Any particular reason for combining a binary tree and a doubly linked list in the same node especially since the binary tree is sorted.

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    58
    Quote Originally Posted by itCbitC View Post
    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..

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    Last edited by iMalc; 11-22-2008 at 01:51 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Sep 2008
    Posts
    58
    Quote Originally Posted by iMalc View Post
    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???

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by scarlet00014 View Post
    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.
    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?
    Last edited by iMalc; 11-22-2008 at 02:17 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Sep 2008
    Posts
    58
    Quote Originally Posted by iMalc View Post
    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


    Oh, this isn't a self-balancing binary tree is it
    i dont think so.. not really sure

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by scarlet00014 View Post
    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;
            }
    Last edited by iMalc; 11-22-2008 at 02:51 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Sep 2008
    Posts
    58
    Quote Originally Posted by iMalc View Post
    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?

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by scarlet00014 View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List or Binary Search Tree
    By rhysmeister in forum C++ Programming
    Replies: 6
    Last Post: 04-29-2004, 03:04 PM
  2. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  3. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  4. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM