关于中序遍历HuffmanTree的问题 - Chinaunix

/****************************************************************************
文件名：Huffman.cpp
修改历史：
1.函数Output(HT,HC,n)的输出表示增加了制表位
2.修改Select(HuffmanTree &HT,int i,int &s1,int &s2),
具体为:for(j = 1; j <= i; j++)之处为把j<i改成j<=i
尚存在的问题：中序遍历？？
最后修改日期：2007,5,30
*****************************************************************************/
#include <stdlib.h>
#include <iostream.h>
#include <string.h>
#define MAX_SIZE 50
#define OVERFLOW -1
typedef struct
{
char letter;
int weight;
int parent;
int lchild;
int rchild;
}HTNode,*HuffmanTree;
typedef char * *HuffmanCode;
/***************************************************************************
函数名称：void Select(HuffmanTree &HT,int i,int &s1,int &s2)
功能描述：在HT[1...i]选择parent为空且weight最小的两个结点，其下标分别为s1,s2
具体实现：先把输入的第一个字符的权值的下标赋给s1，然后把每个字符的权值与 HT[s1].weight比较，
直至遍历输入的所有字符，把权值最小的下标赋给s1；用同样的方法再找到s2
****************************************************************************/
void Select(HuffmanTree &HT,int i,int &s1,int &s2)
{
int j, k;
for(k = 1; k < i; k++)
{
if(HT[k].parent != NULL)
continue;
s1 = k; //初始化s1
break;
}
for(j = 1; j <= i; j++)
{
if(HT[j].parent != NULL)
continue;
if(HT[j].weight < HT[s1].weight)
s1 = j;
}
for(k = 1; k <= i; k++)
{
if(HT[k].parent != NULL || k == s1)
continue;
s2 = k;
break;
}
for(j = 1; j <= i; j++)
{
if(HT[j].parent != NULL)
continue;
if(HT[j].weight <= HT[s2].weight && j != s1)
s2 = j;
}
} //end of void Select(HuffmanTree &HT,int i,int &s1,int &s2)
/*根据输入的字符及其权值建立哈夫曼树*/
void Creat_HuffmanTree(HuffmanTree &HT,HuffmanCode &HC,char *zifu,int *w,int n)
{
HuffmanTree p;
int m,s1,s2;
for(int i=0;i<n;i++) //输入字符
{
cout<<"请输入第"<<i+1<<"个字符:";
cin>>zifu[i];
}
for(i=0;i<n;i++) //输入字符对应的权值
{
cout<<"请输入字符"<<zifu[i]<<"的权值:";
cin>>w[i];
}
if(n <= 1)
return;
m = 2*n-1;
if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))
exit(OVERFLOW);
for(p=HT+1,i=1;i<=n;++i,++zifu,++p,++w)
{
/*生成独立的森林*/
p->parent = NULL;
p->letter = *zifu;
p->lchild = NULL;
p->rchild = NULL;
p->weight = *w;
}
for(;i<=m;++i,++p)
{
(*p).weight=0;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(i=n+1;i<=m;++i)
{
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;
}
}
/*从叶子到根求每个字符的编码*/
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *zifu,int *w,int n)
{
int c,f;
char *cd;
int start = 1;
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char*)malloc(n*sizeof(char));/*临时的code存储*/
cd[n-1]='\0'; //编码结束符
for(int i=1;i<=n;++i)
{
start = n - 1; //编码结束符位置
//从叶子到根逆向求编码
for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
if(HT[f].lchild == c)
cd[--start] = '0'; //树中的左分支表示字符'0'
else
cd[--start] = '1'; //树中的右分支表示字符'1'
HC[i] = (char *)malloc((n - start) * sizeof(char));
strcpy(HC[i], &cd[start]); //从cd复制编码（串）到HC
}
free(cd);
}
/*中序遍历HuffmanTree,输出其结点值,并对内部结点作标记*/
void InOrderTraverse(HuffmanTree HT,HuffmanTree HT2)
{
if(HT->lchild!=0)
InOrderTraverse(HT2+HT->lchild,HT2);
{//如果某个结点有孩子，显然它是内结点，应将其标记出来
if(HT->lchild!=0)
cout<<","<<HT->weight<<"(内点)";
else
cout<<","<<HT->weight;
}
if(HT->rchild!=0)
InOrderTraverse(HT2+HT->rchild,HT2);
} //end of void InOrderTraverse(HuffmanTree HT,HuffmanTree HT2,int n)
/*输出各字符的哈夫曼编码*/
void Output_HuffmanTree(HuffmanTree &HT,HuffmanCode &HC,int n)
{
cout<<"\nchar"<<"\tweight"<<"\thuffmancode\n";
for(int i=1;i<=n;i++)
cout<<HT[i].letter<<"\t"<<HT[i].weight<<"\t"<<HC[i]<<endl;
} //end of void Output_HuffmanTree(HuffmanTree &HT,HuffmanCode &HC,int n)
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int i=0;
char zifu[MAX_SIZE]; //zifu[]为存放字符的数组
int n=0,w[MAX_SIZE]; //w[]为存放权值的数组
cout<<"请输入字符的个数:";
cin>>n;
if(n<=0 || n>MAX_SIZE)
{
cerr<<"字符个数必须为不大于50的自然数!\n";
exit(1);
}
Creat_HuffmanTree(HT,HC,zifu,w,n);
HuffmanCoding(HT,HC,zifu,w,n);
Output_HuffmanTree(HT,HC,n);
{//这个花括号内的功能为中序遍历HuffmanTree
while(HT[i].parent!=0) i++; //确定HuffmanTree的所有结点数i
cout<<"\n中序遍历HuffmanTree结果如下:\n";
InOrderTraverse(HT+i,HT);
cout<<endl;
}
} //end of void main()

复制代码