binary tree depth

This is a discussion on binary tree depth within the C Programming forums, part of the General Programming Boards category; hi, i just want to count the levels of random binary tree. i have used a queue to do a ...

  1. #1
    Registered User trekker's Avatar
    Join Date
    Mar 2002
    Posts
    46

    binary tree depth

    hi,
    i just want to count the levels of random binary tree.
    i have used a queue to do a level-order traversal.
    So the depth is equal to the height of the tree node
    stored int the tail of the queue,
    here's the algorithms i used to get the level of the tree

    Code:
    int levelCtr, nodeCtr = 0;
    	QueueNodePtr headPtr = NULL, tailPtr = NULL, indexPtr = NULL, lastPtr = NULL;
    	TreeNodePtr p;/*more code*/
    lastPtr = tailPtr;
    	indexPtr = headPtr;
    	
    	p = &( lastPtr -> qData );
    	
    	while ( lastPtr != headPtr ) {
    		while ( ( indexPtr -> qData.leftPtr != &( lastPtr -> qData ) ) || ( indexPtr -> qData.rightPtr != &( lastPtr -> qData ) ) ) {
    			indexPtr = indexPtr -> nextPtr;
    		}
    		
    		lastPtr = indexPtr;
    		indexPtr = headPtr;
    		
    		levelCtr++;
    	}
    but the debugger shows that p doesn't get the address of qData,
    but the address of lastPtr

    any hints are welcome,
    trk

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    int depthCount( Node *n )
    {
        int x=1,y=1;
    
        if ( !n ) return 0;
    
        x += depthCount( n->left );
        y += depthCount( n->right );
        return x > y ? x : y;
    }
    I think that'll do the trick. I haven't tested it, I just threw it together. However, it should work for what you want, assuming I'm understanding what you want done.

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

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    but the debugger shows that p doesn't get the address of qData,
    but the address of lastPtr
    This is normal. The address of the first element of a structure is generally the address of the structure.
    Code:
    #include <stdio.h>
    
    int main (void)
    {
     struct
     { int x, y} myStruct;
     printf ("myStruct: %p\n", &myStruct);
     printf ("myStruct.x: %p\n", &myStruct.x);
     printf ("myStruct.y: %p\n", &myStruct.y);
    
     return 0;
    }
    And the output
    Code:
    myStruct: 8f120
    myStruct.x: 8f120
    myStruct.y: 8f124
    Quzah's algorithm is the correct(TM) way to go about this kind of problem though; figure out the depth of the left subtree, the right subtree, pick the biggest, and add 1.
    Callou collei we'll code the way
    Of prime numbers and pings!

  4. #4
    Registered User trekker's Avatar
    Join Date
    Mar 2002
    Posts
    46
    The members of a structure have
    the address of the structure...i got that now.
    I was just trying to find another way except the usual
    recursive function.

    thanks and sorry for replying late,
    it's been a busy week

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. 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
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  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