wcppcw
Newbie level 1
a problem of binary tree
i have met a problem:
if a binary tree has n leaf nodes, the maximal depth of the tree is n-1 and the minimal is ceil( log2
), what is the mean depth of the binary tree?
i have got a formular conclusion:
avg_k=Σ(k*p_k)
where p_k means the probability of the depth equals to k,
p_k=c(2^k-1-i, n-1-i)/c(2^i, n-1)!
but it seems to be wrong!
who can help me!?
thx!
i have met a problem:
if a binary tree has n leaf nodes, the maximal depth of the tree is n-1 and the minimal is ceil( log2
), what is the mean depth of the binary tree?i have got a formular conclusion:
avg_k=Σ(k*p_k)
where p_k means the probability of the depth equals to k,
p_k=c(2^k-1-i, n-1-i)/c(2^i, n-1)!
but it seems to be wrong!
who can help me!?
thx!