思路：使用Scanner接受屏幕输入，在这里，仅限连续的小写字母
求出不同字母在上述Scanner输入中，出现的次数。 比如字母a（如果有），出现几次，b（如果有），出现几次……
根据不同字母出现的次数（权值），构建哈夫曼树
得到每个字母对应的路径，即可生成哈夫曼编码
对已有的哈夫曼编码，采取从头开始截取编码
长度从1开始，如果截取下来的编码与某个字母匹配，则去掉这个截取的编码 继续截取新的编码，长度从1开始，到2，到3，直到截取的字符串与某个字母匹配…… 继续上述操作，最后得到原先的连续的小写字母
package fifty;
public class Node {
Node leftNode;
Node rightNode;
int data;
char zifu;
public Node(){
leftNode = null;
rightNode = null;
data = 0;
zifu = 'a';
}
}
package fifty;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class HuffmanCoding {
static List<String[]> qlist = new ArrayList<String[]>();
//qlist里某个数组内元素个数
public static int getCnt(String[] s){
int n = 0;
for(int i = 0; i < s.length; i++)
{
if(null != s[i])
n++;
}
return n;
}
//每条路径装在一个数组里，每个数组装在qlist里
private static void printPaths(Node node, String[] path,
int pathLen){
if(node == null){
return;
}
path[pathLen++] = /*Character.toString(node.zifu)*/
Integer.toString(node.data);
if(node.leftNode == null
&& node.rightNode == null){
//System.out.print(node.zifu+"：");
//printArray(node, path, pathLen);
path[0] = Character.toString(node.zifu);
String[] s = new String[path.length];
for(int m = 0; m < path.length; m++){
s[m] = path[m];
}
qlist.add(s);
}else{
printPaths(node.leftNode, path, pathLen);
printPaths(node.rightNode, path, pathLen);
}
}
//求最小值
public static int[] getMinInt(List<Integer> list){
int[] min = new int[2];
min[1] = (int) Collections.min(list);
min[0] = list.indexOf(min[1]);
list.remove(list.indexOf(min[1]));
return min;
}
//求根节点的值最小的两棵树
public static Node[] getMinInt2(List<Node> list){
List<Integer> newlist = new ArrayList<Integer>();
int[] min2 = new int[2];
Node[] newtree = new Node[2];
for(int m = 0; m < list.size(); m++){
newlist.add(list.get(m).data);
}
min2 = getMinInt(newlist);
newtree[0] = list.get(min2[0]);
list.remove(list.indexOf(newtree[0]));
min2 = getMinInt(newlist);
newtree[1] = list.get(min2[0]);
list.remove(list.indexOf(newtree[1]));
return newtree;
}
//获取左节点
public static Node getLeftNode(Node node){
return node.leftNode;
}
//获取右节点
public static Node getRightNode(Node node){
return node.rightNode;
}
//节点总数
public static int sumNode(Node node){
if(node == null){
return 0;
}else{
int a = sumNode(getLeftNode(node));
int b = sumNode(getRightNode(node));
return 1+a+b;
}
}
//主函数
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String input;
System.out.println("输入（仅限连续的小写字母）：");
input = scanner.next();
/*String[] shuzu = new String[100];
for(int m = 0; m <= input.length()-1; m++){
shuzu[m] = Character.toString(input.charAt(m));
}*/
int[] countabc = new int[26];
for(int m = 0; m <=input.length()-1; m++){
char c = input.charAt(m);
int index = c-'a';
countabc[index] = countabc[index]+1;
}
List<Integer> list = new ArrayList<>();
List<Character> charlist = new ArrayList<Character>();
int count = 0;
for(int m = 0; m < countabc.length; m++){
if(countabc[m] != 0){
list.add(countabc[m]);
charlist.add((char)(m+'a'));
count++;
System.out.println((char)(m+'a')
+"："+countabc[m]+"次");
}
}
System.out.println("字母种类："+count);
//构建二叉树
Node[] node = new Node[count];
//赋值给每棵树的根节点
for(int m = 0; m < count; m++){
node[m] = new Node();
node[m].data = list.get(m);
node[m].zifu = charlist.get(m);
}
List<Node> otherlist = new ArrayList<Node>();
for(int m = 0; m < count; m++){
otherlist.add(node[m]);
}
Node[] tempnode = new Node[2];
//newlist用于存储旧树新树
List<Node> newlist = new ArrayList<Node>();
//while循环，构建哈夫曼树
while(otherlist.size() != 1){
tempnode = getMinInt2(otherlist);
Node newnode = new Node();
newlist.add(tempnode[0]);
newlist.add(tempnode[1]);
newnode.data = tempnode[0].data +
tempnode[1].data;
newnode.leftNode = tempnode[0];
newnode.leftNode.data = 0;
newnode.rightNode = tempnode[1];
newnode.rightNode.data = 1;
otherlist.add(newnode);
}
Node lastnode = otherlist.get(0);
newlist.add(lastnode); //最后一棵树加上去
int num = sumNode(lastnode);
System.out.println("节点个数："+num);
/* Node[] node_shuzu = new Node[num];
for(int m = 0; m < num; m++){
node_shuzu[m] = newlist.get(m);
if(node_shuzu[m].leftNode == null
&& node_shuzu[m].rightNode == null){
System.out.println(node_shuzu[m].data+"和"+node_shuzu[m].zifu+"和数组下标"+m);
}
}
*/ String[] path = new String[sumNode(lastnode)];
printPaths(lastnode, path, 0);
System.out.println("对应路径：");
for(int m = 0; m < qlist.size(); m++){
for(int n = 0; n < getCnt(qlist.get(m)); n++){
System.out.print(qlist.get(m)[n]);
}
System.out.println();
}
System.out.print("哈夫曼编码：");
List<String> numlist = new ArrayList<String>();//存储哈夫曼编码
for(int m = 0; m < input.length(); m++){
for(int i = 0; i < qlist.size(); i++){
if(Character.toString(input.charAt(m)).equals(qlist.get(i)[0])){
for(int n = 1; n < getCnt(qlist.get(i)); n++){
numlist.add(qlist.get(i)[n]);
System.out.print(qlist.get(i)[n]);
}
}
}
}
//numlist转换成字符串
String huffmanstr = numlist.toString();
huffmanstr = huffmanstr.substring(1, huffmanstr.length()-1);
huffmanstr = huffmanstr.replaceAll("[,]", "");
huffmanstr = huffmanstr.replaceAll("[ ]", "");
System.out.println();
System.out.println("huffmanstr长度："+huffmanstr.length());
System.out.print("numlist输出：");
for(int m = 0; m < numlist.size(); m++){
System.out.print(numlist.get(m));
}
System.out.println();
List<String> zlist = new ArrayList<String>();
for(int n = 0; n < qlist.size(); n++){
List<String> templist = new ArrayList<String>();
String s = null;
for(int m = 0; m < getCnt(qlist.get(n)); m++){
templist.add(qlist.get(n)[m]);
s = templist.toString();
s = s.substring(1, s.length()-1);
s = s.replaceAll("[,]", "");
s = s.replaceAll("[ ]", "");
}
zlist.add(s);
}
System.out.println("zlist输出：");
for(int m = 0; m < zlist.size(); m++){
System.out.println(zlist.get(m));
}
System.out.println("解码后得到：");
while(huffmanstr != null){
for(int m = 0; m < zlist.size(); m++){
inter:for(int n = 1; n <= huffmanstr.length(); n++){
if((huffmanstr.substring(0, n))
.equals(zlist.get(m).substring(1,zlist.get(m).length()))){
System.out.print(Character.toString(zlist.get(m).charAt(0)));
huffmanstr = huffmanstr.substring(n, huffmanstr.length());
continue inter;
}
}
}
}
scanner.close();
}
}
![数据在网络7层中的传输过程[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)