1.树的基本概念
1.树的定义
树是由n(n>=0)个结点（或元素）组成的有限集合（记为T）。
如果n=0,它是一棵空树，这是树的特例。
如果n>0，这个结点中有且仅有一个结点作为树的根结点，简称为根。其余结点可分为m个互不相交的有限集T1,T2......Tm，其中每个子集本身又是一棵符合本定义的树，称为根结点的子树。
2.树的逻辑表示方法
（1）.树形表示法：用一个圆圈表示一个结点，圆圈内的符号代表该结点的数据信息，结点之间的关系通过分支线标识，其方向隐含着从上向下，即分支线的上方结点是下方结点的前驱结点，下方结点是上方结点的后继结点。
（2）文氏表示法：每棵树对应一个圆圈，圆圈内包含根结点和子树的圆圈，同一个根结点的各子树的圆圈不能相交。
（3）凹入表示法
（4）括号表示法
3.树的基本术语
（1）结点的度与树的度：树中某个结点的子树的个数称为该结点的度，书中所有节点的度中最大值称为树的度，通常将度为m的数称为m次树。
（2）分支结点与叶子结点：树中度不为0的结点称为分支结点，度为0的结点称为叶子结点。对于度为1的结点，其分支树为1，被称为单分支结点。对于度为2的结点，其分支树为2，被称为双分支结点。以此类推。
（4）路径与路径长度：从结点i到结点j的一条路径，路径长度等于从i到j经过的所有结点数减1.
（5）孩子结点，双亲结点和兄弟结点：在一棵树中，每个结点的后继结点称为该结点的孩子结点，相应的，该节点被称为孩子结点的双亲结点，具有同一个双亲结点的孩子互为兄弟结点。
（6）结点层次与树的高度：结点层次或结点深度是一根结点为第一层，孩子结点为第二层，以此类推，树中结点的最大层次称为树的高度或树的深度。
（7）有序数和无序树：树中各结点按照一定的次序从左到右安排，且相对次序不能随意变化，则称为有序数，否则为无序树。
（8）森林：m棵互不相交的数的集合称为森林。
4.树的性质
1.树中的结点数等于所有结点的度数之和加1.
2.度为m的树中第i层上最多有m^(i-1)个结点。
3.高度为h的m次树最多有（m^h-1）/(m-1)个结点。（该结果由等比数列求和可得）
4.具有n个结点的m次树的最小高度为
。
5.树的存储结构
1.双亲存储结构
：是一种顺序存储结构，用一组连续空间存储树的所有结点，同时在每个结点中附设一个伪指针指示其双亲结点的位置。
typedef struct
{
ELemType data; //存放结点的值
int parent; //存放双亲的位置
}PTree[MaxSize]; //PTree双亲存储结构类型
缺点：该方法找一个结点的双亲结点十分容易，但是找其孩子结点时需要遍历整个存储结构。
2.孩子链存储结构
typedef struct
{
ELemType data; //结点的值
struct node* sons[MaxSons]; //指向孩子结点
}TSonNode; //孩子链存储结构中的结点类型缺点：查找某个结点的双亲结点需要遍历树，当树的度较大时存在较多的空指针域，浪费空间。
3.孩子兄弟存储结构
typedef struct tnode
{
ELemType data; //结点的值
struct tnode* hp; //指向兄弟
struct tnode* vp; //指向孩子结点
}TSBNode; //孩子兄弟存储结构的结点类型缺点： 查找一个结点的双亲结点需要遍历树。