-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHuffman.java
More file actions
98 lines (94 loc) · 2.41 KB
/
Copy pathHuffman.java
File metadata and controls
98 lines (94 loc) · 2.41 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import java.util.*;
public class TreeNode
{
public TreeNode leftNode;
public TreeNode rightNode;
public T data;
public TreeNode(T data)
{
this.data=data;
}
}
public class Huffman
{
public static void main(String[] args)
{
Character[] character = { 'A', 'B', 'C', 'D', 'E', 'F' };
int[] weight = { 2, 3, 5, 7, 9, 12 };
Map map=new HashMap();
for(int i=0;i> nodes = new ArrayList>();
for (int i = 0; i < weight.length; i++)
{
nodes.add(new TreeNode(weight[i]));
}
while (true)
{
if (nodes.size() <= 1)
break;
// 找两个最小的
TreeNode minNode = nodes.get(0);
TreeNode sminNode = nodes.get(1);
for (int i = 1; i < nodes.size(); i++)
{
TreeNode tempNode = nodes.get(i);
if (minNode.data >=tempNode.data)
{
sminNode = minNode;
minNode = tempNode;
}
}
nodes.remove(minNode);
nodes.remove(sminNode);
TreeNode newNode = new TreeNode(
minNode.data + sminNode.data);
newNode.leftNode = minNode;
newNode.rightNode = sminNode;
nodes.add(newNode);
}
TreeNodehafmanTreeNode=nodes.get(0);
getHalmanCode(hafmanTreeNode," ");
}
public static void getHalmanCode(TreeNodehafmanTreeNode,String blank)
{
if(hafmanTreeNode==null)
return;
if(hafmanTreeNode.leftNode==null&&hafmanTreeNode.rightNode==null)
{
System.out.println("->"+getCharacter(hafmanTreeNode.data));
}
else
{
System.out.print("0");
getHalmanCode(hafmanTreeNode.leftNode,blank+" ");
System.out.print(blank+"1");
getHalmanCode(hafmanTreeNode.rightNode,blank+" ");
}
}
public static void getHalmanCode(TreeNodehafmanTreeNode,Character character)
{
if(hafmanTreeNode==null)
return;
if(hafmanTreeNode.leftNode==null&&hafmanTreeNode.rightNode==null)
{
if (getCharacter(hafmanTreeNode.data)==character)
{
System.out.print("");
}
}
}
//得到权值对应的字符
public static Character getCharacter(int weight)
{
Set>set=map.entrySet();
for(Iterator> iterator=set.iterator();iterator.hasNext();)
{
Map.Entryentry=iterator.next();
if(entry.getValue()==weight)
{
map.remove(entry.getKey());
return entry.getKey();
}
}
return null;
}
}