这是我用二叉哈夫曼树代码改的，但是无法实现，首先是叶子节点和节点数没法表示，然后就算自己输入固定节点也无法正确实现，请问怎么实现三叉哈夫曼树呢
#include
#include
#include
#include
using namespace std;
typedef struct
{
unsigned int weight; //结点权值
unsigned int parent, lchild, rchild; //结点的父指针，左右孩子指针
}HTNode, HuffmanTree; //动态分配数组存储哈夫曼树
typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表
HuffmanTree HT; //哈夫曼树HT
HuffmanCode HC; //哈夫曼编码表HC
unsigned int *w; //w存放叶子结点权值
char * source_code;//source_code 存放原始码
void CreateHuffmanTree(HuffmanTree &, unsigned int, int); //生成一棵哈夫曼树
void HuffmanCoding(HuffmanTree, HuffmanCode &, int); //对哈夫曼树进行编码
void PrintHuffmanCode(HuffmanCode, unsigned int*, int); //显示哈夫曼编码
void Select(HuffmanTree, int, int&, int&); //在数组中寻找权值最小的两个结点
int main()
{
int n, i; //n是哈夫曼树叶子结点数
char choose = 'y'; //用于选择程序是否退出
//程序解说
printf("本程序将演示构造哈夫曼树.\n");
printf("首先输入叶子结点数目.\n例如:2\n");
printf("然后输入原始码以及权值.\n");
printf("第1个原始码及其权值 :");
printf("a 5\n");
printf("第2个原始码及其权值 :");
printf("b 3\n");
printf("程序会构造一棵哈夫曼树并显示哈夫曼编码.\n");
cout << "权值" << " " << "原始码" << " " << "哈夫曼编码" << endl;
printf(" 5 a 1\n");
printf(" 3 b 0\n");
putchar('\n');
putchar('\n');
while (choose != 'N'&&choose != 'n')
{
printf("请输入叶子结点数目:");
scanf("%d", &n); //输入叶子结点数
if (n <= 1)
{
printf("该数不合理!\n"); continue;
}
w = (unsigned int*)malloc(n * sizeof(unsigned int)); //开辟空间存放权值
source_code = (char *)malloc(n * sizeof(char)); //开辟空间存放原始码
//printf("请输入各原始码以及权值 :\n");
for (i = 0; i < n; i++)
{
printf("第%d个原始码及其权值 :", i + 1);
cin >> source_code[i]; //输入原始码
cin >> w[i]; //输入各叶子结点权值
}
CreateHuffmanTree(HT, w, n); //生成哈夫曼树
HuffmanCoding(HT, HC, n); //进行哈夫曼编码
putchar('\n');
PrintHuffmanCode(HC, w, n); //显示哈夫曼编码
printf("哈夫曼树构造完毕，还要继续吗?(Y/N)");
scanf(" %c", &choose);
}
}
void CreateHuffmanTree(HuffmanTree &HT, unsigned int *w, int n)
{//w存放n个结点的权值，将构造一棵哈夫曼树HT
int i, m;
int s1, s2;
HuffmanTree p;
if (n <= 1) return;
m = 2 * n - 1; //n个叶子结点的哈夫曼树，有2*n-1个结点
HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //开辟2*n各结点空间，0号单元不用
for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w) //进行初始化
{
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for (; i <= m; ++i, ++p)
{
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for (i = n + 1; i <= m; ++i) //建哈夫曼树
{
//从HT[1...i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2
Select(HT, i - 1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i; //修改s1和s2结点的父指针parent
HT[i].lchild = s1; HT[i].rchild = s2; //修改i结点的左右孩子指针
HT[i].weight = HT[s1].weight + HT[s2].weight; //修改权值
}
}
void HuffmanCoding(HuffmanTree HT, HuffmanCode &HC, int n)
{
//将有n个叶子结点的哈夫曼树HT进行编码， 所编的码存放在HC中
//方法是从叶子到根逆向求每个叶子结点的哈夫曼编码
int i, c, f, start;
char *cd;
HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //分配n个编码的头指针向量
cd = (char *)malloc(n * sizeof(char)); //开辟一个求编码的工作空间
cd[n - 1] = '\0'; //编码结束符
for (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)); //为第i个编码分配空间
strcpy(HC[i], &cd[start]); //将编码从cd复制到HC中
}
free(cd); //释放工作空间
}
void PrintHuffmanCode(HuffmanCode HC, unsigned int *w, int n)
{
//显示有n个叶子结点的哈夫曼树的编码表
int i;
printf("哈夫曼编码如下 :\n");
putchar('\n');
cout << "权值" << " " << "原始码" << " " << "哈夫曼编码" << endl;
for (i = 1; i <= n; i++)
{
printf(" %d", w[i - 1]);
printf(" %3c\t ", source_code[i - 1]);
puts(HC[i]);
}
printf("\n");
}
void Select(HuffmanTree HT, int t, int&s1, int&s2)
{
//在HT[1...t]中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2,s1存放最小的，s2存放次小的
int i = 0;
int j = 0;
int k = 0;
int least = 0;
int second = 0;
for (i = 1; i <= t; i++)
{
if (HT[i].parent == 0)
break;
}
for (j = i + 1; j <= t; j++)
{
if (HT[j].parent == 0)
break;
}
if (HT[i].weight < HT[j].weight)
{
least = i;
second = j;
}
else
{
least = j;
second = i;
}
for (k = j + 1; k <= t; k++)
{
if (HT[k].parent == 0)
{
if (HT[k].weight < HT[least].weight)
{
second = least;
least = k;
}
else if (HT[k].weight >= HT[least].weight && HT[k].weight < HT[second].weight)
second = k;
}
}
s1 = least;
s2 = second;
}
