令 TTT 是一个正则二元树,它有 iii 个内顶点(出度为 222 的顶点).如果 EEE 为所有内顶点深度之和, III 为所有叶节点的深度之和,证明:
假设节点数小于 ppp 时成立,往证节点数为 ppp 时也成立:
若去掉根节点及其边,产生的两棵子树节点树均小于 ppp ,符合归纳假设.加回根节点后,两棵子树所有节点深度均加 111 .故:
I=I1+I2+(p−i1−i2−1)I = I_1 + I_2 + (p - i_1 - i_2 - 1)I=I1 +I2 +(p−i1 −i2 −1) E=E1+E2+i1+i2E = E_1 + E_2 + i_1 + i_2E=E1 +E2 +i1 +i2  i=i1+i2+1i = i_1 + i_2 + 1i=i1 +i2 +1
仅证需证明 I1+I2+(p−i1−i2−1)=E1+E2+i1+i2+2(i1+i2+1)I_1 + I_2 + (p - i_1 - i_2 - 1) = E_1 + E_2 + i_1 + i_2 + 2 (i_1 + i_2 + 1)I1 +I2 +(p−i1 −i2 −1)=E1 +E2 +i1 +i2 +2(i1 +i2 +1)
令 TTT 是一个正则 mmm 元树,它有 iii 个内顶点(出度为 mmm 的顶点).如果 EEE 为所有内顶点深度之和, III 为所有叶节点的深度之和,证明:
I=(m−1)E+miI = (m-1)E + miI=(m−1)E+mi