一、树的概念
1、树的定义
1）树
树是 n(n≥0) 个结点的有限集合。当 n>0 时，它是一棵非空树，满足如下条件：
1）有且仅有一个特定的结点，称为根结点Root；
2）除根结点外，其余结点分为 m 个互不相交的有限集合 T1、T2、…………、Tm，其中每一个 Ti(1≤i≤m) 又是一棵树，并且为根结点 Root 的子树。如图所示，代表的是一棵以 a 为根结点的树。
2）空树
当 n=0，也就是 0 个结点的情况也是树，它被称为空树。
3）子树
树的定义用到了递归的思想。即树的定义中还是用到了树的概念，如图所示，T1 和 T2 就是结点 a 的子树。结点 d、g、h、i 组成的树又是结点 b 的子树等等。
子树的个数没有限制，但是它们一定是互不相交的，如下图所示的就不是树。因为在这两个图中，a 的子树都有相交的边。
2、结点的定义
树的结点包含一个 数据域 和 m 个 指针域 用来指向它的子树。结点的种类分为：根结点、叶子结点、内部结点。结点拥有子树的个数被称为 结点的度。树中各个结点度的最大值被称为 树的度。
1）根结点
一棵树的根结点只有一个。
2）叶子结点
度为 0 的结点被称为 叶子结点 或者 终端结点。叶子结点的不指向任何子树。
3）内部结点
除了根结点和叶子结点以外的结点，被称为内部结点。
如上图所示，红色结点 为根结点，蓝色结点 为内部结点，黄色结点 为叶子结点。
3、结点间关系
1）孩子结点
对于某个结点，它的子树的根结点，被称为该结点的 孩子结点。
如上图所示，黄色结点 d 是 红色结点 b 的孩子结点。
2）父结点
而该结点被称为孩子结点的 父结点。
如上图所示，蓝色结点 a 是 红色结点 b 的父结点。
3）兄弟结点
同一父结点下的孩子结点，互相称为 兄弟结点。
如上图所示，绿色结点 c 和 红色结点 b 互为兄弟结点。
4、树的深度
结点的层次从根结点开始记为第 1 层，如果某结点在第 i 层，则它的子树的根结点就在第i+1 层，树中结点的最大层次称为 树的深度。
如下图所示，代表的是一棵深度为 4 的树。
5、森林的定义
森林是 m 棵 互不相交的树的集合，对于树的每个结点而言，其子树集合就是森林。
如图所示，b 和 c 两棵子树组成的集合就是一个森林。
二、二叉树的概念
1、二叉树的性质
二叉树是一种树，它有如下几个特征：
1）每个结点最多 2 棵子树，即每个结点的孩子结点个数为 0、1、2；
2）这两棵子树是有顺序的，分别叫：左子树 和 右子树；
3）如果只有一棵子树的情况，也需要区分顺序，如图所示：
b 为 a 的左子树；
c 为 a 的右子树；
数据结构——二叉树四种遍历的实现-2
