数据结构 408-5-4&5 - 数据结构 - 计算机科学 | Flüstern = Whispering's Blog = 无需过去，无关未来，只有现在

# 树的存储结构

# 双亲表示法 (顺序存储)

双亲表示法：每个结点中保存指向双亲的指针

根节点固定存储在 0，-1 表示没有双亲

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

新增数据元素，无需按逻辑上的次序存储

优点：查指定结点的双亲很方便

缺点：查指定的孩子只能从头遍历

空数据导致遍历更慢

# 孩子表示法 (顺序 + 链式存储)

孩子表示法：顺序存储各个节点，每个节点中保存孩子链表头指针

struct CTNode{
    int child; //孩子节点在数据中的位置
    struct CTNode *next; //下一个孩子
};
typedef struct {
    ElemType data;
    struct CTNode *firstChild; //第一个孩子
} CTBox;
typedef struct {
    CTBox nodes[MAX_TREES_SIZE];
    int n,r; //结点数和根的位置
} CTree;

# 孩子兄弟表示法 (链式存储)

typedef struct CSNode{
    ElemType data; //数据域
    struct CSNode *firstchild,*nextsibling; //第一个孩子和右兄弟指针
}CSNode,*CSTree;

树与二叉树相互转化

优点：可以用我们熟悉的二叉树操作来处理树

# 森林和二叉树的相互转换

森林。森林是 m (m>=0) 棵互不相同的树的集合

本质：用二叉链表存储森林

# 树和森林的遍历

# 树的遍历

# 先根遍历

先根遍历：若树非空，先访问根节点，再依次对每棵子树进行先根遍历

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

树的先根遍历序列与这棵树对应的二叉树的先序序列相同

# 后根遍历

后根遍历：若树非空，先依次对每棵子树进行后根遍历，最后再访问根节点

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

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

# 层序遍历

层序遍历 (用队列实现)（广度优先遍历）：

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

# 森林的遍历

# 森林的先序遍历

先序遍历森林：

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

访问第一棵树的根节点
先序遍历第一棵树中根节点的子树森林
先序遍历除去第一课树之后剩余的树构成的森林

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

# 森林的中序遍历

中序遍历森林：

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

中序遍历第一棵树中根节点的子树森林
访问第一棵树的根节点
中序遍历除去第一课树之后剩余的树构成的森林

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

# 哈夫曼树

# 带权路径长度

结点的权：由某种现实含义的数值 (如：表示结点的重要性等)

结点的带权路径长度：从树的根到结点的路径长度 (经过的边数) 与结点上权值的乘积 (比如一个在第三层的节点权值为 4，则长度为 12)

树的带权路径长度：树中所有叶节点的带权路径长度之和

# 哈夫曼树定义

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

# 哈夫曼树构造

给定 n 个分别为 $w_1,w_2,...,w_n$ 的结点，构造哈夫曼树的算法描述如下：

将这 n 个结点分别作为 n 棵仅含一个结点的二叉树，构成森林 F
构造一个新节点，从 F 中选取两棵根节点最小的树作为新节点的左、右子树，并将新结点的权值置为左、右子树上根节点的权值之和
从 F 中删除刚才选出的两个数，同时将新得到的树加入 F 中
重复第二步和第三步，直至 F 中只剩下一棵树为止

1、每个初始结点最终都成为叶节点，且权值越小的结点到根结点的路径长度越大

2、哈夫曼树的结点总数为 2n-1

3、哈夫曼树中不存在度为 1 的节点

4、哈夫曼树并不唯一，但带权路径长度之和必然相同且为最优

# 哈夫曼编码

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

可变长编码 —— 允许对不同字符用不等长的二进制位表示

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

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

# 并查集

逻辑结构：集合

查一个元素属于哪一个集合：从指定元素出发，一路向上，找到根节点

判断两个元素是否属于同一个集合：分别查两个元素的根，判断根节点是否相同

如何合并两个集合：让一棵树称为另一棵树的子树即可

并查集存储结构：用一个数组即可表示集合关系

集合基本操作：

Find—— 查操作：确定一个指定元素所属集合
Union—— 并操作：将两个不相交的集合合并为一个

注意：并查集是逻辑结构 —— 集合的一种具体结构，只进行并和查两种基本操作

#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];
}

若结点数为 n，Find 最坏时间复杂度为 O (n)

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

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

//Union 改进版
void Union(int S[],int Root1,int Root2){
    if(Root1==Root2)
        return;
    if(S[Root1]>S[Root2]){
        S[Root1]+=S[Root2];
        S[Root2]=Root1;
    } else {
        S[Root2]+=S[Root1];
        S[Root1]=Root2;
    }
}

优化之后，Find 最坏时间复杂度为 O (logn)

# 进一步优化

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指向父节点
        S[x]=root;    //x直接挂到根结点下
        x=t;
    }
    return root;     //返回根节点编号
}

数据结构考研408