数据结构--树（3）

数据结构基础（13）

–树

树的存储结构

• 树是 n（n≥0）个结点的有限集合，n = 0 时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：

1. 有且仅有一个特定的称为根的结点。
2. 当 n > 1 时，其余结点可分为 m（m > 0）个互不相交的有限集合$T_1,T_2,...,T_m$，其中每个集合本身又是一棵树，并且称为根结点的子树。

• 树是一种递归定义的数据结构

二叉树：一个分支结点最多只能有两棵子树
树：一个分支结点可以有多棵子树

• 二叉树的顺序存储：

按照完全二叉树中的结点顺序，将各结点存储到数组的对应位置。数组下标反映结点之间的逻辑关系

• 树：一个分支结点可以有多棵子树

只依靠数组下标，无法反映结点之间的逻辑关系

解决思路：

用数组顺序存储各个结点。每个结点中保存数据元素、指向双亲结点（父节点）的 “指针”

根节点的双亲指针 = -1

非根节点的双亲指针 = 父节点在数组中的下标

树的存储方式1：双亲表示法（顺序存储）

• 根节点的双亲指针 = -1
• 非根节点的双亲指针 = 父节点在数组中的下标

#define MAX_TREE_SIZE 100  //树中最多结点数
typedef struct{             //树的结点定义
    ElemType data;         //数据元素
    int parent;            //双亲位置域
}PTNode;
typedef struct{             //树的类型定义
    PTNode nodes[MAX_TREE_SIZE]; //双亲表示
    int n;                 //结点数，结点总数n=11 
}PTree;

• 森林：森林是$ m（m \geq 0） $棵互不相交的树的集合,同理，森林也可以用这个方法来存储

这个双亲表示法的优缺点：

优点：找双亲（父节点）很方便

缺点：找孩子不方便，只能从头到尾遍历整个数组

• 适用于 “找父亲” 多，“找孩子” 少的应用场景。如：并查集

树的存储方式2：孩子表示法

孩子表示法：

• 用数组顺序存储各个结点。每个结点中保存数据元素、孩子链表头指针
• 用一个链表记录一个结点的孩子编号

方法：顺序存储 + 链式存储

struct CTNode {
    int child;  //孩子结点在数组中的位置
    struct CTNode *next;  //下一个孩子
};

typedef struct {
    ElemType data;
    struct CTNode *firstChild;  //第一个孩子
} CTBox;

typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r;  //结点数和根的位置，结点总数n=11，根的位置r=0 
} CTree;

• 森林：森林是$ m（m \geq 0） $棵互不相交的树的集合,同理，森林也可以用这个方法来存储
• 注意：用孩子表示法存储森林，需要记录多个根的位置

孩子表示法的优缺点：

优点：找孩子很方便
缺点：找双亲（父节点）不方便，只能遍历每个链表

树的存储方式3：孩子兄弟表示法

树的存储：

//树的存储—孩子兄弟表示法
typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild,  *nextsibling;  //指向第一个孩子和右边一个兄弟
 
}CSNode,*CSTree;

二叉树的存储：

//二叉树的结点（链式存储）
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild;  //左子树
    struct BiTNode *rchild;  //右子树
}BiTNode,*BiTree;

• 树的孩子兄弟表示法，与二叉树类似，采用二叉链表实现。每个结点内保存数据元素和两个指针，但两个指针的含义与二叉树结点不同

• 森林：森林是$ m（m \geq 0） $棵互不相交的树的集合,同理，森林也可以用这个方法来存储

• 森林中每棵树的根节点视为平级的兄弟关系

树转二叉树

• 使用方法：孩子兄弟表示法

• 树→二叉树 转换技巧：

1. 先在二叉树中，画一个根节点。
2. 按 “树的层序” 依次处理每个结点。

处理一个结点的方法是：如果当前处理的结点在树中有孩子，就把所有孩子结点 “用右指针串成糖葫芦”，并在二叉树中把第一个孩子挂在当前结点的左指针下方

例如：

• 树

• 二叉树

森林转二叉树

方法与树转二叉树一样，不过需要注意的是：

• 森林中各棵树的根节点视为平级的兄弟关系

二叉树转树

• 二叉树→树 转换技巧：

1. 先画出树的根节点
2. 从树的根节点开始，按 “树的层序” 恢复每个结点的孩子

如何恢复一个结点的孩子：在二叉树中，如果当前处理的结点有左孩子，就把左孩子和 “一整串右指针糖葫芦” 拆下来，按顺序挂在当前结点的下方

• 二叉树

• 树

二叉树转森林

方法与二叉树转树的差不多，不同的是：

• 先把二叉树的根节点和“一整串右指针糖葫芦”拆下来，作为多棵树的根节点
• 森林中各棵树的根节点视为平级兄弟

树的先根遍历

遍历： A B E K F C G D H I J

//树的先根遍历
void PreOrder(TreeNode *R){
    if (R!=NULL){
        visit(R);  //访问根节点
        while(R还有下一个子树T)
            PreOrder(T);  //先根遍历下一棵子树
    }
}

• 树的先根遍历序列与这课树相应二叉树的先序序列相同

树的后根遍历：

遍历：K E F B G C H I J D A

//树的后根遍历
void PostOrder(TreeNode *R){
    if (R!=NULL){
        while(R还有下一个子树T)
            PostOrder(T);  //后根遍历下一棵子树
        visit(R);  //访问根节点
    }
}

• 树的后根遍历序列与这棵树相应二叉树的中序序列相同

树的层次遍历

层次遍历（用队列实现）

1. 若树非空，则根节点入队
2. 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
3. 重复步骤2直到队列为空

森林的先序遍历

• 森林：森林是$m（m\ge 0）$棵互不相交的树的集合。每棵树去掉根节点后，其各个子树又组成森林。

• 先序遍历森林

若森林为非空，则按如下规则进行遍历：

1. 访问森林中第一棵树的根结点。
2. 先序遍历第一棵树中根结点的子树森林。
3. 先序遍历除去第一棵树之后剩余的树构成的森林。

其效果等同于依次对各个树进行先根遍历

遍历： B E K L F C G D H M I J

方法二：也可以将其转化为二叉树，其效果等同于依次对二叉树的先序遍历

森林的中序遍历

• 中序遍历森林。

• 若森林为非空，则按如下规则进行遍历：

1. 中序遍历森林中第一棵树的根结点的子树森林。
2. 访问第一棵树的根结点。
3. 中序遍历除去第一棵树之后剩余的树构成的森林。

效果等同于依次对各个树进行后根遍历

遍历： K L E F B G C M H I J D

方法二：也可以将其转化为二叉树，其效果等同于依次对二叉树的中序遍历

–哈夫曼树 + 并查集

带权路劲长度

• 结点的权：有某种现实含义是数值（如：表示结点的重要性等）

• 结点的带权路劲长度：从树的根到该结点的路劲长度（经过的边数）与该结点上权值的乘积

以右下角为例 则为; 3 * 3 = 9

• 树的带权路劲长度：树中所有叶结点的带权路劲长度之和（WPL,Weighted Path Length）

$$\mathrm{WPL}=\sum _{i=1}^n{w}_i{l}_i$$

例如：

WPL = 1 * 5 + 2 * 4 + 3 * 1 + 3 * 3 = 25

哈夫曼树的定义：

在含有 n 个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树

哈夫曼树的构造

1. 给定 n 个权值分别为($w_1$, $w_2$, …,$ w_n$)的结点，构造哈夫曼树的算法描述如下：
2. 将这 n 个结点分别作为 n 棵仅含一个结点的二叉树，构成森林 F。
3. 构造一个新结点，从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
4. 从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中。
5. 重复步骤 2 和 3，直至 F 中只剩下一棵树为止。

哈夫曼树的性质

1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
2. 哈夫曼树的结点总数为 2n - 1
3. 哈夫曼树中不存在度为 1 的结点。
4. 哈夫曼树并不唯一，但 WPL 必然相同且为最优

哈夫曼编码

• 固定长度编码–每个字符用相等长度的二进制位表示

例如：ASCLL编码 / 每个字符用长度为2的二进制表示

• 可变长度编码

允许对不同字符用不等长的二进制表示

• 若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码

• 有哈夫曼树得到哈夫曼编码 —— 字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树

哈夫曼编码可以用来数据的压缩

并查集

• Q : 如何 “查” 到一个元素到底属于哪一个集合
  A : 从指定元素出发，一路向北，找到根节点

• Q : 如何判断两个元素是否属于同一个集合？

  A : 分别查到两个元素的根，判断根节点是否相同即可

• Q :如何把两个集合 “并” 为一个集合？

  A : 让一棵树成为另一棵树的子树即可

集合的两个基本操作 ——“并” 和 “查”

Find ——“查” 操作：确定一个指定元素所属集合

Union ——“并” 操作：将两个不相交的集合合并为一个

P S: 并查集（Disjoint Set）是逻辑结构 —— 集合的一种具体实现，只进行 “并” 和 “查” 两种基本操作

基本操作

#define SIZE 13
int UFSets[SIZE];  //集合元素数组

//初始化并查集
void Initial(int S[]){
    for(int i=0;i<SIZE;i++)
        S[i]=-1;
}

//Find“查”操作，找x所属集合（返回x所属根结点）
int Find(int S[],int x){
    while(S[x]>=0)      //循环寻找x的根
        x=S[x];
    return x;           //根的S[]小于0
}

//Union“并”操作，将两个集合合并为一个
void Union(int S[],int Root1,int Root2){
    //要求Root1与Root2是不同的集合
    if(Root1==Root2) return;
    //将根Root2连接到另一根Root1下面
    S[Root2]=Root1;
}

Find“查”操作的最坏时间复杂度；O(n)

Union“并”操作的时间复杂度 ：O(1)

Union“并”操作的优化

优化思路：在每次 Union 操作构建树的时候，尽可能让树不长高高

1. 用根节点的绝对值表示树的结点总数
2. Union 操作，让小树合并到大树

优化的代码

//Union “并”操作，小树合并到大树
void Union(int S[], int Root1, int Root2) {
    if (Root1 == Root2) return;
    if (S[Root2] > S[Root1]) {  //Root2结点数更少
        S[Root1] += S[Root2];  //累加结点总数
        S[Root2] = Root1;      //小树合并到大树
    } else {
        S[Root2] += S[Root1];  //累加结点总数
        S[Root1] = Root2;      //小树合并到大树
    }
}

Union 操作优化后，该方法构造的树高不超过 $\lfloor {\log }_{2}n\rfloor +1$,Find 操作最坏时间复杂度：$O(lo{g}_{₂}n)$

Find“查”操作的优化

压缩路径–Find“查”操作，先找到根节点，再将查找路径上所有结点都挂到根结点下

//Find “查”操作优化，先找到根节点，再进行“压缩路径”
int Find(int S[],int x){
    int root = x;
    while(S[root]>=0)   root=S[root];  //循环找到根
    while(x!=root){     //压缩路径
        int t=S[x];     //t指向x的父节点
        S[x]=root;      //x直接挂到根节点下
        x=t;
    }
    return root;        //返回根节点编号
}

每次 Find 操作，先找根，再 “压缩路径”，可使树的高度不超过$O(\alpha (n))$。$(\alpha (n)$是一个增长很缓慢的函数，对于常见的n值，通常$\alpha (n)\le 4$，因此优化后并查集的 Find、Union 操作时间开销都很低

核心思想：让尽可能的矮