二叉树的定义
一个有穷的结点集合：
这个集合可以为空；
若不为空，则它是由根结点和称为其左子树和右子树的两个不相交的二叉树组成
二叉树的子树有左右顺序之分
特殊的二叉树
斜二叉树（Skewed Binary Tree）
完美二叉树（Perfect Binary Tree）或满二叉树（Full Binary Tree）
完全二叉树（Complete Binary Tree）
有n个结点的二叉树，对树中结点按从上到下，从左到右顺序进行编号，编号为i（1<=i<=n）结点与满二叉树编号为i的结点位置相同
二叉树的几个重要性质
- 二叉树的第i层最大结点数为2^(i-1)，i>=1
- 深度为k的二叉树有最大结点总数为2^k-1，k>=1
- 对于任何非空二叉树T，若n0表示叶结点的个数、n2是度为2的非叶结点的个数，那么两者满足关系n0=n2+1
二叉树的存储结构
顺序存储结构
完全二叉树按从上到下，从左到右顺序存储n个结点的完全二叉树的结点父子关系
- 非根结点（序号>1）的父结点的序号是⌊i/2⌋；
- 结点（序号为i）的左孩子结点的序号是2i，若2i>n则没有左孩子
一般二叉树也可以采用这样的结构，但会造成空间浪费
链表存储
二叉树的遍历
先序、中序和后序遍历的过程中经过结点的路线相同，只是访问各结点的时机不同
先序遍历
根结点 -> 左子树 -> 右子树
中序遍历
左子树 -> 根结点 -> 右子树
后序遍历
左子树 -> 右子树 -> 根结点
