新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> We choose to study algorithmic problems,  not because they are easy,  but because they are hard.
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 算法理论与分析 』 → [求助]哈夫曼树的构造 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 8537 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： [求助]哈夫曼树的构造 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     sjbird331 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：39
      积分：175
      门派：XML.ORG.CN
      注册：2007/11/3

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给sjbird331发送一个短消息 把sjbird331加入好友 查看sjbird331的个人资料 搜索sjbird331在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看sjbird331的博客楼主
    发贴心情 [求助]哈夫曼树的构造

    近几天做了一些哈夫曼树的问题，发现有的参考书中对于哈夫曼树的构造问题存在不同的理解，这种理解造成了我在做题时的困惑。现在就把这些困惑的地方写出来，希望有兴趣的朋友能给我解答，谢谢
    （1）有的参考书上说，从给定序列T中选取权值最小的和次小的作为合并之后树的左、右孩子；而还有一些参考书则直接没有这种规定，直接选取较小的两个结点，而对于谁为左、右孩子，则没有规定。请问在实际的哈夫曼树构造过程中，我们应该遵循一个什么样的原则进行合并呢？
    （2）我做的一些题中，总是存在这样一个问题：构造完成后的哈夫曼树的带权路径长度总是正确的，但是构造之后树的结构和答案给出的哈夫曼树的结构存在一些差异，这种差异体现在原序列中结点的次序不对，比如说，答案中结点3和结点4分别为合并之后树的左、右孩子，但是我做出来的却是结点4和结点3分别为左、右孩子。请问，这种差异是正常的还是不正常的，WPL一样，但是结点的相对次序不一样（当然，对应的结点总是在同一层）
    请大家帮我想想这是怎么回事，谢谢

       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/19 9:25:00
     
     weiyild 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：1
      积分：58
      门派：XML.ORG.CN
      注册：2007/11/16

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给weiyild发送一个短消息 把weiyild加入好友 查看weiyild的个人资料 搜索weiyild在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看weiyild的博客第2楼
    发贴心情 
    做树的时候加入一条让小的固定做左孩子或者右孩子，然后做出的树应该就有序了
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/23 21:59:00
     
     zlsbm 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：4
      积分：76
      门派：GOOGLEBBS.NET
      注册：2007/4/30

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给zlsbm发送一个短消息 把zlsbm加入好友 查看zlsbm的个人资料 搜索zlsbm在『 算法理论与分析 』的所有贴子 点击这里发送电邮给zlsbm 引用回复这个贴子 回复这个贴子 查看zlsbm的博客第3楼
    发贴心情 
    首先得知道，哈夫曼树并不是唯一的，但在构造时需要确定条让小的固定做左孩子或者右孩子，那么如果没有权值相同的点，则应当是唯一的。

    ----------------------------------------------
    疯狂的石头！

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/24 10:50:00
     
     sjbird331 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：39
      积分：175
      门派：XML.ORG.CN
      注册：2007/11/3

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给sjbird331发送一个短消息 把sjbird331加入好友 查看sjbird331的个人资料 搜索sjbird331在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看sjbird331的博客第4楼
    发贴心情 
    在实际的做题过程中，题目通常对谁做左孩子，谁做右孩子没有限定，所以解题过程中是不是由我们自己进行约定
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/24 19:36:00
     
     weiyild 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：1
      积分：58
      门派：XML.ORG.CN
      注册：2007/11/16

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给weiyild发送一个短消息 把weiyild加入好友 查看weiyild的个人资料 搜索weiyild在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看weiyild的博客第5楼
    发贴心情 
    其实我觉得哈夫曼树的本质是让wpl值最低，所以我觉得左右子树颠倒不影响这个树的设计要求，如果希望让权值按某个顺序进行排序的话只要设定下就好了哦，相等的话可以根据其序列进行选择，这样的话就不会引起做出的树不确定了吧！
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/24 20:02:00
     
     冬天的农夫 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(面向对象是个好东东!)
      文章：85
      积分：606
      门派：XML.ORG.CN
      注册：2006/7/1

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给冬天的农夫发送一个短消息 把冬天的农夫加入好友 查看冬天的农夫的个人资料 搜索冬天的农夫在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看冬天的农夫的博客第6楼
    发贴心情 
    一般来说，在霍夫曼树中，得最小权值的节点是由最小堆取得的。每次从最小堆中取得两个节点。左右顺序只要规定好，就不会有错误。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/2/2 19:58:00
     
     LCW123 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：1
      积分：74
      门派：XML.ORG.CN
      注册：2008/5/22

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给LCW123发送一个短消息 把LCW123加入好友 查看LCW123的个人资料 搜索LCW123在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看LCW123的博客第7楼
    发贴心情 
    哈夫曼树不唯一 ，不管怎样，带权路径长度总是最小且为固定之，产生的编码值是唯一的
    可以从给定序列T中选取权值最小的和次小的作为合并之后树的左、右孩子入手，实现如下：
    typedef struct HaffNode
    {
     int weight;
     int parent;
     int lchild;
     int rchild;
    }HaffNode;
    void HaffMan(int w[],int n,HaffNode HNode[])
    {
     int min1, min2;
     int l_index, r_index; // 最小和次小权值的索引
     for(int i = 0; i <= 2*n-1; i++)
     {
      if(i <= n-1) HNode[i].weight = w[i];
      else HNode[i].weight = 0;
      HNode[i].parent = -1;
      HNode[i].lchild = -1;
      HNode[i].rchild = -1;
     }
     for(i = 0; i < n-1; i++) // 0 ... n-2
     {
      for(int j = 0; ; j++)   //查找未构造的哈夫曼节点
       if(HNode[j].parent == -1) break;
      min1 = min2 = HNode[j].weight;
      l_index = r_index = j;
      for(int k = j; k < n+i; k++) // j < n+n-2
      {
       if(HNode[k].weight < min1 && HNode[k].parent == -1)
       {
        min2 = min1;
        min1 = HNode[k].weight; // 最小权值
        r_index = l_index;
        l_index = k;
       }
       else if(((HNode[k].weight < min2 && HNode[k].weight > min1) || min1 == min2) && HNode[k].parent == -1)
       {
        min2 = HNode[k].weight; // 次最小权值
        r_index = k;
       }
      }
      HNode[l_index].parent = n + i;
      HNode[r_index].parent = n + i;
      HNode[n+i].weight = min1 + min2;
      HNode[n+i].lchild = l_index;
      HNode[n+i].rchild = r_index;
     }
    }
    int main(void)
    {
     int w[] = {2,6,1,8,3,1,2};
     int n = sizeof(w) / sizeof(w[0]);
     HaffNode*  ht = new HaffNode[2*n-1];
     HaffMan(w,n,ht);
     for(int i = 0; i < 2*n-1; i++)
     {
      cout<<"num = "<<i<<", weight = "<<ht[i].weight
       <<", parent = "<<ht[i].parent<<", lchild = "
       <<ht[i].lchild<<", rchild = "<<ht[i].rchild<<endl;
     }
     return 0;
    }
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/5/22 12:27:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 算法理论与分析 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/11/30 10:17:08

    本主题贴数7，分页： [1]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 89.844ms