{
if(p) {
InThreading(p->lchild);/*左子树线索化*/
if(!p->lchild){p->LTag=Thread;p->lchild=pre;} /*前驱线索*/ if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;} /*后继线索*/
pre=p;/*保持pre指向p*/
InThreading(p->rchild);/*右子树线索化*/ }
}
int InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{/*中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点*/
if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0);
(*Thrt)->LTag=Link;(*Thrt)->RTag=Thread;/*建头结点*/ (*Thrt)->rchild=*Thrt;/*右指针回指*/ if (!T)
(*Thrt)->lchild=*Thrt;
else {
(*Thrt)->lchild=T;pre=*Thrt;
InThreading(T);/*中序遍历进行中序线索化*/
pre->rchild=*Thrt;pre->RTag=Thread;/*最后一个结点线索化*/ (*Thrt)->rchild=pre; }
return 1; }
//输出结点
int print(BiThrTree e) {
printf(\%c %d\\n\}
//中序遍历线索化二叉树
int InOrderTraverse(BiThrTree T,int (* visit)(BiThrTree e))
{/*T指向头结点，头结点的左链lchild指向根结点，中序遍厉二叉树 BiThrTree p;
p=T->lchild; /*p指向根结点*/
while(p!=T) /*空树或遍厉结束时，p==T*/ {
while(p->LTag==Link) p=p->lchild;
if(!visit(p)) return 0; /*打印*/
while(p->RTag==Thread&&p->rchild!=T)
{
p=p->rchild;visit(p);
11
}/*访问后继结点*/
p=p->rchild; }
return 1; }
void main() { /*测试程序*/ BiThrTree T,Thrt; CreatBinTree(&T);
InOrderThreading(&Thrt, T); InOrderTraverse(Thrt ,print); }
6.4 提高实验
[实验1] 哈夫曼树与哈夫曼编码
实验内容与要求:
从终端读入一段电文（允许出现标点和空格），统计其中出现的字符的个数，以及每个每个字符出现的频率，然后根据统计数据建立以字符作为叶子结点，以其出现的次数为权值的哈夫曼树，求出各字符的编码并输出。根据上述编码对输入的信息进行译码。
分析:
哈夫曼树是最优二叉树，利用哈夫曼树求得的用于通信的二进制编码成为哈夫曼编码。 树中从根到每个叶子都有一条路径，对路径上的各分支进行约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，去每条路径上的“0”和“1”的序列作为和各个叶子结点对应的字符的编码，就是哈夫曼编码。
假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n中字符，则电文编码总长为ΣWiLi。若将此对应到二叉树上，Wi为叶子结点的权，Li为根结点到叶子结点的路径长度，ΣWiLi恰好为二叉树上带权路径长度。 实现提示
根据题目要求，要实现本设计，必须实现以下几方面的功能： ①哈夫曼树的建立； ②哈夫曼编码的生成； ③编码文件的译码。 ⑴哈夫曼树的建立
由哈夫曼算法可知，初始森林中含有n棵只含有根结点的二叉树，每合并一次，森林中减少一个二叉树，产生一个新结点，最终求得的哈夫曼树中共有2n-1个结点。其中n 个叶结点是初始森林中的n个孤立结点。可用一个大小为2n-1的一维数组来存储哈夫曼树中的结点。因此哈夫曼树的存储结构描述为：
#define n 100 //树中叶结点的个数 #define m 2*n-1 //哈夫曼树中结点总数 typedef struct{
int weight; //权值
12
int lchild,rchild,parent; //左右还自己双亲指针 }HTNode; //树中结点类型
typedef HTNode HuffmanTree[m+1] ; //0号单元不用 要实现哈夫曼树算法，首先要实现HT[1..k]中选择parent为0且权值最小的两个根结点的选择算法；另外，还需要有一个记录电文中出现的各个字母以及统计它们出现的频率的算法。假设电文中仅含有大写字母。
1)选择parent为0且权值最小的两个根结点的算法： void select(HuffmanTree HT,int k,int &s1,int &s2)
{ //在HT[1..k]中选择parent为0且权值最小的两个根结点 //其序号分别为s1和s2，通过引用参数带回主调函数 int i,j;
int min1=32767;
for(i=1;i<=k;i++) // 找s1
if (HT[i].weight min1=HT[i].weight; } s1=j; min1=32767; for(i=1;i<=k;i++) // 找s1 if (HT[i].weight min1=HT[i].weight; } s2=j; } 2)统计电文中的字符及其出现的次数 假设电文中全是大写字母，该算法的思想为：定义一个含有26个元素的整形数组，用来存储各字母出现的次数。因为大写字母的ASCII码与整数1-26之间相差64，因此在算法中使用字母减去64 （或采用字母作为下标）作为统计数组的下标对号入座，可以免去循环判断。另外要求出电文中包含多少种字符，并保存这些字符以供编码时使用。可以用一个循环判断先前统计好的各类字符个数的数组是否为0，若不为0，表示该字符在电文中出现过，将其值存入一个数组对应的元素中，同时将其对应的字符也存入另一个数组的元素中。具体实现如下： int jsq(char *s,int cnt[],char str[]) 13 { char *p; int i,j,k; int temp[27]; for(i=1;i<=26;i++) temp[i]=0; for(p=s;*p!=’\\0’;p++) //统计各字符的个数 if(*p>=’A’ && *P<=’Z’) { k=*p-64; tepm[k]++; } j=0; for(i=1,j=0;i<=26;i++) if(temp[i]!=0) { j++; str[j]=i+64; //存入对应的字母到数组中 cnt[j]=temp[i] //存入对应字母的权值 } return j; } 3)构造哈夫曼树 void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[]) {//构造哈夫曼树HT int i,s1,s2; for(i=1;i<=2*num-1;i++) //初始化HT { HT[i].lchild=0; HT[i].rchild=0; HT[i].parent=0; HT[i].weight=0; } for(i=1;i<=num;i++) //输入n个结点的权值 HT[i].weight=cnt[i]; for(i=num+1;i<=2*num;i++); //生成其余n-1个结点 {// 在HT[1..k]中选择parent=0且权值最小的两个根结点s1和s2 select(HT,i-1,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].weight; 14 } for(i=0;i<=num;i++) HC[i].ch=str[i]; i=1; while(i<=num) { printf(“字符 %c, 次数为: %d\\n”,HC[i].ch,cnt[i]); i++; } } ⑵哈夫曼编码 要求电文的哈夫曼编码，必须先定义哈夫曼编码类型，根据设计需要类型定义如下： typedef struct{ char ch; char bits[n-1]; //存放编码位串 int len; //编码长度 }CodeNode; typedef CodeNode HuffmanCode[n]; 1)哈夫曼编码算法： void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC) {//根据哈夫曼树HT求哈夫曼编码 int c,p,i; //c和p分别指示HT中孩子和双亲的位置 char cd[n]; //临时存放编码串 int start ; //指示编码在cd 中的起始位置 cd[num]=’\\0’; //最后一位放串结束符 for(i=1;i<=num;i++) { start=num; c=i; //从叶结点HT[i]开始上朔 while((p=HT[c].parent)>0) //直至回朔到HT[c]的根为止 {//若HT[c]是HT[p]的左孩子,则生成0,否则生成代码1 cd[--start]=(HT[p].lchild==c)? ’0’ : ’1’; c=p; } strcpy(HC[i].bits,&cd[start]); HC[i].len=num-start; } } 2)建立正文的编码文件 将要编码的字符串中的字符逐一与预先生成哈夫曼树时保存的字符编码对照表进行比较，找到之后，对该字符的编码写入代码文件，直至所有字符处理完为止。具体算法如下： void coding(HuffmanCode HC,char *str) {//对str 所代表的字符串进行编码并写入磁盘文件 15