Thread: General Trees, calculating height

  1. #1
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640

    General Trees, calculating height

    Ok, I've been trying this over and over and I can't seem to get it right. I have a general tree, and I just need to calculate the height of the tree. This is what I have so far:

    Code:
    //Is a member function of my general tree class
    		int getHeight(gNode *rt)
    		{
    			if (rt == NULL) return 0; //if given node is null, return 0
    			if (rt->isLeaf()) return 1; //if given node is a leaf, return 1
    			int height = 0; //height starts at 0
    			if (rt->getSib() != NULL) //if node has a sibling
    				height = getHeight(rt->getSib()); //set height as height of sibling
    			if (!rt->isLeaf())  //if node is not a leaf
    				height += getHeight(rt->getChild()); //height += height of child
    
    			return height;
    		}
    All I can say is that the answers I get are close. I know I'm missing something, but I don't know what it is, any ideas?
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  2. #2
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    this is my feeble attempt - it may be WAY off
    this is a assuming that child != child->sibling->sibling
    Code:
    int getHeight(gNode *rt)
    {
    	
    	if(!rt)      
    		return 0;     
    	//recursive stopper 
    	if(rt->isLeaf())
    		return 1;
    
    	int path1, path2;
    	path1 = path2 = 0;
    
    	//i'm assuming there much be a child to have a sibling
    	if(rt->getChild())
    	{
    		//find out how long the path is straight down through all the children
    		path1 = getHeight(rt->getChild());
    
    		//if siblings - find the longest path thru them
    		//this should visit all the siblings and the children
    		//..children first.
    		if(rt->getSib())
    			path2 = getHeight(rt->getSib()) - 1;
                      //we subtract 1 because we are making a 'horizontal' move, but the design
                     // of this function will add 1 to the return value automatically. subtracting
                     //one offsets this
                     //edit: by 'horizontal' i'm assuming each child make the
                     ///tree grow taller (downward), and that each sibling
                    //makes it grow wider (from a child) 
    
    	}
    
    	//the height is the longest path from the root to a leaf
    	//path 1 is the longest path of the children
    	//path 2 is is the longest path of a mixture of children and siblings
             //return the largest of the 2 paths plus one (this node)
    
    	//if path 1 and 2 are the same, save yourself a few CPU cycles
    	//and return it automatically	
             if(path1 >= path2)
    		return (path1 + 1);
    	else
    		return (path2 + 1);
    		
    }
    edit: btw - i read somewhere that NULL is not officialy part of c++ and that NULL should not be used in c++. even for pointers. but i can't remember where i read this, so i guess it's up to you
    Last edited by misplaced; 04-08-2005 at 01:35 AM.
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    There are some good tree tutorials in Prelude's Corner of the FAQ. You may want to give them a read.

    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Why are you settting the node height to the height of the sibling and then adding the height of the node? IF a node and its siblings are all on the same level tt seems to me you want to be returning the maximum value between all of the siblings with the height being calculated as child's height + 1.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A bunch of Linker Errors...
    By Junior89 in forum Windows Programming
    Replies: 4
    Last Post: 01-06-2006, 02:59 PM
  2. struct question
    By caduardo21 in forum Windows Programming
    Replies: 5
    Last Post: 01-31-2005, 04:49 PM
  3. 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
  4. Ok, Structs, I need help I am not familiar with them
    By incognito in forum C++ Programming
    Replies: 7
    Last Post: 06-29-2002, 09:45 PM
  5. Outputting String arrays in windows
    By Xterria in forum Game Programming
    Replies: 11
    Last Post: 11-13-2001, 07:35 PM