函数表示return二叉搜索树的平均深度

Question

我有以下二叉树结构，我想编写一个函数来计算和return树中对象的平均深度。 这是我正在尝试做的事情：

• 计算树的总高度
• 划分总数 height/total 个节点

但是，我一事无成，希望就如何着手实施该算法提供任何有用的建议。

typedef struct tree_s tree_t;
struct tree_s {
    int num;
    tree_t *left;
    tree_t *right;
}


int total_depth(tree_t *tree, int accum) {
    if (tree == NULL) {
        return accum; /* done */
    }
    accum = accum + total_depth(tree->left, accum+1);
    accum = accum + total_depth(tree->right, accum+1);
    return accum;
}

我的递归函数 total_depth 似乎有问题，因为我得到的数字大得离谱。

Answer 1

你应该这样做：

int total_depth(tree_t *tree, int accum)
{
    if (tree == NULL) {
        return 0;
    }
    return accum +
        total_depth(tree->left, accum + 1) +
        total_depth(tree->right, accum + 1);
}

total_depth(root, 0);