Need help with BST Program

This is a discussion on Need help with BST Program within the C Programming forums, part of the General Programming Boards category; Hello All, I'm learning about BST from a book and I'm stuck half way while trying to code a BST. ...

  1. #1
    Registered User
    Join Date
    May 2012
    Location
    India
    Posts
    32

    Need help with BST Program

    Hello All, I'm learning about BST from a book and I'm stuck half way while trying to code a BST. Here's my code:

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    typedef struct node
    {
            int *dataPtr;
            struct node *left;
            struct node *right;
    }NODE;
    typedef struct
    {
            int count;
            NODE *root;
    }TREE;
    TREE *createTree(void)
    {
         TREE *tree;
         tree = (TREE *)malloc(sizeof(TREE));
         if(tree)
         {
                 printf("Tree created successfully. . .\n");
                 tree->root = NULL;
                 tree->count = 0;
         }
         return tree;
    }
    void addNode(TREE *tree, int *dataInPtr)
    {
        NODE *newNode;
        newNode = (NODE *)malloc(sizeof(NODE));
        if(newNode)
        {
            newNode->dataPtr = dataInPtr;
            newNode->left = NULL;
            newNode->right = NULL;
        }
        if(tree->count == 0)
            tree->root = newNode;
        else
            insertNode(tree->root, newNode, dataInPtr);
        (tree->count)++;
    }
    NODE *insertNode(NODE *root, NODE *newNode, int *dataInPtr)        
    {
        if(!root)
            return newNode;
        if(dataInPtr < root->dataPtr)    
        {
            root->left = insertNode(root->left, newNode, dataInPtr);
            return root;
        }
        else
        {
            root->right = insertNode(root->right, newNode, dataInPtr);
            return root;
        }
        return root;
    }
    void inOrder(NODE *node)
    {
         if(node != NULL)
         {
                 inOrder(node->left);
                 printf("%d\t", node->dataPtr);
                 inOrder(node->right);
         }
    }
    int main(void)
    {
        TREE *tree;
        tree = createTree();
        addNode(tree->root, 20);
        inOrder(tree->root);
        getch();
        return 0;
    }
    I kinda know where the problem lies. In the "else" loop of the addNode() function, I call insertNode() function which is a function with a void return type. But the insertNode() function actually return a NODE type.

    I really don't know how to set the left and right nodes. I tried several things but failed. I want to do it on my own. Any help / suggestion would be appreciated.

    Thanks in advance.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    > if(dataInPtr < root->dataPtr)
    You need to store (and compare) values, NOT pointers.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,457
    Code:
    typedef struct node
    {
            int *dataPtr;
            struct node *left;
            struct node *right;
    }NODE;
    ...
    void addNode(TREE *tree, int *dataInPtr)
    ...
    addNode(tree->root, 20);
    Why are you passing a value (20) to a function that expects a pointer to int? I think your struct and addNode function are actually incorrect, dataPtr should really just be data, an int:
    Code:
    typedef struct node
    {
            int data;
            struct node *left;
            struct node *right;
    }NODE;
    ...
    void addNode(TREE *tree, int dataIn)
    Then the comparison Salem mentioned should work.

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,799
    Code:
    TREE *createTree(void)
    {
         TREE *tree;
         tree = (TREE *)malloc(sizeof(TREE));
         if(tree)
         {
                 printf("Tree created successfully. . .\n");
                 tree->root = NULL;
                 tree->count = 0;
         }
         return tree;
    }
    ...
    int main(void)
    {
        TREE *tree;
        tree = createTree();
        addNode(tree->root, 20);
        inOrder(tree->root);
        getch();
        return 0;
    }
    Your createTree function can potentially return a NULL pointer, you return "tree" in that function regardless of whether it is NULL or not and then immediately start using it. This can result in problems when you access the returned NULL pointer as you are doing in your calls to addNode and inOrder. You should have a check in main to only proceed if the returned pointer is not NULL.




    Code:
    tree = (TREE *)malloc(sizeof(TREE));
    ...
    newNode = (NODE *)malloc(sizeof(NODE));
    You should avoid casting the return value of your malloc calls where possible. Also, it is preferable from a maintenance standpoint to use the size of the dereferenced variable you are assigning to rather than the size of the type pointed to when passing how many bytes to allocate to malloc. This makes future changes easier since you won't be required to hunt down and fix all those sizeof statements if you change the type of the pointer.

    This is a preferable way to write the above:
    Code:
    tree = malloc(sizeof(*tree));
    ...
    newNode = malloc(sizeof(*newNode));
    Of course if you change the variable name for some reason you'd still have to do some replacement





    Code:
    #include<conio.h>
    ...
    getch();
    Unless you have a very good reason for doing so, it's best to avoid non-standard headers and functions. Though it's behavior is different and perhaps undesirable, a more standard approach to this typical "press any key to continue" behavior is to replace getch with getchar and use the return key to end the program.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  5. #5
    Registered User
    Join Date
    May 2012
    Location
    India
    Posts
    32
    I removed the pointer to integer from all places and replaced with integer variables. I feel, the problem really lies in the way insertNode() is defined and called. In the else part of addNode() function, insertNode() is called as a function with void return type.

    However in reality, insertNode() returns a NODE type. I know this is wrong, but am not able to figure out a way to do this.
    Last edited by Shyam Raj; 11-29-2012 at 12:13 PM.

  6. #6
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    insertNode returns a pointer to a node. Not a node!

    If I were you I would post my updated code
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,457
    Updated code would help.

    I think your insertNode function is okay (if a bit awkward). The problem seems to lie in the else part of your addNode function. You need to assign the return value of insertNode to tree->root. Also, addNode takes a TREE *, not a NODE *, so you should pass in tree, not tree->root.

    Your compiler should be complaining about all these type-mismatch issues. If not, turn up the warning level to the max.

  8. #8
    Registered User
    Join Date
    May 2012
    Location
    India
    Posts
    32
    @anduril462: Rightly said mate, there were a few errors which i corrected. And as you said, the problem is definitely in the else part of addNode function, but I don't know how to assign that function. You say that the return value of insertNode to tree->root. But don't you think this is incorrect? Because we assign the tree->root only if the tree->count is 0, that is the tree is just created.

    Once tree->count is incremented, we already have a node and the next node should either go to the left or the right of the root which is where am confused.

    The updated code is as follows:

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    typedef struct node
    {
            int data;
            struct node *left;
            struct node *right;
    }NODE;
    typedef struct
    {
            int count;
            NODE *root;
    }TREE;
    TREE *createTree(void)
    {
         TREE *tree;
         tree = (TREE *)malloc(sizeof(TREE));
         if(tree)
         {
                 printf("Tree created successfully. . .\n");
                 tree->root = NULL;
                 tree->count = 0;
         }
         return tree;
    }
    void addNode(TREE *tree, int dataIn)
    {
        NODE *newNode;
        newNode = (NODE *)malloc(sizeof(NODE));
        if(newNode)
        {
            newNode->data = dataIn;
            newNode->left = NULL;
            newNode->right = NULL;
        }
        if(tree->count == 0)
            tree->root = newNode;
        else
            insertNode(tree->root, newNode, dataIn);
        (tree->count)++;
    }
    NODE *insertNode(NODE *root, NODE *newNode, int dataIn)        
    {
        if(!root)
            return newNode;
        if(dataIn < root->data)    
        {
            root->left = insertNode(root->left, newNode, dataIn);
            return root;
        }
        else
        {
            root->right = insertNode(root->right, newNode, dataIn);
            return root;
        }
        return root;
    }
    void inOrder(NODE *node)
    {
         if(node != NULL)
         {
                 inOrder(node->left);
                 printf("%d\t", node->data);
                 inOrder(node->right);
         }
    }
    int main(void)
    {
        TREE *tree;
        tree = createTree();
        addNode(tree, 20);
        inOrder(tree->root);
        getch();
        return 0;
    }

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    Look at line 40
    insertNode(tree->root, newNode, dataIn);

    Look at line 43
    NODE *insertNode(NODE *root, NODE *newNode, int dataIn)

    Now back to line 40
    insertNode(tree->root, newNode, dataIn);

    What happens to the red bit?
    You're returning a result, but ignoring it.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #10
    Registered User
    Join Date
    May 2012
    Location
    India
    Posts
    32
    Hi Salem, I changed the code a bit, I guess it works fine but it doesn't print the output:

    The changed code is like this:

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    typedef struct node
    {
            int data;
            struct node *left;
            struct node *right;
    }NODE;
    typedef struct
    {
            int count;
            NODE *root;
    }TREE;
    TREE *createTree(void)
    {
         TREE *tree;
         tree = (TREE *)malloc(sizeof(TREE));
         if(tree)
         {
                 printf("Tree created successfully. . .\n");
                 tree->root = NULL;
                             tree->count = 0;
         }
         return tree;
    }
    NODE *addNode(NODE *node, int dataIn)
    {
        if(node == NULL)
        {
                NODE *newNode;
                newNode = (NODE *)malloc(sizeof(NODE));
                if(newNode)
                {
                           newNode->data = dataIn;
                           newNode->left = NULL;
                           newNode->right = NULL;
                           node = newNode;
                }
        }
        else
        {
            if(dataIn < node->data)
            {
                 node->left = addNode(node->left, dataIn);
                 return node;
            }
            else if(dataIn > node->data)
            {
                 node->right = addNode(node->right, dataIn);
                 return node;
            }
        }
        return node;
    }
    
    void inOrder(NODE *node)
    {
         if(node != NULL)
         {
                 inOrder(node->left);
                 printf("%d\t", node->data);
                 inOrder(node->right);
         }
    }
    int main(void)
    {
        TREE *tree;
        tree = createTree();
        addNode(tree->root, 20);
        inOrder(tree->root);
        getch();
        return 0;
    }
    In the inOrder function, the "if" condition doesn't get satisfied, so that means the node is not getting created? Is it?


    But I did a bit of debug and I found that the newNode does get created.

  11. #11
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    So back to line 70, where is THAT result being stored?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  12. #12
    Registered User
    Join Date
    May 2012
    Location
    India
    Posts
    32
    Hi Salem, I understand what you're saying. The addNode()function returns a NODE type and am not storing it. But I am not sure what do I assign it to.

    If I do it this way
    Code:
    tree->root = addNode(tree->root, 20);
    It would only be applicable for the first node - root, isn't it? Or am I wrong?

    Or should I assign it in some other way?

  13. #13
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    Did you try the modification?
    Did it work?

    > It would only be applicable for the first node - root, isn't it? Or am I wrong?
    Yes, it only applies to the first assignment.

    But then again,
    node->left = addNode(node->left, dataIn);
    will only ever assign a different value the FIRST time each node gets added into the tree.
    Thereafter, it will always end up assigning the same value.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  14. #14
    Registered User
    Join Date
    May 2012
    Location
    India
    Posts
    32
    I could only understand a bit of your previous comment. If you can give me some hint, I'll try it out myself.

    I've been stuck up with this for the past 5 days.

  15. #15
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    Try this as your main
    Code:
    int main(void)
    {
        TREE *tree;
        tree = createTree();
        int i;
        for ( i = 0 ; i < 10 ; i++ ) {
          printf("Root was %p;", (void*)tree->root);
          tree->root = addNode(tree->root, rand() % 100);
          printf("Root is %p\n", (void*)tree->root);
        }
        inOrder(tree->root);
    //    getch();
        return 0;
    }
    I get
    Code:
    $ ./a.out 
    Tree created successfully. . .
    Root was (nil);Root is 0x1809030
    Root was 0x1809030;Root is 0x1809030
    Root was 0x1809030;Root is 0x1809030
    Root was 0x1809030;Root is 0x1809030
    Root was 0x1809030;Root is 0x1809030
    Root was 0x1809030;Root is 0x1809030
    Root was 0x1809030;Root is 0x1809030
    Root was 0x1809030;Root is 0x1809030
    Root was 0x1809030;Root is 0x1809030
    Root was 0x1809030;Root is 0x1809030
    15	21	35	49	77	83	86	92	93	$
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help converting array program to link list program
    By hsmith1976 in forum C++ Programming
    Replies: 0
    Last Post: 02-14-2010, 08:50 PM
  2. Replies: 1
    Last Post: 03-03-2009, 03:47 PM
  3. Replies: 5
    Last Post: 08-16-2007, 11:43 PM
  4. Replies: 18
    Last Post: 11-13-2006, 12:11 PM
  5. How To Make The Program Installed In Program Files Folder?
    By javacvb in forum Windows Programming
    Replies: 4
    Last Post: 11-05-2003, 04:33 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21