做网站投广告赚钱么,提供网站建设教程的网站,建筑品牌网站,各类网页设计哈夫曼树#xff08;最优二叉树#xff09;
1#xff09;基础概念
**路径#xff1a;**从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。
**结点的路径长度#xff1a;**两结点间路径上的分支数。 **树的路径长度#xff1a;**从树根到每一个结点的路径…哈夫曼树最优二叉树
1基础概念
**路径**从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。
**结点的路径长度**两结点间路径上的分支数。 **树的路径长度**从树根到每一个结点的路径长度之和。记作TL。 结点数目相同的二叉树中完全二叉树是路径长度最短的二叉树。
**权**将树中结点赋给一个有着某种含义的数值则这个数值称为该结点的权。
**结点的带权路径长度**从根结点到该结点之间的路径长度与该结点的权的乘积。
**树的带权路径长度**树中所有叶子结点的带权路径长度之和。 2构造哈夫曼树 顺序存储结构——一维结构数组
1定义结构 typedef struct {int weight; int parent, lch, rch;
}HTNode, * HuffmanTree;HuffmanTree H;2步骤 初始化HT [1…2n-1]lch rch parent 0输入初始几个叶子结点置HT[1…n]的 weight 值进行以下n-1次合并依次产生n-1个结点HT[i]i n 1…2n-1 在HT[1…i-1]中选两个未被选过(从parent 0 的结点中选)的weight最小的两个结点 HT[S1] 和 HT[S2]s1、s2为两个最小结点下标修改 HT[s1] 和 HT[s2] 的parent值HT[s1].parent i; HT[s2] .parent i;修改新产生的HT[i]
HT[i].weight HT[s1].weight HT[s2].weight;
HTli].Ich s1;
HT[i].rch s2;void CreatHuffmanTree(HuffmanTree HT, int n) { //构造哈夫曼树--哈夫曼算法if (n 1) return;int m 2 * n - 1; // 数组共2n-1个元素HT new HTNode[m 1]; // 动态分配内存0号单元未用HT[m]表示根结点// 初始化2n-1个元素的lch、rch、parent为0for (int i 1; i m; i) {HT[i].lch HT[i].rch HT[i].parent 0;}// 输入前n个元素的weight值cout 请输入 n 个字符的频率 endl;for (int i 1; i n; i) {cin HT[i].weight;}// 构建哈夫曼树for (int i n 1; i m; i) {int s1, s2;Select(HT, i - 1, s1, s2);HT[s1].parent i;HT[s2].parent i;HT[i].lch s1;HT[i].rch s2;HT[i].weight HT[s1].weight HT[s2].weight;}
}3总代码
权值为整数
#include iostream
#include limits.husing namespace std;// 定义哈夫曼树节点结构
typedef struct {int weight;int parent, lch, rch;
} HTNode;typedef HTNode* HuffmanTree;// 选择两个双亲域为0且权值最小的结点
void Select(const HTNode* HT, int i, int s1, int s2) {s1 s2 -1;int min1 INT_MAX, min2 INT_MAX;for (int j 1; j i; j) {if (HT[j].parent 0 HT[j].weight min1) {min2 min1;s2 s1;min1 HT[j].weight;s1 j;}else if (HT[j].parent 0 HT[j].weight min2) {min2 HT[j].weight;s2 j;}}
}void CreatHuffmanTree(HuffmanTree HT, int n) { //构造哈夫曼树--哈夫曼算法if (n 1) return;int m 2 * n - 1; // 数组共2n-1个元素HT new HTNode[m 1]; // 动态分配内存0号单元未用HT[m]表示根结点// 初始化2n-1个元素的lch、rch、parent为0for (int i 1; i m; i) {HT[i].lch HT[i].rch HT[i].parent 0;}// 输入前n个元素的weight值cout 请输入 n 个字符的频率 endl;for (int i 1; i n; i) {cin HT[i].weight;}// 构建哈夫曼树for (int i n 1; i m; i) {int s1, s2;Select(HT, i - 1, s1, s2);HT[s1].parent i;HT[s2].parent i;HT[i].lch s1;HT[i].rch s2;HT[i].weight HT[s1].weight HT[s2].weight;}
}int main() {int n;cout 请输入叶子节点的数量;cin n;HuffmanTree HT;CreatHuffmanTree(HT, n);// 打印哈夫曼树示例cout 哈夫曼树构造完成打印结果如下 endl;for (int i 1; i 2 * n; i) {cout Node i : Weight HT[i].weight , Parent HT[i].parent , Left Child HT[i].lch , Right Child HT[i].rch endl;}delete[] HT; // 释放动态分配的内存return 0;
}权值为浮点数
#include iostream
#include limits.h // 如果不再使用 INT_MAX可以不需要这个头文件using namespace std;// 定义哈夫曼树节点结构将 weight 改为 double 类型
typedef struct {double weight; // 权值改为 double 类型int parent, lch, rch;
} HTNode;typedef HTNode* HuffmanTree;// 选择两个双亲域为0且权值最小的结点
void Select(const HTNode* HT, int i, int s1, int s2) {s1 s2 -1;double min1 DBL_MAX, min2 DBL_MAX; // 使用 DBL_MAX 作为最大值初始化for (int j 1; j i; j) {if (HT[j].parent 0 HT[j].weight min1) {min2 min1;s2 s1;min1 HT[j].weight;s1 j;}else if (HT[j].parent 0 HT[j].weight min2) {min2 HT[j].weight;s2 j;}}
}void CreatHuffmanTree(HuffmanTree HT, int n) { //构造哈夫曼树--哈夫曼算法if (n 1) return;int m 2 * n - 1; // 数组共2n-1个元素HT new HTNode[m 1]; // 动态分配内存0号单元未用HT[m]表示根结点// 初始化2n-1个元素的lch、rch、parent为0for (int i 1; i m; i) {HT[i].lch HT[i].rch HT[i].parent 0;HT[i].weight 0.0; // 初始化 weight 为 0.0}// 输入前n个元素的weight值cout 请输入 n 个字符的小数频率 endl;for (int i 1; i n; i) {cin HT[i].weight;}// 构建哈夫曼树for (int i n 1; i m; i) {int s1, s2;Select(HT, i - 1, s1, s2);HT[s1].parent i;HT[s2].parent i;HT[i].lch s1;HT[i].rch s2;HT[i].weight HT[s1].weight HT[s2].weight;}
}int main() {int n;cout 请输入叶子节点的数量;cin n;HuffmanTree HT;CreatHuffmanTree(HT, n);// 打印哈夫曼树示例cout 哈夫曼树构造完成打印结果如下 endl;for (int i 1; i 2 * n - 1; i) { // 注意这里应该是 2*n-1 而不是 2*ncout Node i : Weight HT[i].weight , Parent HT[i].parent , Left Child HT[i].lch , Right Child HT[i].rch endl;}delete[] HT; // 释放动态分配的内存return 0;
}4运行结果 3哈夫曼编码
在远程通讯中要将待传字符转换成由二进制的字符串
若将编码设计为长度不等的二进制编码即让待传字符串中出现次数较多的字符采用尽可能短的编码则转换的二进制字符串便可能减少。
问题1 什么样的前缀码能使得电文总长最短
——哈夫曼编码
方法:
1、统计字符集中每个字符在电文中出现的平均概率概率越大要求编码越短。
2、利用哈夫曼树的特点权越大的叶子离根越近将每个字符的概率值作为权值构造哈夫曼树。 则概率越大的结点路径越短。
3、在哈夫曼树的每个分支上标上0或1
结点的左分支标0右分支桥 1。把从根到每个吐子的路径上的标号连接起来作为该叶子代表的字符的编码。 问题2 为什么哈夫曼编码能够保证是前缀编码?
因为没有一片树叶是另一片树叶的祖先所以每个叶结点的编码就不可能是其它叶结点编码的前缀。
问题 3 为什么哈夫曼编码能够保证字符编码总长最短?
因为哈夫曼树的带权路径长度最短故字符编码的总长最短。
性质1 哈夫曼编码是前缀码性质2 哈夫曼编码是最优前缀码
算法实现
// 从叶子到根逆向求每个字符的哈夫曼编码存储在编码表HC中
void CreatHuffmanCode(const HuffmanTree HT, HuffmanCode HC, int n) {HC new char*[n 1]; // 分配n个字符编码的头指针数组char* cd new char[n]; // 分配临时存放编码的动态数组空间cd[n - 1] \0; // 编码结束符for (int i 1; i n; i) {int start n - 1;int c i;int f HT[i].parent;// 从叶子结点开始向上回溯直到根结点while (f ! 0) {--start;if (HT[f].lch c)cd[start] 0; // 结点c是f的左孩子则生成代码0elsecd[start] 1; // 结点c是f的右孩子则生成代码1c f;f HT[f].parent;}// 计算编码长度并分配适当的空间int codeLength n - start;HC[i] new char[codeLength];strncpy(HC[i], cd[start], codeLength);HC[i][codeLength - 1] \0; // 确保字符串以空字符终止}delete[] cd; // 释放临时空间
}strncpy(HC[i], cd[start], codeLength);语句在C中确实可以用于复制字符数组但它有一些潜在的问题和局限性。特别是当你使用strncpy时如果目标缓冲区没有足够的空间来包含源字符串加上终止空字符\0它不会自动添加终止空字符这可能会导致后续操作出现问题。
此外在现代C中更推荐使用std::string来处理字符串因为它们更安全、更方便并且可以避免手动管理内存的复杂性和风险。
// 从叶子到根逆向求每个字符的哈夫曼编码存储在编码表HC中
void CreatHuffmanCode(const HuffmanTree HT, HuffmanCode HC, int n) {HC.resize(n 1); // 分配n个字符编码的空间for (int i 1; i n; i) {string code ;int c i;int f HT[i].parent;// 从叶子结点开始向上回溯直到根结点while (f ! 0) {if (HT[f].lch c)code 0 code; // 结点c是f的左孩子则生成代码0elsecode 1 code; // 结点c是f的右孩子则生成代码1c f;f HT[f].parent;}HC[i] code;}
}总代码实现 #include iostream
#include cstring // 用于 strcpy 和 strlen
#include limits // 用于 std::numeric_limitsusing namespace std;// 定义哈夫曼树节点结构
typedef struct HTNode {double weight; // 权重改为 double 类型int parent, lch, rch;
} HTNode;typedef HTNode* HuffmanTree;// 定义哈夫曼编码结构
typedef char** HuffmanCode;// 选择两个双亲域为0且权值最小的结点
void Select(const HTNode* HT, int i, int s1, int s2) {s1 s2 -1;double min1 numeric_limitsdouble::max(), min2 numeric_limitsdouble::max();for (int j 1; j i; j) {if (HT[j].parent 0 HT[j].weight min1) {min2 min1;s2 s1;min1 HT[j].weight;s1 j;} else if (HT[j].parent 0 HT[j].weight min2) {min2 HT[j].weight;s2 j;}}
}// 构造哈夫曼树--哈夫曼算法
void CreatHuffmanTree(HuffmanTree HT, int n) {if (n 1) return;int m 2 * n - 1; // 数组共2n-1个元素HT new HTNode[m 1]; // 动态分配内存0号单元未用HT[m]表示根结点// 初始化2n-1个元素的lch、rch、parent为0for (int i 1; i m; i) {HT[i].lch HT[i].rch HT[i].parent 0;HT[i].weight 0.0; // 初始化权重为 0.0}// 输入前n个元素的weight值cout 请输入 n 个字符的频率浮点数 endl;for (int i 1; i n; i) {cin HT[i].weight;}// 构建哈夫曼树for (int i n 1; i m; i) {int s1, s2;Select(HT, i - 1, s1, s2);HT[s1].parent i;HT[s2].parent i;HT[i].lch s1;HT[i].rch s2;HT[i].weight HT[s1].weight HT[s2].weight;}
}// 从叶子到根逆向求每个字符的哈夫曼编码存储在编码表HC中
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) {HC new char*[n 1]; // 分配n个字符编码的头指针数组char* cd new char[n]; // 分配临时存放编码的动态数组空间cd[n - 1] \0; // 编码结束符for (int i 1; i n; i) {int start n - 1;int c i;int f HT[i].parent;// 从叶子结点开始向上回溯直到根结点while (f ! 0) {--start;if (HT[f].lch c)cd[start] 0; // 结点c是f的左孩子则生成代码0elsecd[start] 1; // 结点c是f的右孩子则生成代码1c f;f HT[f].parent;}// 计算编码长度并分配适当的空间int codeLength n - start;HC[i] new char[codeLength];strncpy(HC[i], cd[start], codeLength);HC[i][codeLength - 1] \0; // 确保字符串以空字符终止}delete[] cd; // 释放临时空间
}// 测试函数
int main() {int n;cout 请输入叶子节点的数量;cin n;HuffmanTree HT;CreatHuffmanTree(HT, n);HuffmanCode HC;CreatHuffmanCode(HT, HC, n);// 打印哈夫曼编码cout 哈夫曼编码如下 endl;for (int i 1; i n; i) {cout Character i : HC[i] endl;}// 清理资源for (int i 1; i n; i) {delete[] HC[i];}delete[] HC;delete[] HT;return 0;
}改进后的代码
#include iostream
#include vector
#include string
#include limitsusing namespace std;// 定义哈夫曼树节点结构
typedef struct HTNode {double weight; // 权重改为 double 类型int parent, lch, rch;
} HTNode;typedef HTNode* HuffmanTree;// 选择两个双亲域为0且权值最小的结点
void Select(const vectorHTNode HT, int i, int s1, int s2) {s1 s2 -1;double min1 numeric_limitsdouble::max(), min2 numeric_limitsdouble::max();for (int j 1; j i; j) {if (HT[j].parent 0 HT[j].weight min1) {min2 min1;s2 s1;min1 HT[j].weight;s1 j;} else if (HT[j].parent 0 HT[j].weight min2) {min2 HT[j].weight;s2 j;}}
}// 构造哈夫曼树--哈夫曼算法
void CreatHuffmanTree(vectorHTNode HT, int n) {if (n 1) return;int m 2 * n - 1; // 数组共2n-1个元素// 初始化2n-1个元素的lch、rch、parent为0权重为0.0HT.resize(m 1);for (int i 1; i m; i) {HT[i] {0.0, 0, 0, 0};}// 输入前n个元素的weight值cout 请输入 n 个字符的频率浮点数 endl;for (int i 1; i n; i) {cin HT[i].weight;}// 构建哈夫曼树for (int i n 1; i m; i) {int s1, s2;Select(HT, i - 1, s1, s2);HT[s1].parent i;HT[s2].parent i;HT[i].lch s1;HT[i].rch s2;HT[i].weight HT[s1].weight HT[s2].weight;}
}// 从叶子到根逆向求每个字符的哈夫曼编码存储在编码表HC中
void CreatHuffmanCode(const vectorHTNode HT, vectorstring HC, int n) {HC.resize(n 1); // 分配n个字符编码的空间for (int i 1; i n; i) {string code ;int c i;int f HT[i].parent;// 从叶子结点开始向上回溯直到根结点while (f ! 0) {if (HT[f].lch c)code 0 code; // 结点c是f的左孩子则生成代码0elsecode 1 code; // 结点c是f的右孩子则生成代码1c f;f HT[f].parent;}HC[i] code;}
}// 测试函数
int main() {int n;cout 请输入叶子节点的数量;cin n;vectorHTNode HT;CreatHuffmanTree(HT, n);vectorstring HC;CreatHuffmanCode(HT, HC, n);// 打印哈夫曼编码cout 哈夫曼编码如下 endl;for (int i 1; i n; i) {cout Character i : HC[i] endl;}return 0;
}改进后
#include iostream
#include cstring // 用于 strcpy 和 strlen
#include limits // 用于 std::numeric_limitsusing namespace std;// 定义哈夫曼树节点结构
typedef struct HTNode {double weight; // 权重改为 double 类型int parent, lch, rch;
} HTNode;typedef HTNode* HuffmanTree;// 定义哈夫曼编码结构
typedef char** HuffmanCode;// 选择两个双亲域为0且权值最小的结点
void Select(const HTNode* HT, int i, int s1, int s2) {s1 s2 -1;double min1 numeric_limitsdouble::max(), min2 numeric_limitsdouble::max();for (int j 1; j i; j) {if (HT[j].parent 0 HT[j].weight min1) {min2 min1;s2 s1;min1 HT[j].weight;s1 j;} else if (HT[j].parent 0 HT[j].weight min2) {min2 HT[j].weight;s2 j;}}
}// 构造哈夫曼树--哈夫曼算法
void CreatHuffmanTree(HuffmanTree HT, int n) {if (n 1) return;int m 2 * n - 1; // 数组共2n-1个元素HT new HTNode[m 1]; // 动态分配内存0号单元未用HT[m]表示根结点// 初始化2n-1个元素的lch、rch、parent为0for (int i 1; i m; i) {HT[i].lch HT[i].rch HT[i].parent 0;HT[i].weight 0.0; // 初始化权重为 0.0}// 输入前n个元素的weight值cout 请输入 n 个字符的频率 endl;for (int i 1; i n; i) {cin HT[i].weight;}// 构建哈夫曼树for (int i n 1; i m; i) {int s1, s2;Select(HT, i - 1, s1, s2);HT[s1].parent i;HT[s2].parent i;HT[i].lch s1;HT[i].rch s2;HT[i].weight HT[s1].weight HT[s2].weight;}
}// 从叶子到根逆向求每个字符的哈夫曼编码存储在编码表HC中
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) {HC new char*[n 1]; // 分配n个字符编码的头指针数组for (int i 1; i n; i) {string code ; // 使用string来构建编码int c i;int f HT[i].parent;// 从叶子结点开始向上回溯直到根结点while (f ! 0) {if (HT[f].lch c)code 0 code; // 结点c是f的左孩子则生成代码0elsecode 1 code; // 结点c是f的右孩子则生成代码1c f;f HT[f].parent;}// 将string转换为C风格字符串并分配适当的空间HC[i] new char[code.length() 1];strcpy(HC[i], code.c_str());}
}// 测试函数
int main() {int n;cout 请输入叶子节点的数量;cin n;if (n 0) {cerr 叶子节点数量必须大于0. endl;return 1;}HuffmanTree HT;CreatHuffmanTree(HT, n);HuffmanCode HC;CreatHuffmanCode(HT, HC, n);// 打印哈夫曼编码cout 哈夫曼编码如下 endl;for (int i 1; i n; i) {cout Character i : HC[i] endl;}// 清理资源for (int i 1; i n; i) {delete[] HC[i];}delete[] HC;delete[] HT;return 0;
}运行结果
