数据结构-5.4.二叉树的性质
一.二叉树的常考性质：
常见考点1：结点个数的性质
设非空二叉树(度最大为2,最小为0)当中度为0的结点个数为a，度为1的结点个数为b，度为2的结点个数为c，那么a=b+c：
推导过程：设该非空二叉树共有n个结点，那么n=a+b+c，
由树的结点数=总度数+1，n = ( 0 * a + 1 * b + 2 * c ) + 1 = b+2c+1
所以a = c +1
常见考点2：树的每层中的结点个数范围
常见考点3：树中结点最多可以有多少个
二.完全二叉树的常考性质：
常见考点1：已知结点个数，求完全二叉树的高度
法一：
上述图片中高度为h的完全二叉树的结点有n个，完全二叉树可由满二叉树推出来，
高度为h的满二叉树的结点有2的h的幂减1个，
高度为h-1的满二叉树的结点有2的(h-1)的幂减1个，
由于该完全二叉树的高度为h，所以它的结点数是一定大于高度为h-1的满二叉树的结点数，不能取等，取等的话完全二叉树的高度就只能是h-1，因为高度为h-1的满二叉树的结点已经满了，要想等于该h-1的满二叉树的结点数，该完全二叉树的高度只能为h-1，由于完全二叉树可由满二叉树推出来，所以高度为h的完全二叉树的结点数是小于或等于高度为h的满二叉树的结点数，可以取等，因为满二叉树是特殊的完全二叉树且高度都为h。
(上述图片里是向上取整得出h的结果)
法二：
思路：首先要保证完全二叉树的高度为h，那么第h-1层就一定排满了(因为完全二叉树最多只能有一个度为1的结点，达到完全二叉树的结点最少时且高度为h，那么就只能在第h层放一个结点，此时第h-1层就必须排满，如果把这一个结点放到第h层以外，编号就会与满二叉树不符)，再多一个就能排到第h层了，其次，当h层全部排满时，就不能再添加结点了，否则就排到第h+1层了
(上述图片里是向下取整得出h的结果)
常见考点2：对于完全二叉树，可以由总结点数n推出度分别为0，1，2的结点个数为a,b,c
推导过程：在完全二叉树中，n=a+b+c，
由树的结点数=总度数+1，n = ( 0 * a + 1 * b + 2 * c ) + 1 = b+2c+1
所以a = c +1 -> a+c = 2c+1 ，所以度为0的结点(叶子结点)总数和度为2的结点总数的和为奇数
完全二叉树最多只能有一个度为1的结点,所以b只能为1(奇数)或者0(偶数)
因此，如果设n=2k为偶数，那么b只能为1，a为k,那么c为k-1
如果设n=2k-1为奇数，那么b只能为0，a为k,那么c为k-1
三.总结：
