一、什么是树
树（Tree）是 n（n ≥ 0）个结点构成的有限集合。当 n=0 时，称为 空树。对于任一棵 非空树（n > 0），它具备以下性质：
- 树中有一个称为“根（Root）”的特殊结点，用 r 表示；
- 其余结点可分为 m（m > 0）个 互不相交的 有限集 \(T_{1}\)，\(T_{2}\)，……，\(T_{m}\)，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”；
子树是不相交的；
除了根节点外，每个结点有且只有一个父节点；
一颗 N 个结点的树有 N-1 条边；
二、树的常用术语
- 结点的度（Degree）：结点的子树个数；
- 树的度：树的所有结点中最大的度数；
- 叶结点（Leaf）：度为 0 的结点；
- 父结点（Parent）：有子树的结点是其子树的根节点的父节点；
- 子结点（Child）：若 A结点 是 B结点 的父节点，则称 B结点 是 A结点的子节点；子节点也称 孩子结点；
- 兄弟结点（Sibling）：具有同一父节点的各结点彼此是兄弟结点；
- 路径和路径长度：从结点 \(n_{1}\) 到 \(n_{k}\) 的路径为一个结点序列 \(n_{1}\)，\(n_{2}\)，……，\(n_{k}\)，\(n_{i}\) 是 \(n_{i+1}\) 的父节点。路径所包含边的个数为 路径的长度；
- 祖先结点（Ancestor）：沿 树根到某一结点路径 上的所有结点都是这个结点的 祖先结点；
- 子孙结点（Descendant）：某一结点的 子树中的所有结点 就是这个结点的子孙。
- 结点的层次（Level）：规定 根节点在 1 层，其它任一结点的层数是其父节点的层数加 1；
- 树的深度（Depth）：树中所有结点的 最大层次 是这棵树的深度。
三、树的表示方法
树一般我们采用 儿子—兄弟表示法，即一个结点有两个指针域，一个指向它的子节点，另一个指向它的兄弟结点。
用儿子—兄弟表示法的树旋转 45° 可以看成 二叉树；
四、集合的表示
我们可以用 树结构 表示集合，树的每个结点代表一个集合元素。例如，有三个整数集合，S1 = {1,2,4,7}，S2 = {3,5,8}，S3={6,9,10}，它们的表示方法如下：
双亲表示法：孩子指向双亲；
我们可以采用数组存储形式，数组中每个元素的类型描述为：
typedef struct
{
ElementType Data;
int Parent;
}SetType;
五、集合运算
【1】、查找某个元素所在的集合（用根结点表示）
在数组 S 中查找值为 X 的元素所属的集合。MaxSize 是全局变量，为数组 S 的最大长度。
int Find(SetType s[], ElementType X)
{
int i;
for(i = 0; i < MaxSize && S[i].Data != X; i++);
if(i >= MaxSize)
{
return -1; // 未找到，返回-1
}
for(; S[i].Parent >= 0; i = S[i].Parent);
return i; // 找到X所属集合，返回树根结点在数组S中的下标
}
【2】、集合的并运算
分别找到 X1 和 X2 两个元素所在集合树的 根节点，如果它们不同根，则将其中的 一个根节点的父节点指针设置为另一个根节点的数组下标。
viud Unino(SetType S[],ElementType X1,ElementType X2)
{
int Root1,Root2;
Root1 = Find(S,X1);
Root2 = Find(S,X2);
if(Root1 != Root2)
{
S[Root2].parent = Root1;
}
}
为了改善合并以后的查找性能，可以采用小的集合合并到相对大的集合中。