pythontree
树
n (n>=0)
n=0根
Tn (n>=0) n=0
mT1, T2、T3……TnTSubTree
degreed(v)
0leaf
0
D33
child|BA
parent|AB
siblingBC
ABDGACEJ
BDGHI
levelL(v)L(4)
depth|4
DEDF
kn1,n2...nknin(i+1)n1nk|
=-13
m(m>=)A2
0
vivjL(vi)=L(vj)-11
22
k1k-1k
k1= 1 i2**(i-1)i>=11,2,4,8,16 2 k(2**k)-1k>=1 2-1 4-1=1+2=3 8-1=1+2+4=7 3 Tn02n2n0=n2+1 -1=2 n=n0+n1+n2n11 n-1n0+n1+n2-1 n0*0+n1*1+n2*2n2222*n2+n1 2*n2+n1=n0+n1+n2-1==>n2=n0-1 kkn(n>=1)n n(n>=1)nmath.ceil(log2(n+1)) h(2**h)-1=n83.169944h=log2(n+1) 4 nint()+1math.ceil() 5 n4i i=1i i>1int(i//2)2i2i2i+1 2i>nii2i 2i+1>nii2i+1 LRABCDEFGHI DLRABDGHCEIF LDRGDHBAIECFGDHBAEICF LRDGHDBIEFCA heap sort heap | 1 328451679 5 [0,3,2,8,4,5,1,6,7,9]index5 2 2A 1A A nn//25 11 O(nlognO(logn) O(1) 
15数据结构tree_堆排序
