一、树是n个节点的有限集。
子树,树的结构定义是一个递归的定义，在树的定义中又用到了树的概念。
一般来说，分等级的分类方案都可以用层次结构来表示，也就是说，都可导致一个树结构。
树的结点包含一个数据元素及若干指向其子树的分支。
结点拥有的子树数量称为结点的度(degree)。
度为0的结点称为叶子结点(leaf)或终端结点.
度不为0的结点称为非终端结点或分支结点。
树的度是树内各结点度的最大值。
结点的子树的根称为孩子结点的孩子child,该结点称为孩子的双亲parent.
同一个双亲之前的孩子之间互称为兄弟。
双亲在同一层的结点互为堂兄弟。
结点的层次level是从根开始定义，根为第一层，根的孩子为第二层。
树中根结点最大的层次称为树的深度depth。
如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树.
森林是m棵互不相交的树的集合，对树中每个结点而言，其子树的集合就是森林。
二、二叉树
1. 二叉树：每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
2. 二叉树有3个性质
a. 在二叉树的第i层上至多有2的i-1方个结点
b. 深度为k的二叉树最多有2的k次方-1个结点
c. 对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1
3. 一个深度为k且有2的k次方-1个结点的二叉树称为满二叉树
4. 深度为k，有n个结点的二叉树，当且仅当其每一个即结点都与深度为k的满二叉树中编号从1至n的结点意义对应时，称为完全二叉树
5. 具有n个结点的完全二叉树的深度为[log2n]+1
三、二叉树的存储结构
1. 顺序存储结构：2的k次方-1的一维数组
2. 链式存储结构:
a. data，lchild,rchild, parent(可选，线索链表), 空链域
b. data, firstchild,nextsibling 兄弟链
3. 遍历二叉树:
a. 前序遍历, 第一根结点，可以采用递归的方法，也可以采用栈实现
b. 中序遍历, 中间根结点，可以采用递归的方法，也可以采用栈实现
c. 后序遍历, 最后根结点，可以采用递归的方法，也可以采用栈实现
d. 层序遍历, 从上到下，从左到右，可以采用队列的方式
4. 线索二叉树
data,lchild左子树,rchild右子树,ltag前驱,rtag后继
线索链表，线索，线索二叉树
四、树和森林
1. 树的存储结构,3种常用的链表结构
a. 双亲表示法，data,parent
b. 孩子表示法, child,next
c. 孩子兄弟表示法,firstchild,nextsibling
2. 森林与二叉树的转换
3. 树和森林的遍历
a. 先序遍历
b. 中序遍历
五、树与等价问题
六、赫夫曼(Huffman)树
1. 最优二叉树（赫夫曼树),树路径长度，树的带权路径长度
2. 构造一个huffman树的方法,最小的右子树
3. 应用：
a.成绩等级划分比较
b.huffman编码，前缀编码
七、回溯法与树的遍历
试探或回溯的搜索技术求解问题。
1. 求含n个元素的集合的幂集
2. 求8皇后问题的所有合法布局
八、树的计数
1. 根据前序遍历和中序遍历可以构造一棵二叉树