二叉树：
二叉树是有限个结点的集合，这个集合或者是空集，或者是由一个根结点和两株互不相交的二叉树组成，其中一株叫根的做左子树，另一棵叫做根的右子树。
二叉树的性质：
- 性质1：在二叉树中第 i 层的结点数最多为2^(i-1)（i ≥ 1）
- 性质2：高度为k的二叉树其结点总数最多为2^k－1（ k ≥ 1）
- 性质3：对任意的非空二叉树 T ，如果叶结点的个数为 n0，而其度为 2 的结点数为 n2，则：n0 = n2 + 1
- 性质4：具有 n 个结点的完全二叉树的深度为 log2n + 1
满二叉树：深度为k且有2^k －1个结点的二叉树称为满二叉树
完全二叉树：深度为 k 的，有n个结点的二叉树，当且仅当其每个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应，称之为完全二叉树。（除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点）
注意：
仅有前序和后序遍历，不能确定一个二叉树，必须有中序遍历的结果
算法：
如果对每一个节点进行编号，你会用什么方式去遍历每个节点呢？
image.png
如果你按照 根节点 -> 左孩子 -> 右孩子 的方式遍历，即「先序遍历」，每次先遍历根节点，遍历结果为 1 2 4 5 3 6 7；
同理，如果你按照 左孩子 -> 根节点 -> 右孩子 的方式遍历，即「中序序遍历」，遍历结果为 4 2 5 1 6 3 7；
如果你按照 左孩子 -> 右孩子 -> 根节点 的方式遍历，即「后序序遍历」，遍历结果为 4 5 2 6 7 3 1；
最后，层次遍历就是按照每一层从左向右的方式进行遍历，遍历结果为 1 2 3 4 5 6 7。
