前面几节分析了表的数据结构以及算法，包括顺序表、链表、hash表以及栈和队列。后面的几节我们讲开始分析树。
1.树的定义
什么是树呢？我们看一下百度百科给的定义：
树是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
一般这种定义都不是人话，我们用图说话大家更容易懂。
树有以下特点：
1.每个节点有零个或多个子节点；
2.没有父节点的节点称为根节点；
3.每一个非根节点有且只有一个父节点；
4.除了根节点外，每个子节点可以分为多个不相交的子树；
2.节点的度
结点拥有的子树数称为结点的度。度为0的结点称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。除根结点以外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。
从上图可以看出这棵树的度是3。
3.层次和深度
结点的层次从根开始定义，根为第一层，根的孩子为第二层。若某结点在第n层，则其子树的根就在第n+1层。双亲在同一层的结点称为堂兄弟。在下图中，D和E、F是堂兄弟。树中结点的最大的层次成为树的深度或者是高度。下图中树的深度为4。
4.树林
树林是指m（m>=0）棵互不相交的树的集合。
5.树的存储结构
通过上面的分析，显然简单的顺序存储结构是难以满足树的实现的。树的存储应该结合顺序存储以及链式存储来完成。
6.常见的几种树的表示方法
双亲表示法：
孩子表示法：
孩子双亲表示法：
把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中。如下图所示：
孩子兄弟表示法：
孩子兄弟表示法为每个节点设计三个域：
一个数据域，一个该节点的第一个孩子节点域，一个该节点的下一个节点的兄弟指针域。如下图所示：
7.二叉树
前面大概分析了一下树的定义及其存储结构，下面我们来介绍一种特殊的树：二叉树。
7.1 二叉树的定义：在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
7.2 斜树
定义：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。
7.3 满二叉树
在一颗二叉树中，如果所有的分支节点都存在左子树和右子树，并且所有的叶子豆子啊同一层上，这样的二叉树就称为满二叉树。
7.4 完全二叉树
对一棵具有n个结点的二叉树按层序编号，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树，如下图所示：
7.5 二叉树的一些特点：
1.在二叉树的第i层上至多有2i-1个结点（i>=1）
2.深度为k的二叉树至多有2k-1个结点（k>=1）
3.对任何一颗二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则n0 = n2+1
4.具有n个结点的完全二叉树深度为[log2n]+1 ([x]表示不 大于 x的最大整数)
5.如果对一颗有n个结点的完全二叉树（其深度为[log2n]+1） 的结点按层序编号（从第1层到第[log2n]+1层，每层从左到 右），对任意一个结点i(1<=i<=n)有：
1）.如果i=1,则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结 点[i/2]
2）.如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩 子是结点2i。
3）.如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1
7.6 二叉树的顺序存储
如图所示，当二叉树为完全二叉树时，只需要按照从上往下以及从左往右的顺序存储即可，而当为普通的二叉树时，则需要将无数据的结点按照完全二叉树的顺序存储方式置空就行。当然，这样会浪费很多内存，但相应的也能提高效率。
7.7 二叉树的链式存储结构
7.8 二叉树的遍历
前序遍历：规则是若二叉树为空，则空操作返回，否则先访问跟结点，然后前序遍历左子树，再前序遍历右子树，如图所示：
中序遍历：规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如图所示：
后序遍历：规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如图所示：
7.9 二叉排序树
定义： 或者是一颗空树，或者是一颗具有如下性质的树：
1）若左子树不为空，那么左子树上面的所有节点的关键字值都比根节点的关键字值小
2）若右子树不为空，那么右子树上面的所有节点的关键字值都比根节点的关键字值大
3）左右子树都为二叉树
今天就先分析到这里，下节我们从代码角度来实现二叉树的增删改查。
