题目： 哈夫曼编码大全
描述：
关于哈夫曼树的建立，编码，解码。
输入
第一行输入数字N，代表总共有多少个字符以及权值
第二第三行分别是一行字符串，以及每个字符对应的权值
接下来输入一个数M，表示接下来有M行字符串，要求你对每个字符串进行编码
再输入一个数X，表示接下来有X行编码，要求你对每行编码进行解码
输出
第一行输出所有节点的权重
接下来输出N行，每行以 “a:001”的格式输出每个字符对应的编码
接着输出M行，对输入的字符串的编码结果
最后，输出X行的解码结果
输入样例
6
abcdef
50 10 5 5 20 10
2
abcdef
defabaabbc
2
011001100100110110101101100
1100011000110101100101100
输出样例
50 10 5 5 20 10 10 20 30 50 100
a:0
b:100
c:1100
d:1101
e:111
f:101
010011001101111101
11011111010100001001001100
accbdfadb
cacadacfb
import java.util.Scanner; /** * 哈弗曼编码大全 * @author 邹龄晋 6 abcdef 50 10 5 5 20 10 * */ public class Demo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int j; HFMTree ht = new HFMTree(n); int data[] = new int[n]; Code code[] = new Code[n]; String str = sc.next(); for(int i=0;i<n;i++){ j = sc.nextInt(); data[i] = j; } ht.init(data); ht.create(); //ht.PrintTree(); ht.Quan(); for(int i=0;i<n;i++){ System.out.print(str.charAt(i)+":"); //ht.PrintCode(i); //System.out.println(); String fff=ht.PrintCode3(i,""); code[i] = new Code(str.charAt(i),fff); System.out.println(fff); } //编码 int k=sc.nextInt(); while(k>0){ String s = sc.next(); for(int i=0;i<s.length();i++){ int m = str.indexOf(s.charAt(i)); ht.PrintCode(m); } k--; } k = sc.nextInt(); String st; int d; String ss = sc.nextLine(); while(k>0){ int q = 0; ss = sc.nextLine(); for(int m=1;m<=ss.length();m++){ st = ss.substring(q,m); for(d=0;d<code.length;d++){ if(st.equals(code[d].getCode())){ System.out.print(code[d].getCh()); break; } } if(d < code.length){ q = m; //System.out.println(m); } } System.out.println(); k --; } } } class HFMTree{ //属性 private int n;//结点数 private HN[] hn;//结点数组 public int getN() { return n; } public void setN(int n) { this.n = n; } public HN[] getHn() { return hn; } public void setHn(HN[] hn) { this.hn = hn; } public HFMTree(int n){ this.n = n; this.hn = new HN[2*n-1];//有n个结点,创建2*n-1个数组空间 for(int i=0;i<2*n-1;i++){ hn[i] = new HN();//创建2*n-1个HN的对象 } } public void init(int data[]){ for(int i=0;i<data.length;i++){ hn[i].setWeight(data[i]); } } //创建哈弗曼树 public void create(){ int min1=0,min2=0,i,j,temp; for(i=n;i<2*n-1;i++){ for(j=0;j<i;j++){ if(hn[j].getParent()==0){ min1=j; break; } } j++; for(;j<i;j++){ if(hn[j].getParent()==0){ min2=j; break; } } if(hn[min1].getWeight()>hn[min2].getWeight()){ temp = min1; min1 = min2; min2 = temp; } j++; for(;j<i;j++){ if(hn[j].getParent()==0){ if(hn[j].getWeight()<hn[min1].getWeight()){ min2 = min1; min1 = j; }else{ if(hn[j].getWeight()<hn[min2].getWeight()){ min2 = j; } } } } //上面的代码找到两个最小的,写到作为第i个左右孩子 hn[i].setWeight(hn[min1].getWeight()+hn[min2].getWeight()); hn[i].setLeft(min1); hn[i].setRight(min2); hn[min1].setParent(i); hn[min2].setParent(i); hn[i].setParent(0); } } //输出哈弗曼树 public void PrintTree(){ for(int i=0;i<2*n-1;i++){ System.out.println(i+" "+hn[i].getWeight()+" "+hn[i].getLeft()+" "+hn[i].getRight()+" "+hn[i].getParent()); } } //输出权数 public void Quan(){ for(int i=0;i<2*n-1;i++){ System.out.print(hn[i].getWeight()+" "); } System.out.println(); } //输出字符对应的代码方法一: public void PrintCode(int i){ if(hn[i].getParent()==0) return; int p = hn[i].getParent(); PrintCode(p); if(hn[p].getLeft()==i){ System.out.print(0); }else{ System.out.print(1); } } //输出字符对应的代码方法二: public String PrintCode2(int i){ String codes=""; if(hn[i].getParent()==0) return ""; int p = hn[i].getParent(); PrintCode(p); if(hn[p].getLeft()==i){ codes+="0"; }else{ codes+="1"; } return codes; } //方法三: public String PrintCode3(int i,String codes){ while(hn[i].getParent() != 0){ if(hn[hn[i].getParent()].getLeft() == i){ codes = codes + "0"; } if(hn[hn[i].getParent()].getRight() == i){ codes = codes + "1"; } i = hn[i].getParent(); } String codes1 = ""; for(int j=codes.length()-1;j>=0;j--){ codes1 = codes1 + codes.charAt(j); } return codes1; } } class HN{ private int weight; private int left; private int right; private int parent; public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } public int getLeft() { return left; } public void setLeft(int left) { this.left = left; } public int getRight() { return right; } public void setRight(int right) { this.right = right; } public int getParent() { return parent; } public void setParent(int parent) { this.parent = parent; } public HN(int weight){ this.weight = weight; this.left = 0; this.right = 0; this.parent = 0; } public HN(){ this.weight = 0; this.left = 0; this.right = 0; this.parent = 0; } } class Code{ private char ch; private String code; public char getCh() { return ch; } public void setCh(char ch) { this.ch = ch; } public String getCode() { return code; } public void setCode(String code) { this.code = code; } public Code(char ch,String code){ this.ch = ch; this.code = code; } }