Like Tree3Likes
  • 1 Post By rags_to_riches
  • 1 Post By quzah
  • 1 Post By rags_to_riches

Can't firgure out why im getting a segmentation fualt

This is a discussion on Can't firgure out why im getting a segmentation fualt within the C Programming forums, part of the General Programming Boards category; I am getting a Segmentation Fault when im trying to pass the tree and its root so that the tree ...

  1. #1
    Registered User
    Join Date
    Jan 2011
    Posts
    20

    Can't firgure out why im getting a segmentation fualt

    I am getting a Segmentation Fault when im trying to pass the tree and its root so that the tree can be traversed. The code for an In-Order traversal was given to me and it works. Here is what how i print the tree with an In-Order Traversal:
    I call
    Code:
    RBTreePrint(tree);
    from my main program. In a separate file i have the functions:
    Code:
    /***********************************************************************/
    /*  FUNCTION:  RBTreePrint */
    /**/
    /*    INPUTS:  tree is the tree to print */
    /**/
    /*    OUTPUT:  none */
    /**/
    /*    EFFECT:  This function recursively prints the nodes of the tree */
    /*             inorder using the PrintKey and PrintInfo functions. */
    /**/
    /*    Modifies Input: none */
    /**/
    /***********************************************************************/
    
    void RBTreePrint(rb_red_blk_tree* tree) {
      InorderTreePrint(tree,tree->root->left);
    }
    
    /***********************************************************************/
    /*  FUNCTION:  InorderTreePrint */
    /**/
    /*    INPUTS:  tree is the tree to print and x is the current inorder node */
    /**/
    /*    OUTPUT:  none  */
    /**/
    /*    EFFECTS:  This function recursively prints the nodes of the tree */
    /*              inorder using the PrintKey and PrintInfo functions. */
    /**/
    /*    Modifies Input: none */
    /**/
    /*    Note:    This function should only be called from RBTreePrint */
    /***********************************************************************/
    
    void InorderTreePrint(rb_red_blk_tree* tree, rb_red_blk_node* x) {
      rb_red_blk_node* nil=tree->nil;
      rb_red_blk_node* root=tree->root;
      if (x != tree->nil) {
        InorderTreePrint(tree,x->left);
        printf("info=");
        tree->PrintInfo(x->info);
        printf("  key="); 
        tree->PrintKey(x->key);
        printf("  l->key=");
        if( x->left == nil) printf("NULL"); else tree->PrintKey(x->left->key);
        printf("  r->key=");
        if( x->right == nil) printf("NULL"); else tree->PrintKey(x->right->key);
        printf("  p->key=");
        if( x->parent == root) printf("NULL"); else tree->PrintKey(x->parent->key);
        printf("  red=%i\n",x->red);
        InorderTreePrint(tree,x->right);
      }
    }
    With that working, I tried to write a Pre-Order traversal function. My function call is:
    Code:
    preOrder(tree, root);
    And this is where i get the Segmentation Fualt.
    Here is the preOrder function
    Code:
    void preOrder(rb_red_blk_tree* tree, rb_red_blk_node* x)
    {
    	if(x != tree->nil)
    	{
    		printNode(tree, x);
    		preOrder(tree, x->left);
    		preOrder(tree, x->right);
    	}
    }
    Here are the structs for the tree and nodes of the tree.
    Code:
    typedef struct rb_red_blk_node {
      void* key;
      void* info;
      int red; /* if red=0 then the node is black */
      struct rb_red_blk_node* left;
      struct rb_red_blk_node* right;
      struct rb_red_blk_node* parent;
    } rb_red_blk_node;
    
    
    /* Compare(a,b) should return 1 if *a > *b, -1 if *a < *b, and 0 otherwise */
    /* Destroy(a) takes a pointer to whatever key might be and frees it accordingly */
    typedef struct rb_red_blk_tree {
      int (*Compare)(const void* a, const void* b); 
      void (*DestroyKey)(void* a);
      void (*DestroyInfo)(void* a);
      void (*PrintKey)(const void* a);
      void (*PrintInfo)(void* a);
      /*  A sentinel is used for root and for nil.  These sentinels are */
      /*  created when RBTreeCreate is caled.  root->left should always */
      /*  point to the node which is the root of the tree.  nil points to a */
      /*  node which should always be black but has aribtrary children and */
      /*  parent and no key or info.  The point of using these sentinels is so */
      /*  that the root and nil nodes do not require special cases in the code */
      rb_red_blk_node* root;             
      rb_red_blk_node* nil;              
    } rb_red_blk_tree;
    Any help would be appreciated.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You should probably build your tree correctly, as you are either not building a tree or walking off the end of your tree.

  3. #3
    Registered User
    Join Date
    Jan 2011
    Posts
    20
    I'm using the same tree that was printed with the supplied code.

    I also narrowed down where the issue is using print statements. I go to my function to print the nodes
    Code:
    void printNode(rb_red_blk_tree* tree, rb_red_blk_node* node)
    {
    	//rb_red_blk_node* nil=tree->nil;
    	//rb_red_blk_node* root=tree->root;
    	printf("info=");
    	tree->PrintInfo(node->info);
    	fflush(stdout);
    	printf("  key=");
    	tree->PrintKey(node->key);
    	fflush(stdout);
    	printf("  l->key=");
    	if( node->left == NULL) printf("NULL"); else tree->PrintKey(node->left->key);
    	fflush(stdout);
    	printf("  r->key=");
    	if( node->right == NULL) printf("NULL"); else tree->PrintKey(node->right->key);
    	fflush(stdout);
    	printf("  p->key=");
    	if( node->parent == tree->root) printf("NULL"); else tree->PrintKey(node->parent->key);
    	fflush(stdout);
    	printf("  red=%i\n",node->red);
    }
    and the PrintKey function is a pointer in the tree struct and it points to
    Code:
    void IntPrint(const void* a) {
    	printf("%i",*(int*) a);
    }
    The print statement is where I get the segmentation fualt.

  4. #4
    a_capitalist_story
    Join Date
    Dec 2007
    Posts
    2,657
    Now is a really good time to learn how to use your debugger, because if you compile this in debug mode and run it in the debugger, it will stop where the segfault is occurring and you can check out the situation.
    quzah likes this.

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Now is also a good time to stop assuming that your pointers are valid, and to test them for validity before you start dereferencing them:
    Quote Originally Posted by dford425 View Post
    and the PrintKey function is a pointer in the tree struct and it points to
    Code:
    void IntPrint(const void* a) {
    	printf("%i",*(int*) a);
    }
    The print statement is where I get the segmentation fualt.


    Quzah.
    rags_to_riches likes this.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Jan 2011
    Posts
    20
    I figured it out, I mis-understood how the provided code for the tree works. It seems that the "root" node is not actually the root and I have to pass the tree->root->left node. I assumed this was how the author wrote the In Order traversal because that is the first step, traverse the left child node. Using the debugger help me figure it out.

    Thanks for all your help.

  7. #7
    a_capitalist_story
    Join Date
    Dec 2007
    Posts
    2,657
    Using the debugger help me figure it out.
    Excellent. You're well on your way to becoming a software engineer! I can't recommend using the debugger enough. You will learn all sorts of new things by stepping through code in the debugger.
    Salem likes this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Segmentation fault
    By Kemaratu in forum C Programming
    Replies: 6
    Last Post: 11-30-2009, 03:40 AM
  2. Segmentation error
    By Kitty Litter in forum C Programming
    Replies: 5
    Last Post: 11-07-2006, 09:35 PM
  3. segmentation fault
    By bazzano in forum C Programming
    Replies: 3
    Last Post: 04-26-2006, 09:02 PM
  4. segmentation fault
    By bazzano in forum C Programming
    Replies: 9
    Last Post: 04-10-2006, 11:25 AM
  5. Segmentation Fault??
    By SteveP4444 in forum C Programming
    Replies: 5
    Last Post: 04-01-2006, 02:24 AM

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