本文目录一览：
- 1、java如何实现动态显示哈夫曼树？意思就是显示每次两个叶子结合，最后组成了一颗树的那个过程。求大神
- 2、已知字符集{a,b,c,d}的权值集合为{7,5,1,2},构造哈夫曼树,并求出字符集的哈夫
- 3、到底什么是哈夫曼树啊，求例子
- 4、Java中Huffman问题
- 5、在java中能直接把BitSet的对象直接输入到二进制文件中吗,用哪个流啊？
- 6、霍夫曼树一定是满二叉树吗？
java如何实现动态显示哈夫曼树？意思就是显示每次两个叶子结合，最后组成了一颗树的那个过程。求大神
根据二叉树的性质：n2=n0-1，列方程组得｛n2=n0-1,n0+n2=199｝，解方程组得n0=100，所以叶子结点有100个。
已知字符集{a,b,c,d}的权值集合为{7,5,1,2},构造哈夫曼树,并求出字符集的哈夫
在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；从森林中删除选取的两棵树，并将新树加入森林。
树的路径长度是从树根到每一结点的路径长度之和；
WPL=（W1*L1+W2*L2+W3*L3+…+Wn*Ln），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。可以证明哈夫曼树的WPL是最小的。
A-B合并（权5）
A-B再和C合并（权10）
D-E合并（权16）
（A-B）-C再和F合并（权21）
最后((A-B)-C)-F再和D-E合并（权37）
总之是找两个最小的结点合并，生成的新节点权为两个结点权之和。
平均路径长度为（2×3+3×3+5×2+7×1+9×1+12×1）/6=53/6约等于8.8
各字符Huffman编码可以为：A-0000 B-0001 C- 001 D-10 E-11 F-01
扩展资料：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
参考资料来源：百度百科-哈夫曼树
到底什么是哈夫曼树啊，求例子
哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
例子：
1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2、 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3、从森林中删除选取的两棵树，并将新树加入森林；
4、重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
扩展资料：
按照哈夫曼编码构思程序流程：
1、切割的顺序是从上往下，直至数组中的元素全部出现在叶节点；
2、我们思路正好相反，从数组中找出最小的两个元素作为最下面的叶节点，在向备选数组中存入这两个叶节点的和（这个新的和加入累加运算，这个和也就是所求的最小值的一部分，原因如上图）。
3、以本题为例，备选数组中现有元素为{30，30}，再次取出两个最小元素进行求和，得到新的元素，回归备选数组并记入累加。
4、上述2.3布重复执行直至备选数组中只有一个元素，此时累加结束，返回累加值即可
5、求数组中的最小值，可以用小根堆进行提取最为方便；此题用到了贪心的思路，即用相同的策略重复执行，直至我们得到所需的结果。
参考资料来源:百度百科——哈夫曼树
Java中Huffman问题
这题在实现层面变得和Huffman树没啥关系…
反复取取最小值，使值成为优先级..用优先队列最合适。。可自己把输入方式补上
import java.util.Arrays;
import java.util.PriorityQueue;
public class Test {
public static void main(String[] args){
Integer[] a= {5, 3, 8, 2, 9};
PriorityQueueInteger q=new PriorityQueueInteger(Arrays.asList(a));
int cost=0;
while(q.size()1){
System.out.println(q); //可删
int c=q.poll()+q.poll();
q.offer(c); cost+=c;
}
System.out.println(q); //可删
System.out.println(cost);
}
}
[2, 3, 8, 5, 9]
[5, 5, 8, 9]
[8, 9, 10]
[10, 17]
[27]
59
在java中能直接把BitSet的对象直接输入到二进制文件中吗,用哪个流啊？
package com.tuz;
import java.io.*;
public class MyTest {
public static void main(String[] args) {
String s = “010101”;
int i = Integer.parseInt(s, 2);//按照2进制提取为十进制
try {
DataOutputStream out=
new DataOutputStream(
new BufferedOutputStream(
new FileOutputStream(“Data”)));//Data是文件的名字
out.writeByte(i);
out.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
}
霍夫曼树一定是满二叉树吗？
不是。
满二叉树是所有分支都有左孩子右孩子结点，叶子结点在二叉树最下一层。
霍夫曼树是带权路径最短，也叫最优二叉树。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/312504.html
微信扫一扫 
支付宝扫一扫 