赫夫曼树的特点.pptVIP

赫夫曼树的特点 1.权值越大的叶子离根越近，权值越小的叶结点越远离根结点。 2.具有n个叶子结点的赫夫曼树共有2n-1个节点。 3.赫夫曼树中没有度为1 的结点。 严格的二叉树：没有度为1 的结点的二叉树。 三、哈夫曼树的构造算法 设置一个结构数组HuffmanTree保存哈夫曼树中各结点的信息，数组元素的结构形式如下： typedef struct { unsingned int weight; unsingned int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树，0号单元不用 Typedef char * *HuffmanCode;//动态分配数组存储哈夫曼编码 其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组HuffmanTree中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过parent域的值来确定。初始时parent的值为0，当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffmanTree中的序号，就不会是0了。 构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组HuffmanTree的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffmanTree数组中的前n个分量的后面。 void HaffmanTree(HuffmanTree HT) {/*哈夫曼树的构造算法*/ int i,j,s1,s2,m1,m2,n,m; scanf(“%d”,n); /*输入叶子结点个数*/ m=2*n-1; HT=(HuffmanTree) malloc(m+1)*sizeof(HTNode)); for (i=1;i=2*n-1;i++) /*数组初始化*/ { HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for (i=1;i=n;i++) scanf(“%d”,HT[i].weight); /*输入n个叶子结点的权值*/ for (i=n+1;i=m;i++) /*构造哈夫曼树*/ { s1=s2=0; m1=m2= 10000; /*取最大权值为10000*/ for (j=1;j=i-1;j++) { if (HT[j].weightm1 HT[j].parent==0) { m2=m1; s2=s1; m1=HT[j].weight; s1=j; } else if (HT[j].weightm2 HT[j].parent==0) {m2=HT[j].weight; s2=j; } }/*查找权值最小且parent为0的两棵子树的序号s1 s2*/ /*将找出的两棵子树合并为一棵子树*/ HT[s1].parent=i; HT [s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight= HT [s1].weight+HT [s2].weigh; } } 四、哈夫曼树在编码问题中的应用 在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA，电文中只含有A，B，C，D四种字符， 字符的四种不同的编码方案 字符 编码 字符 编码 字符 编码 字符 编码 A 000 A 00 A 0 A 01 B 010 B 01 B 110 B 010 C 100 C 10 C 10