Huffman 编码

问题分析

• 可参考 数据结构——HuffmanTree

Java 代码实现

内含详细注释

/*
 * 若尘
 */
package huffmancode;

import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * 哈夫曼编码
 * @author ruochen
 * @version 1.0
 */
public class Test {

	/** 用来存放节点值 */
	private static LinkedList<HuffNode> huffList = new LinkedList<HuffNode>(); public static void main(String[] args) {
		// 第一个输入元素个数
		// 然后换行输入 对应权值 元素
		/** 如 * 5 * 10 a * 6 b * 4 c * 19 d * 1 e * **/
		System.out.println("Please input: ");
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i = 0; i < n; i++) { huffList.add(new Test().new HuffNode(sc.nextInt(), sc.next()));
		}
		huffmanCode();
		decode(huffList.get(0), "");
	} class HuffNode implements Comparable<HuffNode> {
		/** 权值 */
		int value;
		String name;
		/** 左孩子节点 */
		HuffNode lChild = null;
		/** 右孩子节点 */
		HuffNode rChild = null; public HuffNode(int value, String name) { this.value = value; this.name = name;
		} public HuffNode(HuffNode lChild, HuffNode rChild) { this.lChild = lChild; this.rChild = rChild; // 权值之和，即合并两个叶子节点 this.value = lChild.value + rChild.value;
		} /** * 按照权值大小非递减序列 * @param o * @return */
		@Override public int compareTo(HuffNode o) { if (this.value < o.value) { return -1; } else if (this.value == o.value) { return 0; } else { return 1; } }
	} /**
	 * 哈夫曼编码
	 */
	public static void huffmanCode() {
		if (huffList.size() == 1) { return ;
		}
		while (huffList.size() > 1) { // 排序 Collections.sort(huffList); // 将前两个节点进行合并 HuffNode node = new Test().new HuffNode(huffList.get(0), huffList.get(1)); // 删除前两个节点 huffList.remove(); huffList.remove(); // 将新生成的节点添加到列表中 huffList.add(node);
		}
		// 编码完成后，此时huffList中只剩一个根节点
	} /**
	 * 解码
	 * @param n
	 * @param code
	 */
	public static void decode(HuffNode n, String code) {
		if ((n.lChild == null) && (n.rChild == null)) { // 叶子节点， 此时输出其对应编码 System.out.print(n.name + "--->" + code); System.out.println(); return ;
		}
		// 遍历左子树
		decode(n.lChild, code + "0");
		// 遍历右子树
		decode(n.rChild, code + "1");
		return ;
	}
}


  

 

  
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
 

Please input: 
5
10 a
6 b
4 c
19 d
1 e
d--->0
a--->10
e--->1100
c--->1101
b--->111

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

文章来源: ruochen.blog.csdn.net，作者：若尘，版权归原作者所有，如需转载，请联系作者。

原文链接：ruochen.blog.csdn.net/article/details/106492694