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