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

C-方法找到从根到叶的平均距离

C- method find average distance from root to leaves

c

binary-tree