algrn912005 Ответов: 3

Средняя глубина бинарного дерева поиска

Привет,
У меня возникли небольшие проблемы с созданием функции для поиска средней глубины бинарного дерева поиска. Определение средней глубины дерева-это сумма глубины всех узлов, деленная на общее число узлов. Определение глубины узла - это расстояние от корня дерева до узла. Кто-нибудь может мне помочь?

Таким образом, примером может быть, если у вас есть BST:

     6
   /   \
  3     8
 / \     \
2   4     9
     \
      5


Тогда средняя глубина равна 1,571, потому что от 6 до 3 имеет глубину 1, а от 6 до 2 имеет глубину 2. Сделайте это для остальных узлов и суммируйте их, а затем разделите на общее количество узлов, и это будет средняя глубина. Так что это (1 + 1 + 2 + 2 + 2 + 3)/7. Кто-нибудь может мне помочь?

3 Ответов

Рейтинг:
26

Sergey Alexandrovich Kryukov

Проблема не в том, чтобы найти глубину, проблема в том, чтобы сделать это только один раз. Вот как это сделать: не создавайте функцию для поиска глубины текущего узла. Вместо этого включите глубину текущего узла в качестве параметра рекурсивной функции.

void AccumulateNodeInfo(
    node * parent, uint parentDepth,
    uint & accumulatedDepth, uint & nodeCount);


Инициализировать accumulatedDepth и nodeCount 0 и вызовите эту функцию с корневым узлом. Функция должна вызывать дочерние элементы текущего узла с помощью parentDepth + 1, добавлять parentDepth к accumulatedDepth и увеличьте nodeCount. После этого функция обходит все дерево, accumulatedDepth будет равна сумме глубин и nodeCount равно количеству узлов.

—СА

algrn912005

Спасибо, это прекрасно сработало.

Sergey Alexandrovich Kryukov

Отличный. Пожалуйста.
Спасибо, что приняли это решение.
Удачи,
--СА

Рейтинг:
2

mbue

Для каждой вещи, которую я делаю с деревьями, я использую функции ходьбы.
Пример для функции ходьбы :

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

Удачи.

Рейтинг:
2

Member 12884199

Вы должны сразу найти среднюю глубину .Я использую эту формулу - >
AD (n)=ln (n+1)÷ln2
Это вы можете найти из Формулы, так как мы можем найти максимальное количество узлов по / / n=(2^d)-1
Где d-глубина дерева.