1.树
1.1 树的基本概念
（1）树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。
（2）我们可以形式的给出树的递归定义如下：
树是n（n>=0)个结点的有限集。它
①或者是一棵空树(n = 0),空树中不包含任何结点
②或者是一棵非空树(n>0),此时有且仅有一个特定的称为根的结点
当n>1时，其余结点可分为m(m > 0)个互不相交的有限集T1,T2,…,Tm,
其中每一个本身又是一棵树，并且称为根的子树
1.2结点的度与树的度
（1）结点拥有的子树的数目称为结点的度
（2）度为0的结点称为叶子或终端结点
（3）度不为0的结点称为非终端结点或分支结点。除根之外的分支结点也称为内部结点
（4）树内各结点的度的最大值称为树的度
1.3 结点的层次和树的深度
（1）结点的层次从根开始定义，层次数为1的结点是根结点，其子树的根的层次数为2；
（2）树中结点的最大层次数称为树的深度或高度
（3）父亲、儿子、兄弟
①父亲：一个结点的直接前驱结点
②儿子：一个结点的直接后继结点
③兄弟：同一个父亲结点的其他结点
结点A是结点B、C、D的父亲，结点B、C、D是结点A的儿子。由于结点H、I、J有同一个父节点D,因此它们称为兄弟。
（4）祖先、子孙、堂兄弟
①结点的祖先是从根到该结点路径上的所有结点
②以某结点为根的树中的任一结点都称为该结点的子孙
③父亲在同一层次的结点互为堂兄弟
（5）有序树、m叉树、森林
2.二叉树
2.1二叉树的定义
（1）每个结点的度均不超过2的有序树，称为二叉树
（2）二叉树的递归定义如下：
二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称为根的左子树和右子树的子树所组成的非空树
2.2 满二叉树和完全二叉树
（1）满二叉树：高度为k并且有2k+1-1个结点的二叉树。在满二叉树中，每层结点都达到最大数，即每层结点都是满的，因此称为满二叉树
（2）完全二叉树：若在一棵满二叉树中，在最下层从最右侧起去掉相邻的若干叶子结点，得到的二叉树即为完全二叉树
注意：满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树
2.3 二叉树的存储结构
（1）顺序存储结构
对于满二叉树和完全二叉树来说，可以将其数据元素逐层存放到一组连续的存储单元中
（2）链式存储结构
设计不同的结点结构可构成不同的链式存储结构。在二叉树中每个结点都有两个孩子，则可以设计每个结点至少3个域：数据域、左孩子域和右孩子域。数据域存放数据元素，左孩子域存放指向左孩子结点的指针，右孩子域存放指向右孩子结点的指针。如下图所示，利用此结点得到的二叉树存储结构称为二叉链表。
注意：为了方便找到父结点，可以在上述结点结构中新增一个指针域，指向结点的父结点。
3.二叉树的实现
3.1二叉树的遍历
遍历就是按照某种次序访问树中的所有结点，且每个结点恰好访问一次。
注意：由于树的递归定义，其实对三种遍历的概念其实也是一个递归的描述过程
注意：层次遍历是非递归
