C++ Binary Tree Maximum Value function


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 5 of 5

Thread: C++ Binary Tree Maximum Value function

  1. #1
    Join Date
    Dec 2005
    Posts
    2

    C++ Binary Tree Maximum Value function

    Hello -

    I cannot figure out why this binary tree max function will not work correctly, when i try to run this function the program crashes Note: This is to be done without having the binary tree ordered in anyway



    Code:
    template <typename T>	
    tnode<T> *max(tnode<T> *t)
    {
    	
    	// we will return maxValPtr
    	tnode<T> *maxValPtr,*leftMax, *rightMax;
    
    	
    	if (t == NULL)
    		maxValPtr=NULL;
    		
    	else
    	{
    		// temporarily assume t is pointing to the maximum
    		maxValPtr=t;
    		// leftMax points to the maximum value on the left subtree
    		leftMax=max(t->left);
    
    		// if leftMax is not NULL and the value to which it points
    		// is larger, change maxValPtr
    		if(leftMax!=NULL&&leftMax->nodeValue>maxValPtr->nodeValue)
    		{
    			maxValPtr=leftMax;
    		}
    
    		// rightMax points to the maximum value on the right subtree
    		rightMax=max(t->right);
    		// if rightMax is not NULL and the value to which it points
    		// is larger, change maxValPtr
    		if(rightMax!=NULL&&rightMax->nodeValue>maxValPtr->nodeValue)
    		{
    			maxValPtr=rightMax;
    		}
    		
    			
    	}
    
    		return maxValPtr;
    
    	// return a maxValPtr points to the node with maximum value for the tree
    	
    }



    This is the full code for the whole thing if you want to look at it:
    http://studentweb.uwstout.edu/clouti...rytreemax.html

    Any help would be appreciated
    Last edited by krizam; 12-05-2005 at 10:53 AM.

  2. #2
    Join Date
    Dec 2003
    Posts
    3,366
    You should re-write this thing.

    It looks like, from a tired person's eyes, that the thing iterates over all the guys but replaces with NULL on every leaf!!

    Its doing a traversal that looks good in the else area, but EVERY time you hit a null pointer, you lose the value of max and replace it with null. Oops??
    Last edited by jonnin; 12-05-2005 at 05:14 PM.

  3. #3
    Join Date
    Aug 2005
    Location
    Melbourne...Australia
    Posts
    279
    I have done a similar program but not with templates. I used Linked lists to implement my binary Tree.. Anyway you may get some tips from this? It can be done recursively..

    Code:
     getRightmostData()
                  { if(right == null)
                   return data;
              else 
                  return right.getRightmostData(); }
    I did this Java and just tried to roughly convert it over for you.. :)

  4. #4
    Join Date
    Dec 2003
    Posts
    3,366
    His is recursive too.
    and that doesnt look correct either? The if/else seems bad, won't this just return
    the deepest data (his list is not in order remember)?

    It reads:

    if your on the deepest one,
    return data (how do you know this ones the largest)
    else
    go deeper //you dont check these values if right is not null, which it isnt on the way back up the stack.

  5. #5
    Join Date
    Aug 2005
    Location
    Melbourne...Australia
    Posts
    279
    Yes you are correct, I didnt realise his list was not ordered..

    My apologies for not reading the whole thread!
    Last edited by Code_Nerd; 12-05-2005 at 07:00 PM.

Similar Threads

  1. Getting a GUI to run
    By Eric in forum Java
    Replies: 4
    Last Post: 04-14-2006, 09:09 AM
  2. Packed Data(Comp-3, etc)
    By Marcos in forum VB Classic
    Replies: 3
    Last Post: 01-25-2006, 11:18 AM
  3. Getting a list of files into an array
    By Scott in forum VB Classic
    Replies: 12
    Last Post: 12-21-2001, 04:21 PM
  4. Getting a GUI to function
    By Eric in forum Java
    Replies: 1
    Last Post: 11-27-2001, 06:53 AM
  5. Trying to print a PDF File from VB
    By Kunal Sharma in forum VB Classic
    Replies: 2
    Last Post: 04-25-2000, 03:45 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center