Проблемы с функцией длины внутреннего пути

Question

Мне было предложено вычислить среднюю глубину узла как в дереве двоичного поиска, так и в дереве AVL. В ходе некоторых исследований я обнаружил, что средняя глубина дерева - это длина внутреннего пути, деленная на количество узлов в дереве, и что указана длина внутреннего пути (сумма длин пути каждого узла в дереве) с помощью этого рецидива:

D(1) = 0, D(N) = D(i) + D(N − i − 1) + N − 1 

, где D (N) представляет собой дерево с N узлами D (I), является IPL левого поддерева, и D (Ni-1) является IPL правого поддерева ,

Используя это, я написал эту функцию:

int internalPathLength(Node *t, int& sum) const{ 
     if(t == nullptr || (t->left == nullptr && t->right == nullptr)) { 
      return 0; 
     } 
     else { 
      int a = 0; 
      sum += internalPathLength(t->left, sum) + internalPathLength(t->right, sum) + (countNodes(t,a)-1); 
      cout << sum << endl; 
      return sum; 
     } 

Эта функция дает мне, с двоичным деревом поиска 565 узлов, с IPL из 1,264,875,230 и средней глубины 2,238,717, в чудовищно большом количестве. Используя его на дереве AVL аналогичного размера, я получаю IPL от -1,054,188,525 и среднюю глубину -1,865,820, что является отрицательным числом на вершине неистово высокой. Что-то не в порядке с моей интерпретацией/реализацией повторения? что еще я могу попробовать? Или значения, которые я получаю в нормальном диапазоне для этого вычисления в конце концов?

Answer 1

Проблема заключается в том, что вы передаете sum по ссылке, поэтому она увеличивается с шагом слишком много раз. Вам совсем не нужна эта сумма. Это должно работать:

int internalPathLength(Node *t) const{ 
     if(t == nullptr || (t->left == nullptr && t->right == nullptr)) { 
      return 0; 
     } 
     else { 
      return internalPathLength(t->left) + internalPathLength(t->right) + countNodes(t) - 1; 
     } 
    } 

Это не оптимально, потому что функция подсчета, вероятно, также рекурсивна. Вы можете подсчитать узлы в каждом поддереве в той же рекурсии, а затем использовать его. Например:

int internalPathLength(Node *t, int &count) const{ 
     if(t == nullptr) { 
      count = 0; 
      return 0; 
     } 
     else if(t->left == nullptr && t->right == nullptr){ 
      count = 1; 
      return 0; 
     } 
     else { 
      count = 1; 
      int leftCount; 
      int rightCount; 
      int sum = internalPathLength(t->left, leftCount) + internalPathLength(t->right, rightCount); 

      count += leftCount + rightCount; 

      return sum + count - 1; 
     } 
    }