1. package datastructure;
2. import java.awt.*;
3. import java.awt.geom.*;
4. import java.awt.image.*;
5. import java.io.*;
6. import javax.imageio.*;
7. import javax.servlet.*;
8. import javax.servlet.http.*;
9. class HTNode
10.{
11. int weight;
12. int parent;
13. int lchild;
14. int rchild;
15.}
16. public class HuffmanTree
17.{
18. private int pictureWidth=500;
19. private int pictureHeight=500;
20. public int s1,s2;
21. int n=(int)(2+9*Math.random());//随机生成结点的个数
22. int m=2*n-1;
23. public void draw(HttpServletResponse response)
24. {
25. response.reset();
26. response.setContentType( "image/png ");
27. BufferedImage image=new BufferedImage(pictureWidth,pictureHeight,BufferedImage.TYPE_INT_RGB);
28. Graphics2D g2d=image.createGraphics();
29. g2d.setPaint(Color.WHITE);
30. g2d.fillRect(0,0,pictureWidth, pictureHeight);
31. g2d.setPaint(Color.RED);
32. g2d.setFont(new Font( "TimesRoman ",Font.BOLD,24));
33. g2d.drawString( "赫夫曼树和赫夫曼编码演示 ",100,20);
34. HTNode HT[]=new HTNode[m+1];
35. HTNode HC[]=new HTNode[n];
36. HuffmanCoding(HT,HC,g2d);
37. g2d.dispose();
38. ServletOutputStream sos=null;
39. try
40. {
41. sos=response.getOutputStream();
42. ImageIO.write(image, "PNG ",sos);
43. sos.close();
44. }
45. catch (IOException ex){
46. }
47. }
48. public void HuffmanCoding(HTNode HT[],HTNode HC[],Graphics2D g2d)
49. {
50. int i;
51. int w[]=new int[n];//存取每个结点的权值
52. for(i=0;i <n;i++)
53. w[i]=(int)(1+20*Math.random());
54. for(i=1;i <=n;i++)
55. {
56. HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1;i <=m;i++)
{
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1;i <=m;i++)
{
Select(HT,i-1);
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+ HT[s2].weight;