《数据结构实用教程(C语言版)》第5章_树(精品·公开课件).ppt

数据结构实用教程（C语言版） 中国水利水电出版社 【例5.7】假设有一组权值{2,3,7,8,12,9,6,19}，下面我们将利用这组权值演示构造哈夫曼树的过程。 解：第一步：以这8个权值作为根结点的权值构造具有8棵树的森林。 第二步：从中选择两个根的权值最小的树2、3作为左右子树构造一棵新树，并将这两棵树从森林中删除，并将新树5添加进去。 返回到本节目录 第三步：重复第二步过程，直到森林中只有一棵树为止 选择5、6，将11放回。 选择7、8，将15放回。 返回到本节目录 选择9、11，将20放回 选择12、15，将27放回。 返回到本节目录 选择19、20，将39放回。 选择27、39，最后森林中只有一棵树，结束操作，这棵树就是哈夫曼树。 返回到本节目录 为了实现构造哈夫曼树的算法，设计哈夫曼树中每个结点类型如下： typedef struct { char data; /*结点值*/ int weight; /*权值*/ int parent; /*双亲结点下标*/ int lchild; /*左孩子结点下标*/ int rchild; /*右孩子结点下标*/ }HTCode; /*哈夫曼树结点类型*/ 返回到本节目录 用ht数组存放哈夫曼树，对于具有n个叶子结点的哈夫曼树，总共有2n-1个结点。其算法思路是：n个叶子结点只有data和weight域值，先将所有2n-1个结点的parent、lchild和rchild域置为-1。处理每个非叶子结点ht[i]（存放在ht[n]～ht[2n-2]中）：从ht[0]～ht[i-2]中找出根结点（即其parent域为-1）最小的两个结点ht[lnode]和ht[rnode]，将它们作为ht[i]的左右子树，ht[lnode]和ht[rnode]双亲结点置为ht[i]，并且ht[i].weight= ht[lnode].weight+ht[rnode].weight。如此这样直到所有的n-1个非叶子结点处理完毕。构造哈夫曼树的算法如算法5.7。 返回到本节目录 算法5.7 void CreateHT(HTCode ht[],int n) { int i,j,k,lnode,rnode; int min1,min2; for(i=0;i2*n-1;i++) /*将双亲、左、右孩子域置初值-1*/ ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for(i=n;i2*n-1;i++) { min1=min2=32767; /*两个最小值置初值为系统最大值*/ lnode=rnode=-1; 返回到本节目录 for(k=0;ki;k++) { if(ht[k].parent==-1) if(min1ht[k].weight) { min1=ht[k].weight; /*找出最小的权值*/ lnode=k; /*最小权值的结点下标值*/ } } for(k=0;ki;k++) { if(ht[k].parent==-1) if(min2ht[k].weight k!=lnode) { min2=ht[k].weight; /* 找出次最小的权值 */ rnode=k; /*次最小权值的结点下标值*/ } } 返回到本节目录 ht[lnode].parent=i;ht[rnode].parent=i; ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode;ht[i].rchild=rnode; } } 返回到本节目录 5.5.3 哈夫曼编码 1．什么是哈夫编码？ 在进行快速远距离的通信时，经常需要将传送的文字转换成由二进制字符0，1组成的二进制代码，称之为编码。 如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码