C- метод определения среднего расстояния от корня до листьев

Question

Как найти среднее расстояние от корня до всех листьев в двоичном дереве. Расстояние означает количество ребер между узлами.Метод получения рута. Я думаю добавить новые поля в узел.

Мой код в C:

 // A Binary Tree Node 
struct Node 
{ 
    int data; 
    Node *left, *right; 
}; 

int findDistance(Node *root) 
{ 
    // Base case 
    if (root == NULL) 
      return -1; 

    // Initialize distance 
    int dist = -1; 

    if ((root->data != NULL) || 
        (dist = findDistance(root->left)) >= 0 + (dist = findDistance(root->right)) >= 0) /2

        return dist + 1; 

    return dist; 
} 

Answer 1

Я ожидаю, что следующее будет работать, но я не проверял это.

typedef struct
{
    int Number; // Number of nodes in tree.
    int TotalDepths; // Total of depth of each node.
} NAndTotal;

static NAndTotal FindNumberAndTotalDepth(Node *Root)
{
    if (Root == NULL)
        return (NAndTotal) { 0, 0 }; // No nodes in empty tree.

    // Start an NAndTotal with information about the root node.
    NAndTotal A = { 1, 0 }; // Root is 1 node at depth 0.
    // Add the left subtree.
    NAndTotal B = FindNumberAndTotalDepth(Root->left);
    A.Number += B.Number; // Including left subtree adds its nodes.
    A.TotalDepth += B.TotalDepth + B.Number; Each of its nodes become one deeper when placed under this node.

    // Add the right subtree.
    B = FindNumberAndTotalDepth(Root->right);
    A.Number += B.Number; // Including right subtree adds its nodes.
    A.TotalDepth += B.TotalDepth + B.Number; Each of its nodes become one deeper when placed under this node.

    return A;
}

double FindAverage(Node *Root)
{
    NAndTotal NT = FindNumberAndTotalDepth(Root);
    return (double) NT.TotalDepths / NT.Number;
}