回 帖 发 新 帖 刷新版面

主题:[原创]求层次遍历二叉树的算法

以下是我编的求哈夫曼编码的程序,但用图形输出二叉树的算法不知如何写,我一朋友告我说用层次遍历输出二叉树就可以了,但层次遍历二叉树的算法怎么写啊?
各位大虾帮忙啊!
#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);
}

回复列表 (共2个回复)

沙发

想想BFS你就知道

板凳

void travlevel(bitree *t)                         /*层次遍历二叉树*/
{
    bitree *qu[maxsize];
    int front,rear;
    front=rear=0;
    if(t!=NULL)
        printf("%c",t->data);
    rear++;
    qu[rear]=t;
    while(rear!=front)
    {   front=(front+1)%maxsize;
        t=qu[front];
        if(t->lchild!=NULL)
        {   printf("%c",t->lchild->data);
            rear=(rear+1)%maxsize;
            qu[rear]=t->lchild;
        }
        if(t->rchild!=NULL)
        {   printf("%c",t->rchild->data);
            rear=(rear+1)%maxsize;
            qu[rear]=t->rchild;
        }
    }
    printf("\n");
}

我来回复

您尚未登录,请登录后再回复。点此登录或注册