Homework #
令度为2的结点数为
$$n_2$$，叶子结点数为
$$n_0$$；
- 树中当且只有根结点和一个左叶子结点时，$$n_2 = 0, n_0 = 1$$满足关系$$n_2 = n_0 - 1$$；
- 假设对于有$$n'=n-1, n\geq3$$个结点的二叉树，满足关系$$n_2' = n_0' - 1$$，记作$$Tree_{n-1}$$，现在增加一个叶子结点，
得到新树记作
$$Tree_n$$：
-
若增加叶子结点所至双亲结点先前的度为0，则此时其度为1，
$$Tree_n$$度为0的结点数不变，度为2的结点数不变，
则关系
$$n_2 = n_0 - 1$$仍然成立。
-
若增加叶子结点所至双亲结点先前的度为1，则此时其度为2，
$$Tree_n$$度为0的结点数加一，度为2的结点数加一，
则关系
$$n_2 = n_0 - 1$$仍然成立。
-
综上所述，度为2的结点数比叶子结点数小一。
-
对于有且只有一个（叶子）结点的满二叉树，显然有
$$I=0,E=0,n=0$$，满足关系
$$E=I+2n$$；
-
假设对于有
$$n'=n-1,n\geq1$$个内部结点的满二叉树，都有
$$E'=I'+2n'$$，记作
$$Tree_{n-1}$$，现于其中一个叶子结点
$$node_{x}$$下
增加两个结点，使得其仍为满二叉树，记作
$$Tree_n$$。同时
$$node_{x}$$的深度记作
$$d_x$$，对新增结点显然有深度
$$d_{x+1}=d_x+1$$；此时，
$$node_{x}$$由外部结点变为内部结点，同时新增两个外部结点，于是有：
- $$E=E'-d_x+2d_{x+1}=E'+d_x+2$$
- $$I=I'+dx$$
又因为
$$E'=I'+2n'=I'+2n-2$$，联立上述两式可得
$$E=I+2n$$，关系仍然成立。
- 综上所述，$$E=I+2n,n\geq0$$成立。