常用性质
一棵二叉树第 i 层的最大结点数为 2^( i-1), i>1
深度为 k 的二叉树有最大节点数 2^k - 1, k>1（等比数列求和：s = (a1 - an*q) / (1- q), q != 1）
对于任何非空的二叉树 T，若 n0 表示叶节点的个数， n2 表示度为 2 的非叶结点个数，那么两者满足关系 n0 = n2 + 1（结点总数 n = n0 + n1 + n2 = B + 1 = n1 + 2*n2 + 1，B 为边的数量）
二叉树的种类
结构分类
完美二叉树（prefect binary tree）
第 4 层的最大结点数为 2^( 4-1) = 8
最大节点数 2^4 - 1 = 15
n0 = 8, n1 = 0, n2 = 7<br>n0 + n1 + n2 = n1 + 2*n2 + 1; n0 = n2 + 1
完全二叉树（complete binary tree）
完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
完美(Perfect)二叉树 VS 完全(Complete)二叉树
将上图中的编号为 15, 14, 13, 12, 11 叶子结点都拿掉(从右到左的顺序)
上图就不是一棵完全(Complete)二叉树
完满二叉树(Full Binary Tree)
所有非叶子结点的度都是2（只要你有孩子，你就必然是有两个孩子）
完满(Full)二叉树 VS 完全(Complete)二叉树 VS 完美(Perfect)二叉树
斜二叉树（skewed binary tree）
平衡二叉树（balanced binary tree）也称 AVL 树
节点序列分类
二叉搜索树（binary search tree）也称二叉排序树或二叉查找树
性质
节点 N 左子树上的所有节点的值都小于等于节点 N 的值
节点 N 右子树上的所有节点的值都大于等于节点 N 的值
左子树和右子树也都是 BST
