哈夫曼树构造算法的实现 
先考虑如何存储：既可以链式也可以顺序，但顺序存储结构（数组）简单点 这里用一维结构数组，结构数组是因为我们要保存的结点的值比较多，先看结点的类型定义 那几个值？每一个都要知道他的权值weight是多少，双亲parent是谁，左右孩子lch,rch是谁，所以4个值，定义成一个结构类型 
数组如图：它有多大？它有2n-1个素（n个结点进行n-1次合并……）为了简单，我们不使用0下标，所以数组的大小为2n，从1到2n-1，我们不用0就可以了 
每一个素有4个成员，我们用指针类型–哈夫曼树*Huffman来定义一个H:Huffman H,h就可以表示一个指针，或者数组 
让第一个结点的权值为5，同理继续…… 
例子：7+8=15，就可以定义一个16的数组（0-15），只用1到15 
首先，所有素的双亲和孩子都为0（构造森林全是根），用0来表示没有，然后输入权值 
生成n-1个结点，用循环，因为我们这里有n个叶子，所以我们从n+1开始：i=n+1，我们共有2n-1，直到2n-1结束 
选两小造新树：2，3，生成的5在9号结点，删掉2，3…… 
剩下parent为0，只有一个根，结束 
先初始化：1.左右孩子，parent设置为0；2.输入权值 
定义数组m=2n-1个素 2n-1在加1就是2m,这里0号不用，所以m+1 weighr要一个一个输入 
再n-1次合并，放在n+1到2n-1： 找到了，他们两个的双亲就是新产生的结点i:HT[s1].parent=i,HT[s2].parent=i 新产生节点的权重就是两个最小的权重的和：HT[i].weight=HT[s1].weight+HT[s2].weight 左孩子为s1,右孩子为s2：HT[i].lch=s1;HT[i].rch=s2 
Select函数具体的实现方法和本片完整的代码，如下文章： c语言构造哈夫曼树-哈夫曼编码_快乐的孙悟空的博客-CSDN博客_c语言哈夫曼树 void Select(HuffmanTree &HT,int x){//选出无父结点，并且权值最小的两个结点，赋值给s1，s2 int i,min1=inf,min2=inf; for(i=1;i<=x;i++){//找最小 if(HT[i].weight<min1&&HT[i].parent==0){min1=HT[i].weight;s1=i;} } for(i=1;i<=x;i++){//找次小 if(HT[i].weight<min2&&i!=s1&&HT[i].parent==0){ min2=HT[i].weight;s2=i; } } }
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/53179.html
