计算机科学论坛--显示贴子

以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『算法理论与分析』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  [求助]哈夫曼树的构造  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=56927)

--  作者：sjbird331
--  发布时间：12/19/2007 9:25:00 AM

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

--  作者：weiyild
--  发布时间：12/23/2007 9:59:00 PM

--
做树的时候加入一条让小的固定做左孩子或者右孩子，然后做出的树应该就有序了

--  作者：zlsbm
--  发布时间：12/24/2007 10:50:00 AM

--
首先得知道，哈夫曼树并不是唯一的，但在构造时需要确定条让小的固定做左孩子或者右孩子，那么如果没有权值相同的点，则应当是唯一的。

--  作者：sjbird331
--  发布时间：12/24/2007 7:36:00 PM

--
在实际的做题过程中，题目通常对谁做左孩子，谁做右孩子没有限定，所以解题过程中是不是由我们自己进行约定

--  作者：weiyild
--  发布时间：12/24/2007 8:02:00 PM

--
其实我觉得哈夫曼树的本质是让wpl值最低，所以我觉得左右子树颠倒不影响这个树的设计要求，如果希望让权值按某个顺序进行排序的话只要设定下就好了哦，相等的话可以根据其序列进行选择，这样的话就不会引起做出的树不确定了吧！

--  作者：冬天的农夫
--  发布时间：2/2/2008 7:58:00 PM

--
一般来说，在霍夫曼树中，得最小权值的节点是由最小堆取得的。每次从最小堆中取得两个节点。左右顺序只要规定好，就不会有错误。

--  作者：LCW123
--  发布时间：5/22/2008 12:27:00 PM

--
哈夫曼树不唯一，不管怎样，带权路径长度总是最小且为固定之，产生的编码值是唯一的
可以从给定序列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;
}

W 3 C h i n a ( since 2003 ) 旗下站点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》

1,519.531ms