学步园

普通树：

由n个节点构成的二叉树的形态总数为：Cⁿ_2n/(n+1).

节点数、 度数（分叉数） 、叶节点数、 边数 之间的关系

1. 总节点数 = 总边数+1；

2. 总边数 = 总度数 = 总分叉数​

    ​例子：设树T的度为4，其中度为1，2，3，4的节点个数分别为4，2，1，1，则T中的叶子数为？

    ​总节点数=1*4+2*2+3*1+4*1 +1 =16

    ​叶节点数= 节点数 - 总分叉数 = 16 - 4-1-1-2 = 8

二叉树：

1. 第i层最多有 2^(i-1)个节点

2. 深度为k的二叉树最多有 2^(k) - 1 个节点

3. 二叉树中叶节点数 n0 度为2的节点数为 n2 则 n0=n2+1

4. m个节点的完全二叉树 深度 n=log m[下取整] + 1；

    ​例子：699个节点的完全二叉树的叶子节点数位多少？

    解法1：

    ​​深度为 n = log699+1 = 10；

    ​深度为10的满二叉树节点数为2^10-1=1023>699,故叶子节点出现在9、10 两层；

    ​第10曾叶节点个数为：699 - 2^9+1 = 189;

    ​第9曾叶节点个数为：2^(9-1) - 189/2[上取整] = 161;

    ​共189+161=350个叶节点

    ​解法2：

    ​n=n0+n1+n2

    ​n0=n2+1;

    ​又完全二叉树度为1的节点个数只可能为0或1；

    ​故n0=n/2或(n+1)/2  即n0=n/2[上取整]

所以叶节点数为 [699]/2=350