构造哈夫曼树

哈夫曼编码以其高压缩比和压缩性能方面的优势一直在通信、数据压缩等领域占有重要的位置。

要实现哈夫曼编码必须先构造一棵哈夫曼树，下面就通过java进行简单的实现，通过图形化的方式展现生成哈夫曼树的全过程。

 import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.event.MouseAdapter; import java.awt.event.MouseEvent; import java.awt.geom.Ellipse2D; import java.awt.geom.Line2D; import java.util.ArrayList; import java.util.Collections; import java.util.List; import javax.swing.JFrame; import javax.swing.JPanel; public class HalfmanTree { private List<Node> collections = new ArrayList<Node>(); static private boolean stop = true; public Node getRoot(){ return collections.get(0); } public void add(int frequence){ collections.add(new Node(frequence)); } public void buildHalfmanTree(HMPanel p) throws InterruptedException{ while(collections.size() > 1){ Collections.sort(collections); //可以换更快速的排序方式 Node m1 = collections.remove(0); //获取最小的两个元素 Node m2 = collections.remove(0); Node n = new Node(m1.getFrequnce() + m2.getFrequnce()); System.out.println(m1.frequnce + "+"+ m2.frequnce + "=>"+ n.frequnce); n.setLeft(m1); n.setRight(m2); m1.setParent(n); m2.setParent(n); collections.add(n); p.setRoot(n); p.repaint(); while(stop) Thread.sleep(1000); stop = true; } } class Node implements Comparable<Node>{ int frequnce; Node left,right,parent; public Node(int frequnce) { super(); this.frequnce = frequnce; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } public Node getParent() { return parent; } public void setParent(Node parent) { this.parent = parent; } public int getFrequnce() { return frequnce; } @Override public int compareTo(Node o) { // TODO Auto-generated method stub return frequnce - o.frequnce; } private float x,y; public void Paint(Graphics2D g,float x,float y){ g.draw(new Ellipse2D.Double(x,y,15,15)); g.drawString(""+frequnce, x, y); this.x = x; this.y = y ; if(parent != null){ g.draw(new Line2D.Float(x,y,parent.x, parent.y)); } if(left !=null ){ left.Paint(g, x - 50, y + 30); } if(left !=null ){ right.Paint(g, x + 50, y + 30); } } } /** * @param args * @throws InterruptedException */ public static void main(String[] args) throws InterruptedException { HalfmanTree t = new HalfmanTree(); int[] nodes={ 2,5,6,7,8,9,20,40,18,13,54}; for(int n:nodes){ t.add(n); } JFrame jframe = new JFrame(); jframe.setBounds(100, 100, 800, 600); HMPanel p = new HMPanel(); jframe.add(p); jframe.setVisible(true); t.buildHalfmanTree(p); } static class HMPanel extends JPanel{ private Node root; private int startX = 400 ,startY =10; public HMPanel(){ addMouseListener(new MouseAdapter(){ @Override public void mouseClicked(MouseEvent e) { stop = false; } }); } @Override public void paint(Graphics g) { super.paint(g); if(root !=null) root.Paint((Graphics2D)g, startX, startY); } @Override public void update(Graphics g) { paint(g); } public void setRoot(Node root){ this.root = root; } } }