你好,游客 登录 注册 搜索
背景:
阅读新闻

将哈夫曼树转化成二叉树

[日期:2014-12-31] 来源:CSDN博客  作者:Low魂淡 [字体: ]

      今晚感觉好爽啊,好久好久没有这种感觉,起床需要点爆发力,做事还需要点动力,给自己都没有下过这么大的决心写代码,帮她却写的很好,我自己都吃惊了。哈 哈哈。。。今晚也是帮她写好西邮导航睡不着,那就敲了一下哈夫曼树转化成二叉树的代码,其实理解了真的不难,我定义F为一个二级指针,用它指向结点的地 址,创建很简单,输入数据data和权值weight,再把它的左右置为NULL;

        初始化话完了,就开始创建二叉树吧,我定义两个变量s1和s2,s1永远标记的是F这个指针数组中节点权值最小的一个,s2则为次小,特别注意,s1和 s2我每次初始化的时候都是放在F[i]!=NULL的结点上,这里用到了我前几次用的方法,利用for空语句循环找到s1和s2,对于如何让找出s1最 小s2次小我已经说过了,就再次不用说了;

    这里面的关键几步应该是如何把二叉树建立起来,假如说我已经找到小小s1和次小s2了,下面用图好解释:

           

   

    创建出来就是这个样子了,经过一次创建成为下面这个样子,

     

      循环n-1次之后二叉树就创建成功了,直接进入代码;

 

[cpp] view plaincopy
  1. #include <iostream> 
  2.  
  3. #include<stdlib.h> 
  4.  
  5. #include<conio.h> 
  6.  
  7. #define null NULL 
  8.  
  9.  
  10. typedef struct HuffNode{ 
  11.     char data; 
  12.     int weight; 
  13.     struct HuffNode *left,*right; 
  14. }HuffNode; 
  15.  
  16. HuffNode *CreateHuffman(HuffNode **,int ); 
  17. void preorder(HuffNode * ); 
  18. void leafprint(HuffNode *); 
  19. void Print(HuffNode *); 
  20.  
  21. HuffNode *CreateHuffman(HuffNode **F,int n){ 
  22.     HuffNode *p; 
  23.     int i,j; 
  24.     int k1=0,k2=1; 
  25.     for(i=0;i<n-1;i++) 
  26.     { 
  27.        for(k1=0;k1<n&&F[k1]==null;k1++); 
  28.       //    printf("数据%c,权值%d\n",F[k1]->data,F[k1]->weight); 
  29.        for(k2=k1+1;k2<n&&F[k2]==null;k2++); 
  30.       //    printf("数据%c,权值%d\n",F[k2]->data,F[k2]->weight); 
  31.        for(j=k2;j<n;j++) 
  32.        { 
  33.          if(F[j]) 
  34.          { 
  35.             if(F[j]->weight<F[k1]->weight) 
  36.             { 
  37.                 k2=k1; 
  38.                 k1=j; 
  39.             }     
  40.             else if(F[j]->weight<F[k2]->weight&&F[k2]) 
  41.             { 
  42.                 k2=j;         
  43.             }   
  44.          } 
  45.        } 
  46.        printf("输出最小k1=%d k2=%d\n",k1,k2); 
  47.          
  48.        p=(HuffNode *)malloc(sizeof(HuffNode)); 
  49.        p->weight=F[k1]->weight+F[k2]->weight; 
  50.        p->data='w'
  51.        p->left=F[k1]; 
  52.        p->right=F[k2]; 
  53.        F[k1]=p; 
  54.        F[k2]=null; 
  55.          
  56.          
  57.     Print(F[k1]); 
  58.     } 
  59.     return F[k1];         
  60.      
  61.  
  62. void Print(HuffNode *root){ 
  63.      
  64.     if(root) 
  65.     { 
  66.         printf("数据%c,权值%d\n",root->data,root->weight); 
  67.         Print(root->left); 
  68.         Print(root->right); 
  69.     } 
  70.  
  71. void leafprint(HuffNode *root){ 
  72.     if(root) 
  73.     { 
  74.         if(root->left==NULL&&root->right==NULL) 
  75.           printf("数据%c,权值%d\n",root->data,root->weight); 
  76.         leafprint(root->left); 
  77.         leafprint(root->right); 
  78.     } 
  79.      
  80.  int main(int argc, char** argv) { 
  81.     HuffNode **F; 
  82.     HuffNode *root; 
  83.     int n,i; 
  84.     printf("请你输入节点的个数: "); 
  85.     scanf("%d",&n); 
  86.     F=(HuffNode **)malloc(n*sizeof(HuffNode *)); 
  87.     for(i=0;i<n;i++){ 
  88.       fflush(stdin);   
  89.       F[i]=(HuffNode *)malloc(sizeof(HuffNode)); 
  90.       printf("\n输入第%d个节点的数据,权值: ",i+1); 
  91.       scanf("%c%d",&F[i]->data,&F[i]->weight); 
  92.       F[i]->left=F[i]->right=null; 
  93.        
  94.     } 
  95.     root=CreateHuffman(F,n);     
  96.     printf("\n先序遍历二叉树: \n"); 
  97.     Print (root); 
  98.     printf("\n遍历叶子结点: \n"); 
  99.     leafprint(root); 
  100.  return 0; 
  101. }     

对于如何遍历二叉树先序,中序,后序都可以,随意运行结果

 原文链接:http://blog.csdn.net/lotluck/article/details/41996255





收藏 推荐 打印 | 录入:Cstor | 阅读:
相关新闻       哈夫曼树  二叉树 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款