二叉树运作结果有误~求修改

二叉树运行结果有误~求修改
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <stdlib.h>
#define N 6
typedef struct  //静态三叉链表
{
int weight;//用来存放各个结点的权值
int parent,LChild,RChild;//指向双亲，孩子结点的指针
}HTNode,*HuffmanTree;//动态分配数组，存储哈夫曼编码
typedef char **HuffmanCode;//动态分配数组，存储哈夫曼编码
void select(const HuffmanTree &ht,int n,int &s1,int &s2)//找出数组中权值最小的两个结点下标，分别用s1和s2保存
{
int i;
s1=s2=0;
int min1=INT_MIN;//最小值,INT_MAX在<limits.h>中定义
int min2=INT_MIN;//次小值
for(i=1;i<=n;++i)
{
if ( ht[i].parent == 0 )
{//筛选没有父节点的最小和次小权值下标
if ( ht[i].weight < min1 )
{//如果比最小值小
min2 = min1;
                 s2 = s1;
                 min1 = ht[i].weight;
                 s1 = i;
}
else if ( (ht[i].weight >= min1) && (ht[i].weight < min2) )
{//如果大于等于最小值，且小于次小值
                 min2 = ht[i].weight;
                 s2 = i;
}
else
{//如果大于次小值，则什么都不做
}
}
}
}
void CrtHuffmanTree(HuffmanTree &ht,HuffmanCode &hc,int *w,int n)//创建哈夫曼树并求哈夫曼树编码
{//w存放n个权值，构造哈夫曼树ht，并求出哈夫曼编码hc
int m;
int i;
int s1;
int s2;
int c;
int p;
char *cd;//暂存编码
m=2*n-1;//n个节点构造的哈夫曼树是2n-1个节点
ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未使用
for(i=1;i<=n;i++)//叶子结点初始化
{
ht[i].weight=w[i];
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
    for(i=n+1;i<=m;i++)//非叶子结点初始化
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=m;i++)//创建非叶子结点，建哈夫曼树
{//在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给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;
}//哈夫曼树建立完毕
//从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码
    hc=(char **)malloc((n)*sizeof(char *));//分配n个编码的头指针
cd=(char *)malloc(n*sizeof(char));//分配求当前编码的工作空间
for(i=1;i<=n;i++)//求n个叶子结点对应的哈夫曼编码
{
int start=n-1;//初始化编码起始指针
for(c=i,p=ht[c].parent;p!=0;c=p,p=ht[c].parent)//从叶子到根结点求编码
if(ht[p].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[n-1]='\0';//从右向左逐位存放编码，首先存放编码结束符
free(cd);
}
int main()
{
int i;
char key[N]={'0','A','B','C','D','E'};//第0个元素保留不用
int w[N]={0,1,2,4,5,6};//第0个元素保留不用
HuffmanTree ht;
HuffmanCode hc;
CrtHuffmanTree(ht,hc,w,N-1);
for(i=1;i<N;i++)
printf("%c:%s\n",key[i],hc[i]);
printf("\n");
    return 0;
}
运行结果如下：二叉树运作结果有误~求修改

程序哪里有问题问什么输不出正确的二叉树？求帮忙~

二叉树数据结构

------解决方案--------------------
  cd[n-1]='\0';//从右向左逐位存放编码，首先存放编码结束符
上面这行要移到下一行后面:
  cd=(char *)malloc(n*sizeof(char));//分配求当前编码的工作空间
  cd[n-1]='\0';//从右向左逐位存放编码，首先存放编码结束符

以下2行:
  int min1=INT_MIN;//最小值,INT_MAX在<limits.h>中定义
  int min2=INT_MIN;//次小值
要改为:
  int min1=INT_MAX;//最小值,INT_MAX在<limits.h>中定义
  int min2=INT_MAX;//次小值

二叉树运作结果有误~求修改

相关推荐