Need Help with Binary Tree Functions

This is a discussion on Need Help with Binary Tree Functions within the C Programming forums, part of the General Programming Boards category; Hello: I am trying to finish an assignment in my class, and I have the code all typed out with ...

  1. #1
    Registered User
    Join Date
    Aug 2007
    Posts
    5

    Need Help with Binary Tree Functions

    Hello:

    I am trying to finish an assignment in my class, and I have the code all typed out with no errors that keep it from compiling, but when I run it, the functions do not seem to add values to the tree. I just want some pointers (no pun intended) on what problems I am having, so I can correct the code. Any help would be greatly appreciated!!

    binaryTree.h:

    Code:
    struct Node
    {
            int val;
            struct Node *left;
            struct Node *right;
    };
    
    int SearchTree(struct Node *start, int query);
    struct AddNode(struct Node *newnode, int value);
    int PrintTree(struct Node *begin);
    main.c:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include "binaryTree.h"
    
    int main()
    {
            char decision;
            int newnum;
            int findnum;
            int firstnum;
            int i;
            struct Node *root;
            root=malloc(sizeof(struct Node));
            for(i=0; i>=0; i++)
            {
                    if(i==0)
                    {
                            printf("Enter the number for the beginning of the tree:");
                            scanf("&#37;d", &firstnum);
                            printf("\n");
                            root->val = firstnum;
                            root->left = NULL;
                            root->right = NULL;
                    }
                    printf("===========================\n");
                    printf("a to add a value\n");
                    printf("s to search for a value\n");
                    printf("l to list all stored values\n");
                    printf("e to exit program\n");
                    printf("Enter your choice:");
                    scanf("%c", &decision);
                    if(decision == 'e' || decision == 'E')
                            return 0;
                    while(decision != 'a' && decision != 's' && decision != 'l' && decision != 'A' && decision != 'S' && decision != 'L')
                    {
                            printf("\nThat is not a valid choice.\n");
                            printf("===========================\n");
                            printf("a to add a value\n");
                            printf("s to search for a value\n");
                            printf("l to list all stored values\n");
                            printf("Enter your choice:");
                            scanf("%c", &decision);
                            printf("\n");
                            if(decision == 'e' || decision == 'E')
                                    return 0;
                    }
                    if(decision == 'a' || decision == 'A')
                    {
                            printf("\nEnter the value to add:");
                            scanf("%d", &newnum);
                            printf("\n");
                            AddNode(root, newnum);
                    }
                    if(decision == 's' || decision == 'S')
                    {
                            printf("\nEnter the value to search for:");
                            scanf("%d", &findnum);
                            printf("\n");
                            SearchTree(root, findnum);
                    }
                    if(decision == 'l' || decision == 'L')
                            PrintTree(root);
            }
            return 0;
    }
    binaryTree.c:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include "binaryTree.h"
    
    int SearchTree(struct Node *start, int query)
    {
            if (start == NULL)
            {
                    printf("%d was not found.", query);
                    return(-1);
            }
            else
            {
                    if (query == start->val)
                    {
                            printf("%d was found.", query);
                            return(0);
                    }
                    else
                    {
                            if (query < start->val)
                                    return SearchTree(start->left, query);
                            else
                                    return SearchTree(start->right, query);
                    }
            }
    }
    
    struct AddNode(struct Node *newnode, int value)
    {
            if (newnode == NULL)
            {
                    struct Node *newnode = malloc(sizeof(struct Node));
                    newnode->val = value;
                    newnode->left = NULL;
                    newnode->right = NULL;
                    return(newnode);
            }
            else
            {
                    if (value < newnode->val)
                            newnode->left = AddNode(newnode->left, value);
                    else
                            newnode->right = AddNode(newnode->right, value);
                    return (newnode);
            }
    }
    
    int PrintTree(struct Node *begin)
    {
            if (begin == NULL)
                    return 0;
            PrintTree(begin->left);
            printf("%d \n", begin->val);
            PrintTree(begin->right);
            return 0;
    }
    Last edited by Highwind7; 08-02-2007 at 08:49 AM. Reason: Making corrections

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,548
    > scanf("&#37;c", &decision);
    All other scanf formats skip white space and newlines, %c doesn't.
    If you print the decimal value (%d) of decision, you'll find it likely to be a space or a newline.

    Use fgets() to read a whole line, then sscanf to extract what you need without any fear of leaving the input in an undefined state.
    http://faq.cprogramming.com/cgi-bin/...&id=1043284385

    Oh, and in case someone decides to tell you to use fflush(stdin), then read this first
    http://faq.cprogramming.com/cgi-bin/...&id=1043284351
    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
    Aug 2007
    Posts
    5
    Okay, thanks for the input. Now I just need to figure out why the tree isn't storing any values. Again, any advice would be greatly appreciated!

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
     int AddNode(struct Node *node, int value)
    {
            if (node == NULL)
            {
                   struct Node *node = malloc(sizeof(struct Node));
                    node->val = value;
                    node->left = NULL;
                    node->right = NULL;
                    return 0;
    ...
    It is DEFINITELY bad style to use the same variable name for a local variable and a parameter into the function. Surely you can come up with a better name for the variable. I'm not entirely sure this code works right, and the "node" inside the if-statement is never used again, so you've just allocated some memory that is never assigned to something "permanent" - when you leave the if-statement, "node" is lost, and the memory is left "floating" without anything referencing it.

    Code:
                    if (value < node->val)
                            node->left = (void *)AddNode(node->left, value);
                    else
                            node->right = (void *)AddNode(node->right, value);
                    return 0;
    This piece is also quite broken - first of all, AddNode returns an integer, not a pointer (hence the compiler telling you off and you having to cast it - but it's wrong anyways, becuase it ALWAYS returns zero .

    Assuming you returned something sensible (of the type Node * perhaps), I'm not entirely sure that it would actually do the right thing - but I'm sure the code as it stands NOW isn't working, because you are setting the pointer to null.

    --
    Mats

  5. #5
    Registered User
    Join Date
    Aug 2007
    Posts
    5
    Thanks for the input! The corrections have been made in the original post. I haven't tried to compile it yet, but I still think that something is wrong. Please let me know if there are any other errors in this! Thanks!

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Ok, so you are now returning newnode, but you are still creating a local variable with the same name as the input parameter to the function - which is at the very least bad style, even if it's not technically wrong. You could easily use the incoming parameter to assign the new malloc value.

    And I agree, there's probably bugs there still. One point is that you are updating the right or left node when passing down through the tree. That's probably not a good idea.

    You are also missing what kind of struct you are returning from the function, so the code won't compile - before you post code, try to compile it first (and fix any errors unless you are specifically asking about what the fix for a particular error is - of course).

    --
    Mats

  7. #7
    Registered User
    Join Date
    Aug 2007
    Posts
    5
    Okay, I managed to get the code to work, thanks for all of your help!

    I will be posting a new message about an assignment that I have had a lot more trouble with, so please check it out and post any advice that you have.

    Thanks again!!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. best STL method to implement a binary tree
    By MatthewDoucette in forum C++ Programming
    Replies: 8
    Last Post: 06-16-2006, 07:08 AM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  4. Traversing a binary tree with pointers
    By supaben34 in forum C++ Programming
    Replies: 8
    Last Post: 12-07-2003, 12:04 PM
  5. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 01:24 AM

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