看了半天，写出了属于自己的代码。不正之处请指出
public class Haffman {
static class MyNode{
String code="";
int weight;
Character character;
MyNode left;
MyNode right;
public MyNode(Character character,int weight){
this.weight=weight;
this.character=character;
}
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext()){
String string=scanner.next();
MyNode root=create(string);
visit(root);
getHalmanCode(root);
}
}
public static MyNode create(String string){
char[]characters=string.toCharArray();
HashMap<Character,Integer>hashMap=new HashMap<Character, Integer>();
for (int i = 0; i < characters.length; i++) {
if (hashMap.containsKey(characters[i])) {
hashMap.put(characters[i],hashMap.get(characters[i])+1);
}else {
hashMap.put(characters[i], 1);
}
}
ArrayList<MyNode>nodes=new ArrayList<Haffman.MyNode>();
for (char key:hashMap.keySet()) {
nodes.add(new MyNode(key,hashMap.get(key)));
}
while(true){
if (nodes.size()<=1) {
break;
}
Collections.sort(nodes, new Comparator<MyNode>() {
@Override
public int compare(MyNode o1, MyNode o2) {
// TODO Auto-generated method stub
if (o1.weight==o2.weight) {
}
return o1.weight-o2.weight;
}
});
MyNode minNode=nodes.get(0);
MyNode sNode=nodes.get(1);
nodes.remove(minNode);
nodes.remove(sNode);
MyNode newNode=new MyNode(null, minNode.weight+sNode.weight);
newNode.left=minNode;
newNode.right=sNode;
nodes.add(newNode);
}
return nodes.get(0);
}
public static void visit(MyNode root){
if (root!=null) {
Queue<MyNode>myNodes=new LinkedList<Haffman.MyNode>();
myNodes.offer(root);
while(!myNodes.isEmpty()){
MyNode currentNode=myNodes.poll();
System.out.print(currentNode.weight+" ");
if (currentNode.left!=null) {
myNodes.offer(currentNode.left);
}
if (currentNode.right!=null) {
myNodes.offer(currentNode.right);
}
}
}
System.out.println();
}
public static void getHalmanCode(MyNode root)
{
if (root==null) {
return ;
}
Queue<MyNode>queue=new LinkedList<Haffman.MyNode>();
queue.offer(root);
//层次遍历进行编码的过程
while(!queue.isEmpty()){
MyNode currentNode=queue.poll();
if (currentNode.left!=null) {
if (currentNode.left.character==null) {
currentNode.left.code=currentNode.code+"0";
queue.offer(currentNode.left);
}else {
//说明是编码的字符，也即是叶子节点
System.out.println(currentNode.left.character+":"+currentNode.code+"0");
}
}
if (currentNode.right!=null) {
if (currentNode.right.character==null) {
currentNode.right.code=currentNode.code+"1";
queue.offer(currentNode.right);
}else {
System.out.println(currentNode.right.character+":"+currentNode.code+"1");
}
}
}
}
}