本文目录一览：
- 1、Java实现哈夫曼算法，运行出现问题，求帮助，在线等！！！
- 2、数据结构程序作业 Huffman编码 是java版的哈 求帮忙呀 ~>.
- 3、用JAVA实现HUFFMAN算法 1 HUFFMAN算法原理 2 流程图 3 用JAVA语言编写代码
- 4、到底什么是哈夫曼树啊，求例子
- 5、Java中Huffman问题
- 6、用java实现哈夫曼编码
Java实现哈夫曼算法，运行出现问题，求帮助，在线等！！！
可以在Dog与Cat类中重写Animal中的animalDo方法，通过调用animalDo方法，
然后会自动根据不同的实例调用不同类中的方法（多态知识）。
数据结构程序作业 Huffman编码 是java版的哈 求帮忙呀 ~>.
import java.util.Random;class HuffmanTree
{
Node[] nodes;
HuffmanTree(Node[] nodes) {
this.nodes = nodes;
}
public static Node buildTree(Node[] nodes, int end) {
sort(nodes,end); // 根据树的权值由小到大排序
// 取出取值最小的两棵树
Node first = nodes[0];
Node second = nodes[1];
int data = first.data + second.data;
nodes[0] = new Node(data, first, second); //把前两棵树结合为新的树放到第一位
if (end == 1)
{
return nodes[0];
} else
{
for (int i = 1; i end-1 ; i++)
{
nodes[i] = nodes[i + 1]; // 将原数组的第三个以后的树前移一位
}
int len = end - 1;
return buildTree(nodes, len);
}
}
public static void sort(Node[] nodes,int end) {
for (int i = 1; i end; i++)
{
for (int j = 0; j i; j++)
{
if (nodes[j].data nodes[i].data)
{
Node temp = nodes[j];
nodes[j] = nodes[i];
nodes[i] = temp;
}
}
}
}
static String code = ""; // 记录递归路径 static String data = "";
static String str = "";
public static void recurse(Node node) {
if (node.data != null)
{
str += " " + node.data;
}
if (node.left != null)
{
code += "0";
recurse(node.left);
}
if (node.right != null)
{
code += "1";
recurse(node.right);
}
if (node.right == null node.left == null) // 递归达到叶节点取出code
{
System.out.println(node.data + " : " + code);
}
if (code.length() = 1)
{
code = code.substring(0, code.length() - 1); // 去掉code最后一位
}
}
public static void main(String[] args) {
Node[] nodes = new Node[50]; // 免得插入这么多字母 我这里就不一一列举了 你只需改一下这个数组 里面装26个字母的权值， 如果要带字母就在Node加一个成员变量就可以了 for (int i =0;i50 ;i++ )
{
Random r = new Random();
int n = r.nextInt(26);
nodes[i]=new Node(n,null,null);
}
Node n = buildTree(nodes,49);
recurse(n);
System.out.println("前序输出" + str);
}
}
class Node{
Integer data;
Node left;
Node right;
Node(Integer data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
}
用JAVA实现HUFFMAN算法 1 HUFFMAN算法原理 2 流程图 3 用JAVA语言编写代码
import java.util.*;
class HuffmanCode{
String name;
double weight;
int lc,rc,pa;
public HuffmanCode(){
name="";
weight=0;
lc=-1;rc=-1;pa=-1;
}
}
public class Huffman {
HuffmanCode[] codes;
String[] huffstring;
StringBuffer buffer=new StringBuffer();
public Huffman(String s) {
for(int i=0;is.length();i++){
if(buffer.indexOf(s.substring(i,i+1))==-1){
buffer.append(s.charAt(i));
}
}
System.out.println("字母："+buffer);
huffstring=new String[buffer.length()];
codes=new HuffmanCode[2*buffer.length()-1];
for(int i=0;i2*buffer.length()-1;i++)
codes[i]=new HuffmanCode();
for(int i=0;ibuffer.length();i++){
codes[i].name=buffer.substring(i,i+1);
codes[i].weight=haveNum(buffer.charAt(i),s);
}
getHuffstring();
getCode(2*buffer.length()-2,huffstring,"");
//for(int i=0;icodes.length;i++){
// System.out.println(""+i+":"+codes[i].name+codes[i].weight+" "+codes[i].lc+" "+codes[i].rc+" "+codes[i].pa);
//}
for(int i=0;ihuffstring.length;i++){
System.out.println(codes[i].name+" code:"+huffstring[i]);
}
System.out.println("编码："+getHuffmanCode(s));
System.out.println("平均码长为："+getLength());
}
public double getLength(){
double n=0;
for(int i=0;ibuffer.length();i++){
n+=huffstring[i].length();
}
return n/buffer.length();
}
public String getHuffmanCode(String s){
StringBuffer buf=new StringBuffer();
for(int i=0;is.length();i++){
buf.append(getEachCode(s.substring(i,i+1)));
}
return buf.toString();
}
public String getEachCode(String name){
for(int i=0;ibuffer.length();i++){
if(name.equals(codes[i].name)){
return huffstring[i];
}
}
return "";
}
public void getCode(int n,String[] thecodes,String thebuffer){
if(nthecodes.length){
thecodes[n]=thebuffer;
return;
}
getCode(codes[n].lc,thecodes,thebuffer+"0");
getCode(codes[n].rc,thecodes,thebuffer+"1");
}
public void getHuffstring(){
int[] twos={0,0};
for(int i=buffer.length();i2*buffer.length()-1;i++){
twos=findLastTwo(0,i);
codes[i].lc=twos[0];
codes[i].rc=twos[1];
codes[i].weight=codes[twos[0]].weight+codes[twos[1]].weight;
}
}
public int[] findLastTwo(int start,int end){
double[] weights={1.0,1.0};
int[] t={-1,-1};
for(int i=start;iend;i++){
if(codes[i].pa!=-1)continue;
if(weights[0]codes[i].weight){
weights[0]=codes[i].weight;
t[1]=t[0];
t[0]=i;
}
else if(weights[1]codes[i].weight){
weights[1]=codes[i].weight;
t[1]=i;
}
}
codes[t[0]].pa=end;
codes[t[1]].pa=end;
return t;
}
public double haveNum(char c,String s){
double n=0;
for(int i=0;is.length();i++){
if(c==s.charAt(i))n++;
}
return n/s.length();
}
public static void main (String[] args) {
System.out.print("输入编码字符串：");
Scanner sr=new Scanner(System.in);
new Huffman(sr.nextLine());
}
}
到底什么是哈夫曼树啊，求例子
哈夫曼树是给定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实现哈夫曼编码
只要自己再加个类Tree就可以了。
代码如下：
public class Tree {
double lChild, rChild, parent;
public Tree (double lChild, double rChild, double parent) {
this.lChild = lChild;
this.rChild = rChild;
this.parent = parent;
}
public double getLchild() {
return lChild;
}
public void setLchild(double lChild) {
this.lChild = lChild;
}
public double getRchild() {
return rChild;
}
public void setRchild(double rChild) {
this.rChild = rChild;
}
public double getParents() {
return parent;
}
public void setParents(double root) {
this.parent = root;
}
}
