Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++ Recursive Trees
Hi,
I'm having a little trouble with creating a function to find the average depth of a binary search tree. The definition of average depth of a tree is the sum of the depth of all nodes divided by the total number of nodes. The definition of the depth of a node is the distance from the root of the tree to the node. Can anyone help me?
 
So an example would be if you had a BST of:
 
                    6
                  /   \
                 3     8
                / \     \
               2   4     9
                    \
                     5
 
Then the average depth is 1.571 because from 6 to 3 has depth of 1 and 6 to 2 has depth of 2. Do that for the rest of the nodes and sum them up then divide by the total number of nodes and that is the average depth. So it's (1 + 1 + 2 + 2 + 2 + 3)/7. Can anyone help me?
Posted 23-Apr-11 15:24pm
Edited 23-Apr-11 15:44pm
v3
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

The problem is not finding the depth, the problem is to do it just once. Here is the way to do it: do not create a function for finding a depth of the current node. Instead, include the depth of a current node as a parameter of the recursive function.
 
void AccumulateNodeInfo(
    node * parent, uint parentDepth,
    uint & accumulatedDepth, uint & nodeCount);
 
Initialize accumulatedDepth and nodeCount to 0 and call this function with the root node. The function should call the current node's children with parentDepth + 1, add parentDepth to accumulatedDepth and increment the nodeCount. After this function traverses all the tree, accumulatedDepth will be equal to sum of the depths and nodeCount equal to the node count.
 
—SA
  Permalink  
Comments
algrn912005 at 24-Apr-11 16:53pm
   
Thank you, that worked beautifully.
SAKryukov at 24-Apr-11 21:14pm
   
Great. You're welcome.
Thanks for accepting this solution.
Good luck,
--SA
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

For every thing i do with trees i use walk functions.
Example for a walk function:
class INode
{
public:
  INode*  _child;
  INode*  _next;
};
 
class IWalk
{
public: // IWalk
  virtual HRESULT Enter(INode* pNode) = 0;
  virtual HRESULT Leave(INode* pNode) = 0;
};
 

 
void Walk(INode* pNode,IWalk* pWalk)
{
  if(pNode && pWalk)
  {
    if(S_OK==pWalk->Enter(pNode))
    {
      for(INode* p=pNode->_child;p;p=p->_next) Walk(p,pWalk);
      pWalk->Leave(pNode);
    }
  }
}
 

//////////
// implementation
class iWalk : public IWalk
{
public: // IWalk
  virtual HRESULT Enter(INode* pNode){ ++_node_count; _node_level_sum += _level; ++_level; return S_OK; }
  virtual HRESULT Leave(INode* pNode){ --_level; return S_OK; }
 
  iWalk(){ _node_count = _node_level_sum = _level = 0; }
 
  unsigned int  _node_count;
  unsigned int  _node_level_sum;
  unsigned int  _level;
};
 
double Calc()
{
  iWalk  w;
  Walk(root,&w);
  return 0<w._node_count?(double)w._node_level_sum/(double)w._node_count:0;
}
 
Good luck.
  Permalink  

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 OriginalGriff 195
1 ProgramFOX 130
2 Maciej Los 105
3 Sergey Alexandrovich Kryukov 85
4 Afzaal Ahmad Zeeshan 82
0 OriginalGriff 6,564
1 Sergey Alexandrovich Kryukov 6,048
2 DamithSL 5,228
3 Manas Bhardwaj 4,717
4 Maciej Los 4,150


Advertise | Privacy | Mobile
Web01 | 2.8.1411022.1 | Last Updated 24 Apr 2011
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100