request for your comments on a Tree Search function

This is a discussion on request for your comments on a Tree Search function within the C Programming forums, part of the General Programming Boards category; hello there! i'd kindly like to ask your comments about this function. The assignment is to write a function which ...

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    100

    request for your comments on a Tree Search function

    hello there!
    i'd kindly like to ask your comments about this function.
    The assignment is to write a function which searches for a given key in a binary tree and returns 1 if the key is found, 0 if not. The function should stop searching if the key is met.

    I wrote this:

    Code:
    int searchTree (NodePtr headPtr,int key)
    {
    	if (headPtr==NULL)
    	{
    		return 0;
    	}
    	else
    	{
    		if (headPtr->value==key)
    		{
    			return 1;
    		}
    		else
    			if (search (headPtr->leftPtr,key))
    			{
    				return 1;
    			}
    			else
    			{	
    				if (search (headPtr->rightPtr,key))
    				{
    					return 1;
    				}
    				else
    				{
    					return 0;
    				}
    			}
    	}
    }
    I used the several IF to have clearer what happens (i still have some problems with recursion).. According to you, is this function formally a good solution to the given problem?
    many thanks (once again! )

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    I'm guessing about how search works, but won't this work?
    Code:
    int searchTree (NodePtr headPtr,int key)
    {
      if (headPtr==NULL)
      {
        return 0;
      }
      else
      {
        return search (headPtr, key);
      }
    }
    Or, assuming search takes into account the first argument being null:
    Code:
    int searchTree (NodePtr headPtr,int key)
    {
      return search (headPtr, key);
    }
    In which case, why even have searchTree?
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    100
    Quote Originally Posted by Prelude View Post
    I'm guessing about how search works, but won't this work?
    Code:
    int searchTree (NodePtr headPtr,int key)
    {
      if (headPtr==NULL)
      {
        return 0;
      }
      else
      {
        return search (headPtr, key);
      }
    }
    Or, assuming search takes into account the first argument being null:
    Code:
    int searchTree (NodePtr headPtr,int key)
    {
      return search (headPtr, key);
    }
    In which case, why even have searchTree?
    sorry.. i meant it recursive.. It shall be a set of recursive calls to searchTree, there is no search function..

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    I usually default to something like this:
    Code:
    int search ( node *root, int key )
    {
      if ( root != NULL ) {
        if ( key == root->data )
          return 1;
        else if ( key < root->data )
          return search ( root->left, key );
        else /* key > root->data */
          return search ( root->right, key );
      }
    
      return 0;
    }
    My best code is written with the delete key.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Well that's certainly tidy indentation, but you don't need to indent the code like that in this case. It is probably better to structure it like this:
    Code:
    int searchTree(NodePtr headPtr, int key)
    {
    	if (headPtr == NULL)
    	{
    		return 0;
    	}
    	else if (headPtr->value == key)
    	{
    		return 1;
    	}
    	else if (searchTree(headPtr->leftPtr, key))
    	{
    		return 1;
    	}
    	else if (searchTree(headPtr->rightPtr, key))
    	{
    		return 1;
    	}
    	else
    	{
    		return 0;
    	}
    }
    The last part could be outside an else instead too.

    The next question then is: Is this an 'ordered' binary search tree?
    If so, there's no need to search more than one branch in any case. You simply check which branch the item would be in and only search that one.
    Prelude shows a good way to do that.

    I would actually write it non-recursively myself, assuming that it is also perfectly okay for your asignment.
    Last edited by iMalc; 03-28-2008 at 02:32 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Oct 2007
    Posts
    100
    Quote Originally Posted by iMalc View Post
    The next question then is: Is this an 'ordered' binary search tree?
    If so, there's no need to search more than one branch in any case. You simply check which branch the item would be in and only search that one.
    Prelude shows a good way to do that.

    I would actually write it non-recursively myself, assuming that it is also perfectly okay for your asignment.
    The tree is not specified to be a search tree otherwise of course it could be done according to Prelude's code..
    how would you write it iteratively? Isn't it more complicated for trees?

  7. #7
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Not really.
    Code:
    int search(node *root, int key) {
        while(root) {
            if(key == root->data) return 1;
    
            if(key < root->data) root = root->left;
            else root = root->right;
        }
    
        return 0;
    }
    Searching is quite simple, because you only follow one path. If you wanted to access every node of the tree iteratively, it would be more complicated.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Quote Originally Posted by smoking81 View Post
    The tree is not specified to be a search tree otherwise of course it could be done according to Prelude's code..
    how would you write it iteratively? Isn't it more complicated for trees?
    I don't know why you're saying "search tree". Trees are for looking up items, not just for looking pretty . I was asking if it was "ordered".
    In other words, does it maintain the property that no leftPtr values are ever greater than their parent node, and no rightPtr values are ever less than their parent node?

    If not, why not, and what is the point of the tree then?

    If yes, then dwks has just shown how we do it iteratively. It's no harder at all.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,699
    >> Well that's certainly tidy indentation, but you don't need to indent the code like that in this case. It is probably better to structure it like this:

    what does style have to do with it anyway? Prelude's example was correct. your version does the exact same thing. just not as eloquently.
    Code:
    bool fun(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() > 0;
    }

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Quote Originally Posted by Sebastiani View Post
    >> Well that's certainly tidy indentation, but you don't need to indent the code like that in this case. It is probably better to structure it like this:

    what does style have to do with it anyway? Prelude's example was correct. your version does the exact same thing. just not as eloquently.
    Sorry, I would have thought it was obvious that I was responding to the original post.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User
    Join Date
    Oct 2007
    Posts
    100
    Quote Originally Posted by iMalc View Post
    I don't know why you're saying "search tree". Trees are for looking up items, not just for looking pretty . I was asking if it was "ordered".
    In other words, does it maintain the property that no leftPtr values are ever greater than their parent node, and no rightPtr values are ever less than their parent node?

    If not, why not, and what is the point of the tree then?

    If yes, then dwks has just shown how we do it iteratively. It's no harder at all.
    i thought the name of trees with the properties you specified are called "binary search trees"..
    anyway, in the text of the exercise they don't specify this property so i think it should be thought as a randomly initialized tree..

  12. #12
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,699
    >> Sorry, I would have thought it was obvious that I was responding to the original post.

    ah, right.
    Code:
    bool fun(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() > 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. In over my head
    By Shelnutt2 in forum C Programming
    Replies: 1
    Last Post: 07-08-2008, 06:54 PM
  2. Binary Search Tree - one last question
    By tms43 in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2006, 02:58 AM
  3. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

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