Binary Tree Question

This is a discussion on Binary Tree Question within the C Programming forums, part of the General Programming Boards category; I am getting a segmentation fault when I run this code and I know why, root is NULL in main ...

  1. #1
    tar
    tar is offline
    Registered User
    Join Date
    Sep 2002
    Posts
    12

    Binary Tree Question

    I am getting a segmentation fault when I run this code and I know why, root is NULL in main but I don't know why it is null. Any suggestions? Thanks

    Code:
    //proc.c
    #include <stdio.h>
    #include "tree.h"
    
    int main(int argc, char** argv)
    {
        struct node *root;
        int i;
    
        root = NULL;
    
        for(i = 0;i < 1;i++)
        {
            tree_insert(root, i);
        }
    
        tree_print(root);
    
        tree_destroy(root);
    
        return 0;
    }
    
    //tree.h
    #include <stdio.h>
    
    struct node
    {
        int value;
        struct node *left, *right;
    };
    
    void tree_insert(struct node *root, int value);
    void tree_destroy(struct node *root);
    void tree_print(struct node *root);
    
    //tree.c
    #include "tree.h"
    
    void tree_insert(struct node *root, int value)
    {
        struct node temp;
        if(!root)
        {
            root = (struct node *)malloc(sizeof(struct node));
            if(root == NULL)
            {
                printf("Could not allocate memory!\n");
                return;
            }
            root->right = NULL;
            root->left = NULL;
            root->value = value;
            printf("Inserted value: %d\n", value);
            return;
        }
        if(value < root->value)
        {
            tree_insert(root->left, value);
        }
        else if(value > root->value)
        {
            tree_insert(root->right, value);
        }
    }
    
    void tree_destroy(struct node *root)
    {
        if(root != NULL)
        {
            tree_destroy(root->left);
            tree_destroy(root->right);
            free(root);
        }
        return;
    }
    
    void tree_print(struct node *root)
    {
        if(root->left)
        {
            printf("Node value: %d\n", root->value);
            tree_print(root->left);
        }
        if(root->right)
        {
            tree_print(root->right);
        }
    
    }

  2. #2
    tar
    tar is offline
    Registered User
    Join Date
    Sep 2002
    Posts
    12
    I should add that it seg faults when I try to print the tree and this is due to root being NULL after the inserts, which it should not be. What am I doing wrong that is causing root to be NULL after the inserts?

  3. #3
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511
    Have you check a C data structures book or a tutorial online about binary trees. Just a quick glance it looks good what you have. Check your code or the book you got this from.

    Mr. C.

  4. #4
    tar
    tar is offline
    Registered User
    Join Date
    Sep 2002
    Posts
    12
    Yes it does do something, it inserts 1 node.

  5. #5
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    You never return back the address of root in the insert to main.either return it or pass as pointer to pointer.
    sorry was blitzed earlier. should have spotted that.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  6. #6
    tar
    tar is offline
    Registered User
    Join Date
    Sep 2002
    Posts
    12
    Okay I will try that, thanks.

  7. #7
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    532
    Code:
    //proc.c
    #include  <stdio.h>
    
    struct node
    {
       int value;
       struct node *left, *right;
    };
    
    void tree_insert(struct node *root, int value);
    void tree_destroy(struct node *root);
    void tree_print(struct node *root);
    
    void tree_insert(struct node *root, int value)
    {
       struct node * temp;
    
       if(value  < root->value)
       {
        if(root -> left==NULL) {
                temp = (struct node *)malloc(sizeof(struct node));
                if(temp == NULL)
                {
                    printf("Could not allocate memory!\n");
                    return;
                }
                temp->right = NULL;
                temp->left = NULL;
                temp->value = value;
                printf("Inserted value: %d\n", value);
             root -> left = temp;
                return;
             }
    else 
           tree_insert(root->left, value);
       }
       else if(value  > root->value)
       {
        if(root -> right==NULL) {
                temp = (struct node *)malloc(sizeof(struct node));
                if(temp == NULL)
                {
                    printf("Could not allocate memory!\n");
                    return;
                }
                temp->right = NULL;
                temp->left = NULL;
                temp->value = value;
                printf("Inserted value: %d\n", value);
             root -> right = temp;
                return;
             }
    else 
           tree_insert(root->right, value);
       }
    }
    
    void tree_destroy(struct node *root)
    {
       if(root != NULL)
       {
           tree_destroy(root->left);
           tree_destroy(root->right);
           free(root);
       }
       return;
    }
    
    void tree_print(struct node *root)
    {
       if(root->left)
       {
           printf("Node value: %d\n", root->value);
           tree_print(root->left);
       }
       if(root->right)
       {
           tree_print(root->right);
       }
    
    }
    
    int main(int argc, char** argv)
    {
       struct node *root;
       int i;
    
       root = NULL;
    
           root = (struct node *)malloc(sizeof(struct node));
           if(root == NULL)
           {
               printf("Could not allocate memory!\n");
               return;
           }
           root->right = NULL;
           root->left = NULL;
           root->value = 0;
    
    /* if don't allocate memory, you root header is with NULL */
    /* And you are sending NULL, not address of NULL*/
    /* if you want to send header you can send address of header or make the root extern */
    
       for(i = 1;i  < 19;i++)
       {
           tree_insert(root, i);
       }
    
       tree_print(root);
    
       tree_destroy(root);
    
       return 0;
    }
    [ Never code before desk work ]
    -------------------------------------:-->
    A man who fears Nothing is the man who Loves Nothing
    If you Love Nothing, what joy is there in your life.
    =------------------------------------------------------= - I may be wrong.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  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. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  4. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 01:24 AM
  5. inserting characters into a binary tree
    By sballew in forum C Programming
    Replies: 4
    Last Post: 12-06-2001, 03:08 PM

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