C++应用_赫夫曼树.pdf

1． 设计思想 本程序将实现从键盘输入一组字线的权值等相关信息，然后 对这些字母进行赫夫曼编码。 主要思想即为赫夫曼算法。 （1 ） 根据给定的 N 个权值构成的 N 棵二叉树的集合 F ， 其中每棵二叉树中只有一个带权为 W 的根结点，其 左右子树均空。 （2 ） 在 F 中选取两棵根结点权值最小的树作为左右子树 构造一棵新的二叉树，且置新的二叉树的根结点的 权值为其左，右子树上根结点的权值之和。 （3 ） 在 F 中删除这两棵树，同时将新得到的二树加入 F 中 （4 ） 重复（2 ）和（3 ），直到F 只含一棵树为止。这棵树 便是赫夫曼树。 由于赫夫曼树中没有度为1 的结点则一棵有N 个叶子结点的 赫夫曼树共有 2N-1 个结点，可以存储在一个大小为 2N-1 的 一维数组。如何选定结点结构？由于在构成赫夫曼树之后， 为求编码需从叶子结点出发走一条从叶子到根的路径；而为 译码需从根出发走一条从根到叶子的路径。则对每个结点而 言，既需知双亲的信息，又需知孩子结点的信息。由此，则 作如下程序。 2． 源程序代码 运行结果如下： #includeiostream.h #includeiomanip.h struct huffmantree {//weight存放字母的权值。 int weight; int parent,lchild,rchild; }; void select(huffmantree a[],int p,int s1,int s2) {//在数组a[1,p]中选择 parent为 0 且 weight 最小的两个结点，其序号分别为 s1,s2. int q=1; while(a[q].parent !=0) ++q; s1=q; while(q=p) { if(a[q].weight a[s1].weight a[q].parent 0) s1=q; q++; } q=1; while(a[q].parent !=0q!=s1) ++q; s2=q; while(q=p) { if(a[q].weight a[s2].weight q!=s1a[q].parent 0) s2=q; q++; } } void main() { int n; int m; do {cout请输入字母个数；(=10)endl; cinn;}while(n10); m=2*n-1; huffmantree ht[20]; int hc[101]; char s=A; int i=1; int j; int k,a,b; int start=100; int s1; int s2; for(i,s;i=n;++i,++s) {//输入数组中前 项的权值，对其余部分全部初始化为 0。 coutPlease enter s`s weightendl; cinht[i].weight ; ht[i].parent =0; ht[i].lchild=0; ht[i].rchild=0; } for(i;i=m;+