myhuffmantree.java

利用JAVA 实现的 霍夫曼编码压缩解压缩算法

package compress;

public class MyHuffmanTree
	{
		private int weight;
		private int parent;
		private int lchild;
		private int rchild;
		private int[][] HC;
		public MyHuffmanTree()
			{
				// TODO Auto-generated constructor stub
			}
		//建立huffman树及其编码
		public void CreatHuffmanTree(MyHuffmanTree[] HT,int[] w)
			{
				int n=w.length;
				if (n<1) return;
				int m=2*n-1;
				for(int i=1;i<=n;i++)
					HT[i].setHT(w[i-1],0,0,0);
				for(int i=n+1;i<=m;i++)
					HT[i].setHT(0,0,0,0);
				for(int i=n+1;i<=m;i++)
					{
						int s1=this.Select(HT,i-1);
						int s2=this.Select(HT,i-1);
						HT[s1].setParent(i);
						HT[s2].setParent(i);
						HT[i].setLchild(s1);
						HT[i].setRchild(s2);
						HT[i].setWeight(HT[s1].getWeight()+HT[s2].getWeight());
					}
				HC=new int[n+1][];
				int[] cd=new int[n];
				for(int i=1;i<=n;i++)
					{
						int start=0;
						for (int c=i,f=HT[i].getParent();  f!=0;  c=f,f=HT[f].getParent())
					         {
					        	 if (HT[f].getLchild()==c)
					        		  cd[++start]=0;
					        	 else cd[++start]=1;
					         }
						int cdlength=start;
						HC[i]=new int[cdlength];
						for(int j=0;j<cdlength;j++)
							{							
								this.setHC(i,j,cd[start]);
								start--;
							}
					}
			}
		//选取该树num以上节点的父母未知的最小节点
		public int Select(MyHuffmanTree[] HT,int num)
			{
				int order=1;
				while(HT[order].parent!=0)
					{
						order++;
					}
				int min=HT[order].getWeight();
				int s=order;
				for(int i=1;i<=num;i++)
					{if(HT[i].getWeight()<min&&HT[i].getParent()==0)
						{
							min=HT[i].getWeight();
							s=i;
						}
					}
				HT[s].setParent(1);
				return s;
			}
		public void setHT(int weight,int parent,int lchild,int rchild)
			{
				this.setWeight(weight);
				this.setParent(parent);
				this.setLchild(lchild);
				this.setRchild(rchild);
			}
		public int getLchild()
			{
				return lchild;
			}
		public int getParent()
			{
				return parent;
			}
		public int getRchild()
			{
				return rchild;
			}
		public int getWeight()
			{
				return weight;
			}
		public void setLchild(int lchild)
			{
				this.lchild = lchild;
			}
		public void setParent(int parent)
			{
				this.parent = parent;
			}
		public void setRchild(int rchild)
			{
				this.rchild = rchild;
			}
		public void setWeight(int weight)
			{
				this.weight = weight;
			}
		public void setHC(int i,int j,int hc)
			{
				HC[i][j] = hc;
			}
		public int getHC(int i,int j)
			{
				return HC[i][j];
			}
		public int[] getHC(int i)
			{
				return HC[i];
			}
		public int[][] getHC()
			{
				return HC;
			}
	}