主题:[原创]求层次遍历二叉树的算法
以下是我编的求哈夫曼编码的程序,但用图形输出二叉树的算法不知如何写,我一朋友告我说用层次遍历输出二叉树就可以了,但层次遍历二叉树的算法怎么写啊?
各位大虾帮忙啊!
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define NULL 0
typedef struct
{
char symbol;
int weight;
int parent,lchild,rchild;
}HtNode,*HuffmenTree;
typedef char** HuffmenCode;
void Select(HtNode *Ht,int x,int a,int b)
{
int i=0;
int min1=20000;
int min2;
for(i=1;i<=x;i++)
{
if(Ht[i].parent==0&&Ht[i].weight<min1)
{
min1=Ht[i].weight;
a=i;
}
}
min2=20000;
for(i=1;i<=x;i++)
{
if(a!=i)
{
if(Ht[i].parent==0&&Ht[i].weight<min2)
{
min2=Ht[i].weight;
b=i;
}
}
}
Ht[a].parent=i;
Ht[b].parent=i;
Ht[i].lchild=a;
Ht[i].rchild=b;
Ht[i].weight=Ht[a].weight+Ht[b].weight;
}
void wplth(HtNode *Ht,int x)
{
int i;
int wpl=0;
for(i=1;i<=(2*x-1);i++)
{
if(Ht[i].symbol=='0')
wpl=wpl+Ht[i].weight;
}
printf("\nwpl:%d",wpl);
}
void createhuffmen(HtNode *Ht,int x,int y)
{
int i,s1,s2;
for(i=x+1;i<=y;i++)
{
Select(Ht,i-1,s1,s2);
}
}
void HuffmenCoding(HtNode *Ht,HuffmenCode *Hc,int n)
{
int i,start,f,c;
char *cd,*fd;
Hc=(HuffmenCode)malloc((n+1)*sizeof(char*));
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';
else
cd[--start]='1';
}
Hc[i]=(char*)malloc((n-start)*sizeof(char));
fd=&cd[start];
strcpy(Hc[i],fd);
}
for(i=1;i<=n;i++)
{
if(strlen(Hc[i-1])<9)
{ if(i%2==0)
{ printf("\t\t\t\tHc[%1d]:%s\n",i,Hc[i]);
}
else
{ printf("Hc[%1d]:%s",i,Hc[i]);
}
}
else
{ if(i%2==0)
{ printf("\t\t\tHc[%1d]:%s\n",i,Hc[i]);
}
else
{ printf("Hc[%1d]:%s",i,Hc[i]);
}
}
}
free(cd);
}
void main()
{
int wei[]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};
char sym[]={' ','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
HtNode *Ht;
HuffmenCode *Hc;
int n=27,i=0;
int m=2*n-1;
int j,k,t,s1,s2;
int start,c,f;
Ht=(HuffmenTree)malloc((m+1)*sizeof(HtNode));
for(i=1;i<=n;i++)
{
Ht[i].symbol=sym[i-1];
Ht[i].weight=wei[i-1];
Ht[i].parent=0;
Ht[i].lchild=0;
Ht[i].rchild=0;
}
for(i=n+1;i<=m;i++)
{
Ht[i].symbol='0';
Ht[i].weight=0;
Ht[i].parent=0;
Ht[i].lchild=0;
Ht[i].rchild=0;
}
createhuffmen(Ht,n,m);
for(i=1;i<=m;i++)
{
if(i%2!=0)
{
printf("Ht[%d]:%4c%4d%4d%4d%4d",i,Ht[i].symbol,Ht[i].weight,Ht[i].parent,Ht[i].lchild,Ht[i].rchild);
}
else
{
printf("\t\t\tHt[%d]:%4c%4d%4d%4d%4d\n",i,Ht[i].symbol,Ht[i].weight,Ht[i].parent,Ht[i].lchild,Ht[i].rchild);
}
}
getchar();
printf("\nHc:\n");
HuffmenCoding(Ht,Hc,n);
wplth(Ht,n);
}
各位大虾帮忙啊!
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define NULL 0
typedef struct
{
char symbol;
int weight;
int parent,lchild,rchild;
}HtNode,*HuffmenTree;
typedef char** HuffmenCode;
void Select(HtNode *Ht,int x,int a,int b)
{
int i=0;
int min1=20000;
int min2;
for(i=1;i<=x;i++)
{
if(Ht[i].parent==0&&Ht[i].weight<min1)
{
min1=Ht[i].weight;
a=i;
}
}
min2=20000;
for(i=1;i<=x;i++)
{
if(a!=i)
{
if(Ht[i].parent==0&&Ht[i].weight<min2)
{
min2=Ht[i].weight;
b=i;
}
}
}
Ht[a].parent=i;
Ht[b].parent=i;
Ht[i].lchild=a;
Ht[i].rchild=b;
Ht[i].weight=Ht[a].weight+Ht[b].weight;
}
void wplth(HtNode *Ht,int x)
{
int i;
int wpl=0;
for(i=1;i<=(2*x-1);i++)
{
if(Ht[i].symbol=='0')
wpl=wpl+Ht[i].weight;
}
printf("\nwpl:%d",wpl);
}
void createhuffmen(HtNode *Ht,int x,int y)
{
int i,s1,s2;
for(i=x+1;i<=y;i++)
{
Select(Ht,i-1,s1,s2);
}
}
void HuffmenCoding(HtNode *Ht,HuffmenCode *Hc,int n)
{
int i,start,f,c;
char *cd,*fd;
Hc=(HuffmenCode)malloc((n+1)*sizeof(char*));
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';
else
cd[--start]='1';
}
Hc[i]=(char*)malloc((n-start)*sizeof(char));
fd=&cd[start];
strcpy(Hc[i],fd);
}
for(i=1;i<=n;i++)
{
if(strlen(Hc[i-1])<9)
{ if(i%2==0)
{ printf("\t\t\t\tHc[%1d]:%s\n",i,Hc[i]);
}
else
{ printf("Hc[%1d]:%s",i,Hc[i]);
}
}
else
{ if(i%2==0)
{ printf("\t\t\tHc[%1d]:%s\n",i,Hc[i]);
}
else
{ printf("Hc[%1d]:%s",i,Hc[i]);
}
}
}
free(cd);
}
void main()
{
int wei[]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};
char sym[]={' ','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
HtNode *Ht;
HuffmenCode *Hc;
int n=27,i=0;
int m=2*n-1;
int j,k,t,s1,s2;
int start,c,f;
Ht=(HuffmenTree)malloc((m+1)*sizeof(HtNode));
for(i=1;i<=n;i++)
{
Ht[i].symbol=sym[i-1];
Ht[i].weight=wei[i-1];
Ht[i].parent=0;
Ht[i].lchild=0;
Ht[i].rchild=0;
}
for(i=n+1;i<=m;i++)
{
Ht[i].symbol='0';
Ht[i].weight=0;
Ht[i].parent=0;
Ht[i].lchild=0;
Ht[i].rchild=0;
}
createhuffmen(Ht,n,m);
for(i=1;i<=m;i++)
{
if(i%2!=0)
{
printf("Ht[%d]:%4c%4d%4d%4d%4d",i,Ht[i].symbol,Ht[i].weight,Ht[i].parent,Ht[i].lchild,Ht[i].rchild);
}
else
{
printf("\t\t\tHt[%d]:%4c%4d%4d%4d%4d\n",i,Ht[i].symbol,Ht[i].weight,Ht[i].parent,Ht[i].lchild,Ht[i].rchild);
}
}
getchar();
printf("\nHc:\n");
HuffmenCoding(Ht,Hc,n);
wplth(Ht,n);
}