Pre Order Search on a general tree

This is a discussion on Pre Order Search on a general tree within the C Programming forums, part of the General Programming Boards category; HI, I am supposed to use a pre order transversal to search for an inputted value. The function returns a ...

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    10

    Angry Pre Order Search on a general tree

    HI, I am supposed to use a pre order transversal to search for an inputted value. The function returns a pointer to the node it is found in. If it is not found it should return NULL (I think). My code works fine if you only travel left. If the number is to the right at all or not in the tree, I get a segmentation fault. I can't figure out why it is doing this. Been working on it all day. Thank you in advance for any help!

    Code:
    /********************************************************************/
    /*            SearchTree
    /********************************************************************/
    /*
     * Input:       The value being searched for, and the pointer to the root (intially) 
     * Output:      A pointer to the node where the value is found
     * Task:        Uses a preorder transveral to search for the inputted value
     */
       NodePtr SearchTree(int value, Tree T)
       {
       
       
          if(T != NULL)
          {
             if(T->value == value) 
                return T;
             return SearchTree(value,T->Left);
             return SearchTree(value,T->Right);
          	
          }
          
          else 
          {
             
             return T; 
          }
       }

  2. #2
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Can you post the definitions for Tree and NodePtr? It's impossible to tell their types from this.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Posts
    10
    Code:
    typedef struct node Node;
    typedef Node* NodePtr;
    typedef Node* Tree;
    struct node
    {
        int value;
        NodePtr Left;
        NodePtr Right;
    };
    Tree is just a pointer to the root of the tree.

  4. #4
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Well your algorithm is wrong. The second return never happens, it's just dead code. When you reach the bottom left side of your tree you return NULL and exit. You never go in the right side.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Posts
    10
    Could you please give me a suggestion on how to fix it, or how the algorithm should be? I am at my wit's end with it. Just a suggestion, I am not asking you to fix the code for me. Thank you.

  6. #6
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Sure. Well I'm assuming this is a Binary search tree, so the information is already ordered in the tree?

    If so, then you have compare the value you are looking for with the current node and decide where to go accordingly. Here is some Pseudo-code for you:

    Code:
    SEARCH(NODE)
    WHILE CURRENT NODE IS NOT NULL
       IF CURRENT NODE HAS VALUE val
          return CURRENT NODE
       ELSE IF CURRENT NODE VALUE < val
          return SEARCH(CURRENT NODE -> LEFT)
       ELSE
          return SEARCH(CURRENT NODE -> RIGHT)
    END WHILE
    Something like that. Then you have to add in the special case when you don't find it. That's when you have reached leaf level and the current node is not value.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  7. #7
    Registered User
    Join Date
    Nov 2010
    Posts
    10
    It is not a binary search tree. That is what has made it so frustrating. To find the value we essentially have to search the whole tree. Any example I find always assumes it is a BST. :-(
    Any other suggestions? Thank you SO much for taking the time to help me!

  8. #8
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Oh OK, no problem. So what you need then is to look through the entire tree, like you were attempting.

    Well, in that case it should be something like this:

    Code:
    SEARCH(NODE, value)
    IF NODE = NULL 
       return NULL
    IF NODE->val = value
      return NODE
    ELSE 
       LEFT = SEARCH(NODE->LEFT, value)
       RIGHT = SEARCH(NODE->RIGHT,value)
    IF LEFT != NULL
       return LEFT
    ELSE 
       return RIGHT
    Not sure if that works, I am still wrapping my head around it... it's 5 AM here
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  9. #9
    Registered User
    Join Date
    Nov 2010
    Posts
    10
    IT WORKS!!!!!! Thank you! You are a lifesaver! Just have to tweak it a bit, still getting a seg fault for a value not in the tree. X-D

  10. #10
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Wow... I am really glad it worked out for you, I just completely pulled that out of my ass, but it looks like the comp sci. college education still pays off years later. Yay!

    I think there is an improvement you can make to it. When you are calculating LEFT and before searching in RIGHT, if LEFT is not NULL you should just return LEFT(the val is already found so there is no need to search all of RIGHT too). If LEFT is NULL then you can just return SEARCH(RIGHT), because val is either there or nowhere at all in which case you will carry over the return NULL you get from the right side

    So basically

    Code:
    LEFT = SEARCH(NODE->LEFT, value)
    IF LEFT != NULL
       RETURN LEFT
    ELSE RETURN SEARCH(NODE->RIGHT,value)
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  11. #11
    Registered User
    Join Date
    Nov 2010
    Posts
    10
    It is not working. It is again only checking the left hand nodes. :-( If not in the left hand nodes it returns the last left hand node. *Sigh* What do you think? Is there an error in the way I translated it?
    Code:
       NodePtr SearchTree(int value, Tree T)
       {
          if(T==NULL)
             return NULL;
          if(T->value ==value)
             return T;
          else 
          {
             T->Left = SearchTree(value,T->Left);
             T->Right = SearchTree(value,T->Right);
          }
          if (T->Left != NULL)
             return T->Left;
          else if (T->Right != NULL)
             return T->Right;
          else   
          	 		
             return T;
       }

  12. #12
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Quote Originally Posted by TiredStudent View Post
    It is not working. It is again only checking the left hand nodes. :-( If not in the left hand nodes it returns the last left hand node. *Sigh* What do you think? Is there an error in the way I translated it?
    Code:
       NodePtr SearchTree(int value, Tree T)
       {
          if(T==NULL)
             return NULL;
          if(T->value ==value)
             return T;
          else 
          {
             T->Left = SearchTree(value,T->Left);
             T->Right = SearchTree(value,T->Right);
          }
          if (T->Left != NULL)
             return T->Left;
          else if (T->Right != NULL)
             return T->Right;
          else   
          	 		
             return T;
       }
    Yes, there is a problem. Left and right should not be T->left and T->right because then you are messing up your tree.

    Code:
       NodePtr SearchTree(int value, Tree T)
       {
          if(T==NULL)
             return NULL;
          if(T->value ==value)
             return T;
          else 
          {
             NodePtr left = SearchTree(value,T->Left);
             if(left != NULL)
                     return left;
             else return SearchTree(value,T->Right);
          }
       }
    try now
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  13. #13
    Registered User
    Join Date
    Nov 2010
    Posts
    10
    Ok. It is definitely working now, as long as the number is present. Still working on the case of it not being there. Yay for progress!

  14. #14
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Good job!

    It should be fine if it's not in the tree as well. Just check for NULL before using the return value in your main function (or wherever you call the search function). If you use that pointer and its NULL you get a segfault which sounds like what you are doing now.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  15. #15
    Registered User
    Join Date
    Nov 2010
    Posts
    10
    It did work fine! My problem was in my driver. I was printing out the "found value" and its children. I had a check for NULL, but it was after those print statements, so it was trying to print something that wasn't there and giving a seg fault! Wish I would have realized that sooner! But glad it is working now! Thanks so much! You have been a HUGE help!

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

Similar Threads

  1. Help with delete - Binary search tree
    By lazyme in forum C Programming
    Replies: 10
    Last Post: 03-21-2010, 01:19 PM
  2. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 03:56 PM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  4. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

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