binaryTree
- 节点度最大为2 ,可以为空
- 左子树和右子树有序
- 某节点只有一棵子树,区分左右子树
- 非空二叉树的第i层，最多有 2^(i-1) 个节点 (i>=1)
- 高度为h的二叉树,最多总共有2^h-1个节点 (h>=1)
- 对于任何一棵非空二叉树，如果叶子节点个数为 n0，度为2 的节点个数为 n2，则有：n0 = n2 +1
- 推理:
- 假设度为 1 的节点个数为 n1，那么二叉树的节点总数 n = n0 + n1 + n2
- 二叉树的边数T= n1+ 2* n2 = n -1 = no + n1 + n2-1
- 度为1的节点有一条边,度为2的节点有两条边,叶子结点没有边
- 边的个数为总节点数减一
- 推理:
- 所有的节点的度要不是0,要不是2
- 所有节点的度都要么为0，要么为2。且所有的叶子节点都在最后一层
满二叉树一定是真二叉树,反之不一定
完全二叉树- 叶子节点只会出现最后 2层，且最后 1 层的叶子结点都靠左对齐
- 完全二叉树从根结点至倒数第 2层是一棵满二叉树
- 度为1 的节点只有左子树
- 度为 1 的节点要么是1个，要么是0个
- 同样节点数量的二叉树，完全二叉树的高度最小
一些性质
- 一棵有 n 个节点的完全二叉树(n > 0),从上到下、从左到右对节点从 1 开始进行编号，对任意第i个节点
- 如果i=1，它是根节点
- 如果i＞1，它的父节点编号为 floor(i / 2)
- 如果 2i≤ n， 它的左子节点编号为 2i
- 2i>n: 就没有左子节点
- 同理拥有2i+1的右子节点结论
