数据结构树的平均高度★数据输入输入第一行一个正整数N(2

Question

数据结构树的平均高度
★数据输入
输入第一行一个正整数N (2 < N < 10000) 表示该树有N个结点.
接下来N-1行,每行两个整数a b ,表示a 是b的父亲结点,数据保证所给的是一棵树,
结点的编号为1到N.
★数据输出
输出一行一个整数,表示该树的平均高度,结果保留3位小数.
示例
7
1 2
1 3
1 4
3 5
3 6
6 7
输出1.857

Answer 1

你这个是有问题的吧.7个节点,算出来是17/7=2.429
1个一层节点,3个两层节点,2个三层节点,1个四层节点,
1x1+3x2+2x3+1x4=17,你怎么算出来是13呢?
怎么会是1.857呢?
import os,sys
def find(root,f):
#print "root:",root," f:",f
for leaf in root:
#print ">>>leaf ",leaf
if leaf[0]==f:
#print "leaf[1]:",leaf[1]
return leaf[1]
else:
x=find(leaf[1],f)
if x!=None:
return x
return None
sum=0
def calc(root,level):
global sum
print "level,sum:",level,sum
for leaf in root:
print "level:",level,leaf
sum+=level*1
calc(leaf[1],level+1)
#sum+=num
print "sum:",sum
return sum
root=[]
tr=[(1,2),(1,3),(1,4),(3,5),(3,6),(6,7)]
for f,c in tr:
child=find(root,f)
#print "f,c,child:",f,c,child
if child==None:
leaf=[f,[ [c,[]] ]]
root.append( leaf )
else:
child.append( [ c,[] ] )
print root
print calc(root,1)/7.0