哈夫曼树ht初态和终态
时间: 2023-11-05 11:19:02 浏览: 208
哈夫曼树的初态是由n个权值为w1,w2,...,wn的叶子节点构成的n棵二叉树,其中每棵二叉树仅包含一个叶子节点,并且每个叶子节点的权值就是wi。
哈夫曼树的终态是一棵包含n个叶子节点的二叉树,其中每个叶子节点的权值为wi,且树的带权路径长度最小。在构建哈夫曼树的过程中,我们通过不断合并权值最小的两棵树来逐步构造出这棵终态的二叉树。
相关问题
已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8,11,试填写出其对应哈夫曼树HT存储结构的初态和终态。
哈夫曼树是一种用于数据压缩的树形结构,其中每个叶子节点表示一个字符,而每个非叶子节点表示一个权值。根据权值的大小,构建哈夫曼树的过程如下:
初态:
首先,将每个字符作为一个独立的节点,并按照权值从小到大的顺序排列。
A(3) B(12) C(7) D(4) E(2) F(8) G(11)
然后,从这些节点中选择权值最小的两个节点,将它们合并为一个新的节点,并将新节点的权值设置为这两个节点的权值之和。将新节点插入到原来的节点列表中,并保持列表按照权值从小到大的顺序排列。
A(3) E(2) D(4) C(7) F(8) G(11) B(12)
继续选择权值最小的两个节点进行合并,重复上述步骤,直到只剩下一个节点为止。
A+E(5) D(4) C(7) F(8) G(11) B(12)
A+E(5) D(4) C(7) F+G(19) B(12)
A+E+D(9) C(7) F+G(19) B(12)
A+E+D+C(16) F+G(19) B(12)
A+E+D+C+F+G(35) B(12)
A+E+D+C+F+G+B(47)
终态:
最后剩下的节点就是哈夫曼树的根节点,即为整个树的初态和终态。
已知下列字符 A、B、C、D、E、F、G 的权值分别为 3、12、7、4、2、8,11,试填写出其 对应哈夫曼树 HT 的存储结构的初态和终态。 请编写出代码
已知字符 A、B、C、D、E、F、G 的权值分别为 3、12、7、4、2、8,11,其对应哈夫曼树 HT 的存储结构的初态和终态如下:
初态:
HT.weight = 0;
for (int i = 1; i <= 7; i++) {
HT[i].weight = w[i-1];
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
终态:
HT.weight = 48;
for (int i = 1; i <= 7; i++) {
HT[i].weight = w[i-1];
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for (int i = 8; i <= 13; i++) {
HT[i].weight = 0;
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for (int i = 8; i <= 13; i++) {
int s1, s2;
select(HT, i-1, s1, s2);
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
其中 select 函数为选择权值最小的两个结点的函数。