二进制搜索树的平均深度 [英] Average depth of Binary search tree

问题描述

我在创建函数以查找二叉搜索树的平均深度方面遇到了一些麻烦。树的平均深度的定义是所有节点的深度除以节点总数的总和。节点深度的定义是从树的根到节点的距离。任何人都可以帮助我吗？



如果您的BST为：

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

然后平均深度为1.571，因为6到3的深度为1，而6到2的深度为2。其余的节点并将它们相加然后除以节点的总数，即平均深度。所以它是（1 + 1 + 2 + 2 + 2 + 3）/ 7。任何人都可以帮助我吗？

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?

推荐答案

问题不是找到深度，问题是只做一次。以下是执行此操作的方法：不要创建用于查找当前节点深度的函数。相反，包括当前节点的深度作为递归函数的参数。

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);

将 cumulativeDepth 和 nodeCount 初始化为0并使用根节点调用此函数。该函数应该使用 parentDepth + 1 调用当前节点的子节点，将 parentDepth 添加到 cumulativeDepth 并增加 nodeCount 。在此函数遍历所有树之后， cumulativeDepth 将等于深度的总和，并且 nodeCount 等于节点数。

-SA

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

对于我用树做的每件事我都使用步行功能。

步行函数示例：

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.

你必须立刻找到平均深度。我使用这个公式 - >

AD（n）= ln（n + 1）÷ln2

您可以从公式中找到，因为我们可以通过//找到最大的节点数n = （2 ^ d）-1

其中d是树的深度。

You have to find average depth at once .I use this formula->
AD(n)=ln(n+1)÷ln2
This you can find from the formula as we can find maximum no.of nodes by //n=(2^d)-1
Where d is depth of the tree.

这篇关于二进制搜索树的平均深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！