阿里云网站 模板建设,开展网络营销推广方案,开发公司设置部门,html大屏展示模板5.5 树与二叉树的应用
5.5.1 哈夫曼树
结点的权#xff1a;有某种现实含义的数值。
结点的带权路径长度#xff1a;从树的根到该结点的路径长度#xff08;经过的边数#xff09;与该结点上权值的乘积。
树的带权路径长度#xff1a;树中所有叶结点的带权路径长度之和…5.5 树与二叉树的应用
5.5.1 哈夫曼树
结点的权有某种现实含义的数值。
结点的带权路径长度从树的根到该结点的路径长度经过的边数与该结点上权值的乘积。
树的带权路径长度树中所有叶结点的带权路径长度之和WPLWeighted Path Length 哈夫曼树的定义在含有 n 个带权叶结点的二叉树中其中带权路径长度WPL最小的二叉树称为哈夫曼树也称最优二叉树
哈夫曼树的构造 给定n个权值分别为w1, w2,..., wn的结点构造哈夫曼树的算法描述如下: 1) 将这n个结点分别作为n棵仅含一个结点的二叉树构成森林F. 2) 构造一个新结点从F中选取两棵根结点权值最小的树作为新结点的左、右子树并且将新结点的权值置为左、右子树上根结点的权值之和。 3) 从F中删除刚才选出的两棵树同时将新得到的树加入F中。 4) 重复步骤2和3直至F中只剩下一棵树为止。 哈夫曼树的性质 1) 每个初始结点最终都成为叶结点且权值越小的结点到根结点的路径长度越大。 2) 哈夫曼树的结点总数为 2n−1。 3) 哈夫曼树中不存在度为 1 的结点。 4) 哈夫曼树并不唯一但 WPL 必然相同且为最优。哈夫曼编码 固定长度编码――每个字符用相等长度的二进制位表示 可变长度编码――允许对不同字符用不等长的二进制位表示 若没有一个编码是另一个编码的前缀则称这样的编码为前缀编码
有哈夫曼树得到哈夫曼编码――字符集中的每个字符作为一个叶子结点各个字符出现的频度作为结点的权值根据之前介绍的方法构造哈夫曼树
哈夫曼编码可用于数据压缩
5.5.2_1 并查集
逻辑结构数据元素之间为“集合”关系
集合的两个基本操作——“并”和“查” Find ——“查”操作确定一个指定元 素所属集合 Union ——“并”操作将两个不想交 的集合合并为一个
注并查集Disjoint Set是逻辑结构——集合的一种具体实现只进行 “并”和“查”两种基本操作“并查集”的存储结构“并查集”的代码实现——初始化
#define SIZE 13
int uFsets [ SIZE]; //集合元素数组
//初始化并查集
void Initial (int S[]){for(int i0;iSIZE;i)s[i]-1;
}
“并查集”的代码实现——并、查
//Find“查”操作找x所属集合(返回x所属根结点)
int Find (int S[],int x){while(S[x]0) //循环寻找x的根xS[x] ;return x; //根的s[]小于0
)// union“并”操作将两个集合合并为一个
void union(int S[],int Root1,int Root2){//要求Root1与Root2是不同的集合if(Root1Root2)return;//将根Root2连接到另一根Root1下面S[Root2]Root1; Union操作的优化 优化思路在每次Union操作构建树的时候尽可能让树不长高 ①用根节点的绝对值表示树的结点总数 ②Union操作让小树合并到大树
// Union“并”操作小树合并到大树
void Union (int S[],int Root1,int Root2 ){if(Root1Root2 ) return;if(S[Root2]S[Root1]) { //Root2结点数更少S[Root1]S[Root2]; //累加结点总数S[Root2]Root1; //小树合并到大树}else{S[Root2]S[Root1]; //累加结点总数S[Root1]Root2; //小树合并到大树}
} 5.5.2_2 并查集的进一步优化
拓展Find操作的优化(压缩路径) 先找到根结点再将查找路径上所有结点都挂到根结点下
//Find“查操作优化先找到根节点再进行“压缩路径”
int Find(int S[],int x){int root x;while(S[root]0) rootS[root]; //循环找到根while(x! root){ //压缩路径int tS[x]; //t指向x的父节点S[x]root; //x直接挂到根节点下xt;}
return root; //返回根节点编号
}
