二叉树和树
二叉树：概念和性质
定义
二叉树是结点的有穷集合。这个集合或者是空集，或者其中有一个成为根节点的特殊结点，其余结点分属两棵不相交的二叉树，这两棵二叉树分别是原二叉树（或者说是原二叉树的根结点）的左子树和右子树。
- 二叉树是一种递归结构，是最简单的树形结构，是复杂结构
基本概念
- 分类：空树、单点树、其他
- 结点：父结点、子结点、兄弟结点、叶结点
- 关系：父子关系、祖先关系、子孙关系
- 度数：一个结点的子结点个数称为该节点的度数，二叉树中叶结点的度数为0，分结点的度数可以是1或2
- 路径：从一个祖先结点到其任何子孙结点都存在一系列的边，称为一条路径，路径中边的条数称为该路径的长度。每个结点到其自身的路径长度为0
- 层次结构：根结点的层次为0，对于k层结点，其子结点是k+1层的元素。从根结点到树中任一结点的路径长度就是该结点所在的层数，称为该结点的层数
- 高度：一棵二叉树的高度就是树中结点的最大层数（最长路径的长度）。只有根结点的树高度是0
二叉树的性质
- 在非空二叉树第i层至多有$2^i$个结点$(i>=0)$
- 高度为h的二叉树至多有$2^{h+1}-1$个结点$(h>=0)$
- 任何非空二叉树T，如果其叶结点的个数为$n_0$，度数为2的结点的个数为$n_2$，那么$n_0=n_2+1$
满二叉树和扩充二叉树
满二叉树
- 定义：如果二叉树中所有分支结点的度数都是2，则称为满二叉树
- 性质：满二叉树的叶结点比分支结点多一个
扩充二叉树
- 定义：对于二叉树T，加入足够多的新叶结点，使T的原有结点都变成度数为2的分支结点，得到二叉树称为T的扩充二叉树。其新增的结点称为外部结点，原树T的结点称为其内部结点。空树的扩充二叉树为空树
- 性质：是满二叉树，扩充二叉树的外部结点的个数比内部结点个数多1
完全二叉树
- 定义：对于一棵高度为h的二叉树，如果第0-h-1层的结点都满（就是说$0<=i<=h-1$，第i层有$2^i$个结点）。如果下一层的结点不满，则左右结点在最左边连续排列，空位都在右边。这种二叉树称为完全二叉树。
- 性质
- n个结点的完全二叉树高度$h=\lfloor \log_2n \rfloor$，即不大于$\lfloor \log_2n \rfloor$的自最大整数。设完全二叉树有n个结点，高度是h。由于T在n个结点的二叉树里面最低，所以$2^{h}-1<n\leq 2^{h+1}-1$，即$2^h \leq n<2^{h+1}-1$，取对数得$h \leq \log_2n<h+1$
- 包含n个结点的完全二叉树的结点按层次并按从左到右的顺序从0开始编号，对于任一结点i（$0 \leq i \leq n-1$）有：
- 序号为0的是根结点
- 对于i>0，其父结点的编号是$(i-1)/2$
- 对于$ 2i+1<n$，其左孩子结点序号为$2i+1$，否则没有左孩子结点
- 对于$2i+2<n$，其右孩子结点序号为$2i+2<n$，否则没有右孩子结点
遍历二叉树
分类
深度优先遍历：先序遍历、中序遍历、后序遍历
宽度优先遍历
- 如果知道了一棵二叉树的中序序列，又知道另种遍历序列（先序或者后序序列），就可以唯一的确定这个二叉树