什么是树

客观世界中许多事物存在层次结构

人类社会家谱
社会组织结构
图书信息管理

分层次组织在管理上具有更高的效率

树的定义

树(Tree)：n(n>=0)个结点构成的有限集合
当n=0时，称为空树
对于任一棵非空树(n>0)，它具备以下性质：

树中有一个称为“根(Root)”的特殊结点，用r表示
其余结点可分为m(m>0)个互不相交的有限集 $T_1,T_2,…,T_m$ $T_{1}, T_{2}, \dots, T_{m}$ ，其中每个集合本身又是一棵树
- 称为原来树的“子树(SubTree)”

树与非树

树的子树是不相交的
除了根结点外，每个结点有且仅有一个父节点
一棵N个结点的树有N-1条边(m棵树(森林)有k条边，则一共有k-m个结点)
树将所有结点连接在一起，随便去除哪一条边都会使树不连通
树是使结点连通的方式之中边最少的一种

树的一些基本术语

结点的度(Degree)：结点的子树个数
数的度：树中所有结点中最大的度数
叶结点(Leaf)：度为0的结点
父结点(Parent)：有子树的结点是其子树的根结点的父结点
子结点(Child)：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点
兄弟结点(Sibling)：具有同一父结点的各结点之间彼此是兄弟结点
路径和路径长度：从结点 $n_1$ $n_{1}$ 到 $n_k$ $n_{k}$ 的路径为一个结点序列 $n_1,n_2,…,n_k,n_i$ $n_{1}, n_{2}, \dots, n_{k}, n_{i}$ 是 $n_{i+1}$ $n_{i + 1}$ 的父结点
- 路径所包含边的个数为路径的长度
祖先结点(Ancestor)：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点
子孙结点(Descendant)：某一结点的子树中的所有结点是这个结点的子孙
结点的层次(Level)：规定根结点在1层，其他任一结点的层数是其父结点的层数加1
树的深度(Depth)：树中所有结点中的最大层次是这棵树的深度

树的表示

在使用树结构描述实际问题时，大多数不是二叉树，更多的是普通的树结构，在存储之间具有普通树结构的数据时，经常使用的方法有3种：

双亲表示法
- 数据域：Data和指针域：Parent
孩子表示法
- 以单链表作存储结构将每个孩子结点排列起来，则n个结点有n个孩子链表
孩子兄弟表示法
- 一个数据域和两个指针域
  - n个结点有2n个指针域，n-1条边，说明有n+1个指针域是空的
- Firstchild：第一个孩子结点
- NextSibling：相邻的兄弟结点
- 这种情况下，将整棵树旋转45度，得到的是一棵“二叉树”(度为2)

二叉树

分为数据域和指针域，指针分别指向两个孩子结点

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

对一般的树而言均可以用二叉树的形式实现，因此一般数的表示和操作实现其核心和基础就是二叉树的表示和实现
了解二叉树的实现和操作，实际上就解决了一般树的许多问题
二叉树的研究是在树结构的研究当中最重要的一部分

集合

集合的操作

集合运算：交、并、补、差，判定一个元素是否属于某一集合
并查集：用于处理一些集合合并、查某元素属于什么集合的问题(只关心两种运算)

集合存储

并查集问题中集合存储如何实现？
例：有十台电脑{1,2,3,4,5,6,7,8,9,10}，已知下列电脑之间实现了连接：
1和2，2和4，3和5，4和7，5和8，6和9，6和10，问2和7，5和9之间是否是连通的
解决思路：

将10台电脑看成10个集合{1},{2},{3}……{10}
已知一种连接“a和b”就是将a和b对应的集合合并
查询“a和b是否是连通的”就是判别a和b是否在同一集合
用树结构表示集合，数的每个结点代表一个集合元素，并且使用双亲表示法，可以找到结点所属的集合(根结点)

例如：有三个整数集合

$S_1={1,2,4,7},S_2={3,5,8},S_3={6,9,10}$ ;
可以采用双亲表示的树结构表示集合
- $S_1$ 的根结点为1，2、4、7为子结点， $S_2$ 的根结点为3，5、8为子结点， $S_3$ 的根结点为6，9、10为子结点
采用顺序存储的形式存储树(Parent域中负数表示根结点,非负数表示双亲结点的下标)
- 数组中元素描述为

typedef struct SetType
{
    ElementType Data;
    int Parent;
};

下标	Data	Parent
0	1	-1
1	2	0
2	3	-1
3	4	0
4	5	2
5	6	-1
6	7	0
7	8	2
8	9	5
9	10	5

集合运算

查找某个元素所在的集合(用根结点表示)

int Find(SetType S[],ElementType X)
//在数组S中查找值为X的元素所属的集合
//MaxSize是全局变量，为数组S的最大长度
{
    int i;
    for(i=0;i<MaxSize&&S[i].Data!=X;i++);       //在集合中找到X的下标
    if(i>=MaxSize)return -1;                    //未找到X，返回-1
    for(;S[i].Parent>=0;i=S[i].Parent);
    return i;                                   //找到X所属集合，返回树根结点在数组S中的下标
}

集合的并运算

分别找到X1和X2两个元素所在集合数的根结点
如果它们不同根，则将其中一个根结点的指针设置成另一个根结点的数组下标

void Union(SetType S[],ElemnetType X1,ElemnetType X2)
{
    int Root1,Root2;
    Root1=Find(S,X1),Root2=Find(S,X2);         //先找到X1和X2所在的集合
    if(Root1!=Root2)S[Root2].Parent=Root1;     //当X1和X2不属于同一子集时，才需要合并
}

为了改善合并以后的查找性能，可以采用小的集合合并到相对大的集合中
为达到这种效果，可以在根结点记录集合的元素个数(如集合有3个元素则根结点的Parent域的值为-3)

void ModifyRoot(SetType S[])
{
    int i;
    ElementType Leafs[MaxSize];
    for(i=0;i<MaxSize;i++)Leafs[i]=0;
    for(i=0;i<MaxSize;i++)if(S[i].Parent>=0)Leafs[S[i].Parent]++;
    for(i=0;i<MaxSize;i++)if(Leafs[i]>0)S[i]=-Leafs[i]-1;
}

改进后：

void Union(SetType S[],ElemnetType X1,ElemnetType X2)
{
    int Root1,Root2,MaxRoot;
    Root1=Find(S,X1),Root2=Find(S,X2);
    if(Root1!=Root2)
    {
        if(Root1.Parent>=Root2.Parent)
        {
            S[Root1].Parent=Root2;
            Root2+=Root1;
        }
        else 
        {
            S[Root2].Parent=Root1;
            Root1+=Root2;
        }
    }
}

同时可以看到，在集合结构的查找过程中需要遍历一个数组，效率较低，可以考虑进行简化表示

任何有限集合的N个元素都可以被一一映射为整数0～N-1，所以可以进一步进行改进
直接使用数组(直接以下标表示Data)就可以存储一个集合

集合的简化表示

typedef int ElementType;                     //默认元素可以用非负整数表示
typedef int SetName;                         //默认根结点的下标作为集合名称
typedef ElementType SetType[MaxSize];
查找元素
SetName Find(SetType S,ElementType X)        //默认集合元素全部初始化为-1
{
    for(;S[X]>=0;X=S[X]);
    return X;
}       
void Union(SetType S,SetName Root1,SetName Root2)  //这里默认Root1和Root2是不同集合的根结点
{
    S[Root2]=Root1;
}

并查集操作演示

/* 示例程序(浙江大学mooc数据结构) */
#define MAXN 1000                  /* 集合最大元素个数 */
typedef int ElementType;           /* 默认元素可以用非负整数表示 */
typedef int SetName;               /* 默认用根结点的下标作为集合名称 */
typedef ElementType SetType[MAXN]; /* 假设集合元素下标从0开始 */

void Union( SetType S, SetName Root1, SetName Root2 )
{ /* 这里默认Root1和Root2是不同集合的根结点 */
    /* 保证小集合并入大集合 */
    if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */
        S[Root2] += S[Root1];     /* 集合1并入集合2  */
        S[Root1] = Root2;
    }
    else {                         /* 如果集合1比较大 */
        S[Root1] += S[Root2];     /* 集合2并入集合1 */
        S[Root2] = Root1;
    }
}

SetName Find( SetType S, ElementType X )
{ /* 默认集合元素全部初始化为-1 */
    if ( S[X] < 0 ) /* 找到集合的根 */
        return X;
    else
        return S[X] = Find( S, S[X] ); /* 路径压缩 */
}