-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHuffmanTree.java
More file actions
151 lines (132 loc) · 2.64 KB
/
HuffmanTree.java
File metadata and controls
151 lines (132 loc) · 2.64 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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
package chapter16_GreedyAlgorithm;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class HuffmanTree
{
private PriorityQueue<Node> nodeQueue;// 优先队列，用于构造Huffman树
private Map<String, String> codeMap;
public HuffmanTree()
{
super();
codeMap = new HashMap<>();
}
/**
* 用于生成Huffman数
*
* @param collection
* 节点集合
* @return 根节点
*/
public Node huffman(Collection<Node> collection)
{
int n = collection.size();
nodeQueue=new PriorityQueue<>(n, weightComparator);
for (Node node : collection)
nodeQueue.add(node);
//nodeQueue.addAll(collection,weightComparator);
Node xNode = null;
Node yNode = null;
for (int i = 1; i <= n - 1; i++)
{
xNode = nodeQueue.poll();
yNode = nodeQueue.poll();
Node zNode = new Node();
zNode.setLeftNode(xNode);
zNode.setRightNode(yNode);
zNode.setWeight(xNode.getWeight() + yNode.getWeight());
nodeQueue.add(zNode);
}
return nodeQueue.poll();
}
public Map<String, String> coding(Node root)
{
process(root, "");
return codeMap;
}
/**
* 给节点分配变长编码
*
* @param node
* 每个节点
* @param content
* 每个节点新增的编码
*/
private void process(Node node, String content)
{
// 叶子结点
if (node.getLeftNode() == null)
{
codeMap.put(node.getData(), content);
return;
}
// 对左子树分配代码"0"
process(node.getLeftNode(), content + "0");
// 对右子树分配代码"1"
process(node.getRightNode(), content + "1");
}
public static Comparator<Node> weightComparator=new Comparator<Node>()
{
@Override
public int compare(Node o1, Node o2)
{
return (int) (o1.getWeight()-o2.getWeight());
}
};
}
class Node
{
private String data;
private double weight;
private Node leftNode;
private Node rightNode;
public Node()
{
super();
}
public Node(String dataString, double weight)
{
super();
this.data = dataString;
this.weight = weight;
}
@Override
public String toString()
{
return "Node [data=" + data + ", weight=" + weight + "]";
}
public String getData()
{
return data;
}
public void setData(String data)
{
this.data = data;
}
public double getWeight()
{
return weight;
}
public void setWeight(double weight)
{
this.weight = weight;
}
public Node getLeftNode()
{
return leftNode;
}
public void setLeftNode(Node leftNode)
{
this.leftNode = leftNode;
}
public Node getRightNode()
{
return rightNode;
}
public void setRightNode(Node rightNode)
{
this.rightNode = rightNode;
}
}