Thread: Filtering inorder bst print traversal

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    51

    Filtering inorder bst print traversal

    Hi,
    Does anyone have an idea of how to filter an inorder print traversal for a bst?
    Let's say u have 2 + nodes carrying the same data, and u only wanna print one of it out.

    this is my problem.

    my print output seem to be like (eg) - [number is the frequency]

    A 4
    A 4
    A 4
    AA 2
    AA 2
    GAA 2

    and i want it to be

    A 4
    AA 2
    GAA 2

    .... I thought of something like,
    Code:
    void print_inorder(node_t *p_ptr, char *s){
         node_t *x, *y;
         
         x = p_ptr->left;     
         y = p_ptr->right;
         
    	 if(p_ptr!=NULL){
            if(substring(s, p_ptr->start, p_ptr->end) == substring(s, x->start, x->end))
                         p_ptr=x;
            if(substring(s, p_ptr->start, p_ptr->end) == substring(s, y->start, y->end))
                         p_ptr=y;
    		print_inorder(p_ptr->left,s);
    		printf("%s %d\n", substring(s, p_ptr->start, p_ptr->end), p_ptr->freq);
    		print_inorder(p_ptr->right,s);
    	}
    }
    to skip over the node carrying the reoccuring data. But it ended up in a 'SEG FAULT', and seems crappy to me too...

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Why do you have multiple nodes containing the same information?
    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.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    51
    oh yea, silly me

    ok..i changed it to..
    Code:
    void print_inorder(node_t *p_ptr, char *s){
         
    	 if(p_ptr!=NULL){
             if(substring(s, p_ptr->start, p_ptr->end) == substring(s, p_ptr->left->start, p_ptr->left->end))
                         p_ptr = p_ptr->left;
            if(substring(s, p_ptr->start, p_ptr->end) == substring(s, p_ptr->right->start, p_ptr->right->end))
                         p_ptr = p_ptr->right;
    		print_inorder(p_ptr->left,s);
    		printf("%s %d\n", substring(s, p_ptr->start, p_ptr->end), p_ptr->freq);
    		print_inorder(p_ptr->right,s);
    	}
    }
    but it still ends up in a seg fault..

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Write a main() which just adds 3 nodes to your tree (one root, one left, one right) and then run it in the debugger.

    If you can't figure it out from that, at least you will have a self-contained and complete program to post on the forum.

    We can't tell what is possibly going wrong from one random snippet which may not even be the problem.
    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.

  5. #5
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    >Why do you have multiple nodes containing the same information

    We can have two or more nodes containing the same data in bst right?
    This is what a famous book has to say about this issue

    " Let x be a node in a binary search tree. If y is a node in the left subtree of x, then key[y]
    ≤ key[x]. If y is a node in the right subtree of x, then key[x] ≤ key[y]. "

    Though this only leads to some weird situations, it is theoritically possible .
    In the middle of difficulty, lies opportunity

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >We can have two or more nodes containing the same data in bst right?
    That's pointless, really. However, when you consider keys and values then it makes more sense. Different values can have the same keys and nodes are manipulated according to the key. In that case a tree can be designed to allow duplicates.
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    51
    Hey guys!
    I fixed the problem in another way already, thx to the suggestion about creating my own main func to test the print func.
    Then it hit me...
    I was so stupid!

    I altered the tree not to store the reoccuring strings!! Y ?? y?? am i so dumb!
    THX

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Iterative postorder traversal for BST
    By mcha in forum C Programming
    Replies: 6
    Last Post: 02-05-2008, 01:25 AM
  2. Personal Program that is making me go wtf?
    By Submeg in forum C Programming
    Replies: 20
    Last Post: 06-27-2006, 12:13 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. What kind of programs should I start writing?
    By Macabre in forum C++ Programming
    Replies: 23
    Last Post: 04-12-2003, 08:13 PM
  5. InOrder traversal : show tree
    By sballew in forum C Programming
    Replies: 4
    Last Post: 12-17-2001, 10:38 PM