过程如图所示：
图片.png
public class NodeClass {
public String key;
public int value;
public NodeClass left;
public NodeClass right;
public NodeClass(String key, int value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "NodeClass{" +
"key='" + key + '\'' +
", value=" + value +
", left=" + left +
", right=" + right +
'}';
}
import javax.xml.soap.Node;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
/**
* @author shkstart
* @create --
*/
public class Huffman {
public static void main(String[] args) {
String str = "ajsfhsdhfasdfkjhsdfhsalkdjsfhdsfhjsklasjfjksfdghkslkdahjfjhsdgasjfhsdjfjshhfg";
HashMap<String,Integer> map=new HashMap<String,Integer>();
for(int i=0;i<str.length();i++){
String ch=str.charAt(i)+"";
if(map.get(ch)==null){
map.put(ch,1);
}
else{
map.put(ch,map.get(ch)+1);
}
}
ArrayList<NodeClass> arr=new ArrayList<NodeClass>();
for(Map.Entry<String ,Integer> en:map.entrySet()){
NodeClass no=new NodeClass(en.getKey(),en.getValue());
arr.add(no);
}
for(;;){
if(arr.size()>1){
NodeClass[] data=getNode(arr);
NodeClass root=new NodeClass(null,data[0].value+data[1].value);
root.left=data[0];
root.right=data[1];
arr.add(root);
}
else {
break;
}
}
NodeClass tree=arr.get(0);
Map<String,String> charMaps = new HashMap<>();//字符-编码
Map<String,String> codeMaps = new HashMap<>();//编码-字符
//System.out.println(tree);
allView(tree,"",charMaps,codeMaps);
String hafucode = "";
for(int i = 0; i < str.length(); i++) {
String ch = str.charAt(i) + "";
hafucode += charMaps.get(ch);
}
System.out.println( hafucode.length() + "||" + str.length() );
System.out.println( hafucode );
int i=0;
for(int j=i+1;j<hafucode.length();){
String tmp=hafucode.substring(i,j);
if(codeMaps.get(tmp)!=null){
System.out.print(codeMaps.get(tmp));
i=j;
}
else {
j++;
}
}
}
public static void allView(NodeClass tree,String code, Map<String,String> charMaps , Map<String,String> codeMaps ){
if(tree.left==null){
// System.out.println(tree.value+"||"+tree.key+"||code:"+code);
charMaps.put(tree.key, code);
codeMaps.put(code, tree.key);
}else{
allView(tree.left,code+"0",charMaps, codeMaps);
allView(tree.right,code+"1",charMaps, codeMaps);
}
}
public static NodeClass[] getNode(ArrayList<NodeClass> arr){//?
NodeClass[] nos=new NodeClass[2];
int index1=0;
int index2=1;
if( arr.get(0).value <= arr.get(1).value ) {
index1 = 0;
index2 = 1;
}else {
index1 = 1;
index2 = 0;
}
for(int i=2;i<arr.size();i++){
if(arr.get(i).value<arr.get(index1).value){
index2=index1;
index1=i;
}
else if(arr.get(i).value>=arr.get(index1).value&&arr.get(i).value<arr.get(index2).value){
index2=i;
}
}
nos[0]=arr.get(index1);
nos[1]=arr.get(index2);
arr.remove(index1);
if(index2>index1){
arr.remove(index2-1);
}
else
{
arr.remove(index2);
}
return nos;
}
}
优化后,作者：橘子辉煌_秦
package algorithm.ds;
import java.util.*;
/**
* @program: relearn
* @description: 哈夫曼树的实现
* 对于哈夫曼树，规定左 0 右 1
* @author: qinda
* @create: 2020-05-13 14:01
**/
public class Huffman {
/**
* 哈夫曼节点
*/
static class Node
{
public int weight;
public Character word;
public Node left;
public Node right;
public String code = "";
public Node(int weight, Node left, Node right) {
this.weight = weight;
this.left = left;
this.right = right;
}
public Node(int weight, char word) {
this.weight = weight;
this.word = word;
}
@Override
public String toString() {
return "Node{" +
"weight=" + weight +
", word=" + word +
", left=" + left +
", right=" + right +
", code='" + code + '\'' +
'}';
}
}
/**
* 比较器，用于优先队列
*/
static Comparator<Node> cmp = Comparator.comparingInt((Node e) -> e.weight);
public static void main(String[] args)
{
PriorityQueue<Node> queue = new PriorityQueue<>(cmp);
String in = userInput();
Map<Character,Integer> map = countFrequencyOfEachWord(in);
Node root = createHuffman(queue, map);
inorderTraversal(root);
Map<Character,String> everyCode = findEveryCodeByBFS(root);
for (Map.Entry<Character,String> entry : everyCode.entrySet())
System.out.println(entry.getKey()+" : "+entry.getValue());
String encode = encode(in, everyCode);
System.out.println(encode);
String decode = decode(encode, root);
System.out.println(decode);
}
/**
* 编码
* @param in 输入的字符串
* @param map 字母与编码映射
* @return 返回压缩后的编码
*/
public static String encode(String in, Map<Character,String> map)
{
StringBuilder s = new StringBuilder();
for(int i=0;i<in.length();i++)
s.append(map.get(in.charAt(i)));
return s.toString();
}
/**
* 解码
* 从树根开始，遇到1则往右，遇到0则往左，直到走到叶子节点算找到一个字母，然后再从根节点开始。
* @param in 待解码的字符串
* @param root 哈夫曼树根
* @return 返回解压后的字符串
*/
public static String decode(String in, Node root) {
int p = 0;
Node now = root;
StringBuilder s = new StringBuilder();
while (p < in.length())
{
char c = in.charAt(p);
if (c == '0' && now != null) now = now.left;
else if (c == '1' && now != null) now = now.right;
if (now != null && now.right == null && now.left == null)
{
s.append(now.word);
now = root;
}
p += 1;
}
return s.toString();
}
/**
* 根据哈夫曼树寻找每个字符的编码
* 使用bfs宽度优先搜索，左0右1
* @param root 树根
* @return 返回字母与编码映射
*/
public static Map<Character,String> findEveryCodeByBFS(Node root)
{
Queue<Node> queue = new LinkedList<>();
queue.add(root);
Map<Character,String> map = new HashMap<>();
while (!queue.isEmpty())
{
Node node = queue.poll();
if (node.left!=null)
{
node.left.code = node.code+ "0";
queue.add(node.left);
}
if(node.right != null)
{
node.right.code = node.code+"1";
queue.add(node.right);
}
if (node.right == null && node.left == null)
map.put(node.word,node.code);
}
return map;
}
/**
* 中序遍历哈夫曼树
* @param node 当前节点
*/
public static void inorderTraversal(Node node)
{
if (node == null)
return;
inorderTraversal(node.left);
System.out.println(node);
inorderTraversal(node.right);
}
/**
* 统计输入的字符串中每个单词出现的个数
* @param in 输入的字符串
* @return 返回每个字母与出现个数的映射
*/
public static Map<Character,Integer> countFrequencyOfEachWord(String in)
{
Map<Character,Integer> map = new HashMap<>();
for(int i=0;i<in.length();i++)
if (map.get(in.charAt(i)) == null) map.put(in.charAt(i), 1);
else map.put(in.charAt(i), map.get(in.charAt(i)) + 1);
System.out.println(map);
return map;
}
/**
* 用户输入
* @return 返回用户输入的字符串
*/
public static String userInput()
{
return new Scanner(System.in).nextLine();
}
/**
* 哈夫曼建树
* ①先将每个字母生成对应节点并入队
* ②当队列不为空时，取队头两节点，因为是优先队列，所以头两节点为权重最小的节点。
* ③生成新节点，新节点的权重为两节点之和，然后入队。
* 直到队列为空。
* @param queue 优先队列
* @param map 每个字母与出现个数的映射
* @return 返回树根
*/
public static Node createHuffman(PriorityQueue<Node> queue,Map<Character,Integer> map)
{
for (Map.Entry<Character,Integer> entry : map.entrySet())
queue.add(new Node(entry.getValue(),entry.getKey()));
Node root = null;
while (!queue.isEmpty())
{
Node node1 = queue.poll();
Node node2 = queue.poll();
if (node1 != null && node2 != null)
{
Node node = new Node(node1.weight+node2.weight,node1,node2);
if (queue.isEmpty())
{
root = node;
break;
}
queue.add(node);
}
}
return root;
}
}
