哈夫曼树和哈弗曼编码

一、ASCII码定长编码八位表示一个只用01表示不能进行压缩不出现的字母也要提前编码好变长编码提高传输效率可以压缩只针对于出现的字母进项编码哈夫曼编码也属于变长编码二、哈夫曼树1.定义带权路径长度 WPL最小的树为哈夫曼树2.专业名词解释路径和路径长度从根节点到任意节点所走过的路线 路线上班的数目节点的权节点的值带全路径长度从根节点到该节点之间的路径长度与该节点权值的乘积树的带权路径长度所有叶子结点带权路径长度之和WPL3. 性质• 完全二叉树不一定最优哈夫曼树是 正则二叉树只有度为 0 或 2 的结点。•权值越大的叶子离根越近。• 不唯一左右子树交换或同层相同权值互换可得到不同形态但 WPL 相同。4.哈夫曼树的构建权值越大离根结点越近权值越小离根结点越远已知权值 W {2,5,9,6,7},请构造哈夫曼树三、哈夫曼编码1. 定义定长编码ASCII 8 位浪费空间变长编码若设计不当会导致歧义。哈夫曼编码是一种 前缀码任何码字都不是其他码字前缀从而保证唯一可译。2. 编码规则规定朝左的路径为0朝右的路径为13. 解码规则从左到右扫描二进制串按树走路遇 0 向左遇 1 向右到叶子即输出对应字符再回到根继续。四、多叉树1.B树节点叉数-12.构建五阶B树超过五阶把中间抵上去3.B树1.定义B树的非叶子节点仅具有索引作用 只能存储key值不可以存value2.应用不适合在磁盘适合在数据库key值为索引value值为地址3.构建只把索引值顶上去value值不往上走