打印哈弗曼树，输出哈码 小程序v1.0

package hTreeDemo;
import java.awt.Graphics;
import java.util.*;
import javax.swing.*;
/**
 * 给出一个字符串，统计每个字符在字符串中出现的次数，并返回一个TreeNode类型的数组
 * 用TreeNode类型的数组创建一个霍夫曼树，并制定每个叶节点的霍夫曼编码
 * 给出字符要求输出该字符的霍夫曼编码（或者给出字符串，给出该字符串的霍夫曼编码）
 * 
 * 画出一个界面，输入字符串，然后输出这段字符串的哈弗曼码以及画出哈弗曼树：
 * 建一个界面类，在main方法里调用：实现字符串输入和画出哈树及输出哈弗曼码的功能。
 * 
 * 最终是先从一个文件中传入数据压缩存储到另一可选位置，并可以解压缩的功能。
 * @author Administrator
 *
 */
public class Demo {

	/**
	 * 程序入口
	 * @param args
//	 */
//	public static void main(String[] args) {
//		Interface face=new Interface();
//		face.creatUI();
////		Demo demo=new Demo();
////		List<TreeNode> list=demo.creatNodeList("abbcccddddeeeeeeee中eeeeeeee中中中Feeeeeeeeeeeeeeeeeeeeeeeeeeeeghilinin");
////        for(int i=0;i<list.size();i++){
////        	System.out.println(list.get(i).getCh()+"  次数"+list.get(i).getWeight());
////        }
////		TreeNode root=demo.creatTree(list);
////        System.out.println(root);
////        demo.print(root);
////        
////        demo.setHfmcode(root);
////        System.out.println("已经设置了哈夫曼码");
////        String hfmcode1=demo.hfmcodeofSting("F",root);
////        System.out.println(hfmcode1);
////        String s="";
////        demo.set(root,s);
////        String hfmcode=demo.hfmcodeofSting("F",root);
////        System.out.println(hfmcode);
//        
//	}
	
	/**
	 * 传入字符串，生成一个节点队列。因为一般文字都是占有两个字节，所以输入的字符串都能转变为单个文字。
	 * @param str：字符串
	 * @return 树节点类型的队列
	 */
	public List<TreeNode> creatNodeList(String str){
		List<TreeNode> list=new ArrayList<TreeNode>();   //自定义队列，接受字符串中的字符
		for(int h=0;h<str.length();h++){
		     int count=0;   //计算下面的这个循环循环次数
		     for(int i=0;i<list.size();i++){  //遍历chars队列，看新的字符是不是在其中
		    	 
		    	 if(str.charAt(h)==list.get(i).getCh()){  
		    		 //如果str中去除的字符已经在节点队列中了
		    		 list.get(i).setWeight(list.get(i).getWeight()+1);   //让权重增加一
		    		 
		    		 break;  
		    	 }
		    	 count++;
		     }
		     
		     if(count==list.size()){   //如果str取出的新的char不在队列中
		    	 System.out.println("----------");
		    	 TreeNode newNode =new TreeNode(str.charAt(h));
		    	 newNode.setWeight(1);  
		    	 list.add(newNode);
		     }
		     
		     
		}
//		System.out.println(count01);
		return list;
	}
	
	/**
	 * 按权重给节点队列排序
	 * @return  weight属性从小到大排序的节点队列
	 */
	public List<TreeNode>  sortListW(List<TreeNode> list){
		for(int i=0;i<list.size();i++){
			for(int j=i+1;j<list.size();j++){
				if(list.get(j).getWeight()<list.get(i).getWeight()){
					//如果第j个节点元素的权重属性小于第i个元素的权重属性
					TreeNode newNode =list.set(i, list.get(j));//用指定元素替换以前在该位置的元素
				
					list.set(j, newNode);
				}
			}
		}
		return list;
	}
	
	/**
	 * 按父节点权重给节点队列排序
	 * @return  weight:属性从小到大排序的节点队列
	 */
	public void   sortListWofF(List<TreeNode> list){
		for(int i=0;i<list.size();i++){
			for(int j=i+1;j<list.size();j++){
				
				//排序
				if(list.get(j).getParent().getWeight()<list.get(i).getParent().getWeight()){
					//如果第j个节点元素的权重属性小于第i个元素的权重属性
					TreeNode newNode =list.set(i, list.get(j));//用指定元素替换以前在该位置的元素
				
					list.set(j, newNode);
				}
			}
		}
	}
 	
	/**
	 * 生成一个霍夫曼树，并给这个哈树节点的depth属性
	 * @param nodeList：按权重从小到大排好序的树节点类型的队列
	 * @param g:画布对象
	 * @param jf：在这个界面上加组件
	 * @return  霍夫曼树的根节点
	 */
	public TreeNode creatTree(List<TreeNode> nodeList,Graphics g,JFrame jf){

		while(true){
			nodeList=sortListW(nodeList);
		    TreeNode left=nodeList.remove(0);

		    TreeNode right=nodeList.remove(0);
			
	        TreeNode root=new TreeNode('F');
	        root.setWeight(right.getWeight()+left.getWeight());
	    
	        //手动确定三者之间的关系
	        left.setParent(root);
	        right.setParent(root);
	        root.setLeft(left);
	        root.setRight(right);
	        System.out.println("组合了一次");
	        
	    
	        nodeList.add(0,root);   //将根节点加到队列中
	    
	        if(nodeList.size()==1){
	        	 List<TreeNode> newList=new ArrayList<TreeNode>();
	        	 toList(root,newList); //把树转变为队列
	        	 
	        	//给每个节点加深度
	        	 for(int i=0;i<newList.size();i++){
	        		 TreeNode ran=newList.get(i);
	        		 TreeNode newNode=ran;
		        	 while(ran.getParent()!=null){
		        		 newNode.setDepth(newNode.getDepth()+1);
		        		 ran=ran.getParent();
		        	 }
	        	 }
	        	 
	        	 sortListD(newList);  //按depth排序
	        	 drawNode(newList,g);
	        	 drawLine(root,g);
//	        	 javax.swing.SwingUtilities.updateComponentTreeUI(jf);
	    	     return root;
	        }
	    
	    
		}
	}
	
	/**
	 * 遍历树，生成树节点的队列
	 * @param root
	 * @return
	 */
	public void toList(TreeNode root,List<TreeNode> list){
		
		if(root!=null){
			toList(root.getLeft(),list);
			toList(root.getRight(),list);
			list.add(root);
			System.out.println("加了一次");
		}
	}
	
	/**
	 * 按节点拥有的子树的最大深度depth来排序（用插入排序），引用传递，是否返回都无所谓
	 * @param list:要排序的树节点队列
	 */
	public void sortListD(List<TreeNode> list){
		for(int i=1;i<list.size();i++){
			for(int j=i;j>0;j--){
				if(list.get(j).getDepth()>list.get(j-1).getDepth()){  //互换
					TreeNode tem=list.set(j, list.get(j-1));
					list.set(j-1, tem);
				}
//				System.out.println(list.get(j).getCh()+"  深度 "+list.get(j).getDepth());
			}
		}
	}
	
	/**
	 *画出一个哈树的节点，并设置每个节点的x,y属性
	 * @param list：排好序的，设置了depth的节点队列
	 * @param jf：把组件加到这个界面上
	 */
	public void drawNode(List<TreeNode> list,Graphics g){
		while(true){
			int depth=0;
			int newDepth=0;
			List<TreeNode>  newList=new ArrayList<TreeNode>();//创建一个队列用来接收同层次的节点;

			depth=list.get(0).getDepth();  //取出第一个节点的depth，就是说一层一层的画
			newDepth=depth;
			
			while(newDepth==depth){
				 if(list.size()!=0){
//					  System.out.println(list.get(0).getCh()+"深度：——————————————————"+list.get(0).getDepth());
				      newList.add(list.remove(0));  //移到新的队列里
		             
				      if(list.size()!=0){
				      newDepth=list.get(0).getDepth();//list中下一个元素的depth
//				      System.out.println("移除了一个");
				      }else{
				    	  break;
				      }
				 }
	        }
			
			sortListWofF(newList);   //给一层的节点按父节点的权重排序
			
			int x=getDepthofLeft(newList.get(0))+20;   //获得首节点的x坐标
			int y=60*depth+60;                             //获得这一深度的列坐标
			//遍历newList画出一个深度的所有节点
			for(int j=0;j<newList.size();j++){
//				if(newList.get(j).getLeft()!=null){  //如果不是叶节点
//					x=(newList.get(j).getLeft().getX()+newList.get(j).getRight().getX())/2;
//					newList.get(j).setX(x);
//					System.out.println(y);
//				    newList.get(j).setY(y);
//					System.out.println(newList.get(j).getY());
//				}else{
				    newList.get(j).setX(x);
				    newList.get(j).setY(y);
//				}
				
				//画出节点，即在桌面上加上JButton
				if(newList.get(j).getLeft()!=null){
					
				    newList.get(j).draw(g, "父", newList.get(j).getX(), newList.get(j).getY()); 
				}else{
					newList.get(j).draw(g, ""+newList.get(j).getCh(), newList.get(j).getX(), newList.get(j).getY());
				}
//				System.out.println("画出了一个节点      "+x+"    "+y);
				x+=100;
			}
//			System.out.println("画出了一组");
			//死循环的出口
			if(list.size()==0){
				return;
			}
		}
	}
	
	/**
	 * 取得一个子树的最左的叶节点的x值（仅适用于哈弗曼树）
	 * @param root：子树根节点
	 * @return   最左的叶节点的x值
	 */
	public int getDepthofLeft(TreeNode root){
		if(root.getLeft()==null){
			return root.getX();
		}
		if(root!=null){
			getDepthofLeft(root.getLeft());
		}
		return 0;  //不会执行这一步
		
	}
	/**
	 * 画出每个节点间的连线
	 * @param root：树的根节点
	 * @param g：在这个布上画
	 */
	public void drawLine(TreeNode root,Graphics g){
		if(root!=null){
			drawLine(root.getLeft(),g);
			drawLine(root.getRight(),g);
			if(root.getLeft()!=null){
				Line line=new Line(root.getX()+30-20-5,root.getY()+20-20+5,root.getLeft().getX()+30-20-5,root.getLeft().getY()-20+5);
				line.draw(g);
				System.out.println("画出了一条线");
			}
			if(root.getRight()!=null){
				Line line=new Line(root.getX()+30-20-5,root.getY()+20-20+5,root.getRight().getX()+30-20-5,root.getRight().getY()-20+5);
				line.draw(g);
				System.out.println("画出了一条线");
			}
		}
	}
	
	/**
	 * 设置一个哈夫曼树的哈夫曼编码
	 * @param root
	 */
	public void setHfmcode(TreeNode root){
		if(root!=null){
		
			setHfmcode(root.getLeft());
			setHfmcode(root.getRight());
			if(root.getLeft()==null && root.getRight()==null){   //是叶节点
				System.out.println("开始设置了一个根节点的hfmm");
				TreeNode newRoot=root;
				while(root.getParent()!=null){
					TreeNode newNode=root;
					root=root.getParent();
					if(root.getLeft().equals(newNode)){//左节点
						newRoot.setHfmcode(0+newRoot.getHfmcode());
					}else{
						newRoot.setHfmcode(1+newRoot.getHfmcode());
					}
				}
//				System.out.println("设置了一个根节点的hfmm");
			}
		}
	}
	
	public void set(TreeNode root ,String code){
		if(root.getLeft()!=null){
			set(root.getLeft(),code+0);
		}
		if(root.getRight()!=null){
			set(root.getRight(),code+1);
		}
		if(root.getLeft()==null && root.getRight()==null){
			//叶节点
			root.setHfmcode(code);
		}
	}
	
	/**
	 * 获取字符串的哈弗曼编码
	 * @param s：传入的字符串
	 * @param root:传入哈夫曼树的根节点
	 * @return 字符串的哈弗曼编码
	 */
	public String hfmcodeofSting(String s,TreeNode root){
//		System.out.println("调用ofString ");
	    String code="";
		for(int i=0;i<s.length();i++ ){
			char c=s.charAt(i);
			StringBuffer sc=new StringBuffer();
	    	hfmcodeofChar(c,root,sc);
	    	code+=sc.toString();   //取得StringBuffer类中存储的String
	    }
		return code;
	}
	
	
	public void hfmcodeofChar(char c,TreeNode root,StringBuffer sc){
//		System.out.println("调用hfmcodeofChar");
		
		if(root!=null){
			hfmcodeofChar(c,root.getLeft(),sc);
			hfmcodeofChar(c,root.getRight(),sc);
			if(root.getLeft()==null && root.getRight()==null && root.getCh()==c){
				sc.append(root.getHfmcode());
//				System.out.println("sc改变啦");
				return;
			}
		}
	}
	
	/**
	 * 遍历打印叶节点
	 */
	public void print(TreeNode root){
		
		if(root!=null){
			print(root.getLeft());
			print(root.getRight());
			if(root.getLeft()==null && root.getRight()==null){
				System.out.println(root.getCh()+"的权重："+root.getWeight());
//				System.out.println("------------");
			}
		}
		
	}
	

};

package hTreeDemo;

import java.awt.Graphics;

import javax.swing.*;

/**
 * 树节点类
 * @author Administrator
 *
 */
public class TreeNode {

	private int weight;  //统计该节点的字符属性在文件中出现得频率
	private  char ch;    //节点的字符属性
	private TreeNode right;//右节点
	private TreeNode left; //左节点
	private TreeNode parent; //父节点
	private String hfmcode="";   //保存编码的属性
	private static final int width=60;   //JButton的宽度
	private static final int height=20;  //JButton的高度
	private int x,y;  //节点的定位坐标
	private int depth=1; //节点处的位置深度
	
	public TreeNode(char ch){
//		this.weight=weight;
		this.ch=ch;
	}
	
	public void setDepth(int depth){
		this.depth=depth;
	}
	
	public int getDepth(){
		return this.depth;
	}
	
	public int getX() {
		return x;
	}



	public void setX(int x) {
		this.x = x;
	}



	public int getY() {
		return y;
	}



	public void setY(int y) {
		this.y = y;
	}



	public void setWeight(int weight){
		this.weight=weight;
	}
	
	public int getWeight(){
		return this.weight;
	}
	
	public char getCh(){
		return this.ch;
	}

	public String getHfmcode() {
		return hfmcode;
	}



	public void setHfmcode(String hfmcode) {
		this.hfmcode = hfmcode;
	}



	public TreeNode getRight() {
		return right;
	}

	public void setRight(TreeNode right) {
		this.right = right;
	}

	public TreeNode getLeft() {
		return left;
	}

	public void setLeft(TreeNode left) {
		this.left = left;
	}

	public TreeNode getParent() {
		return parent;
	}

	public void setParent(TreeNode parent) {
		this.parent = parent;
	}
	
	//重写toString方法，在调用System类输出时自动调用
	public String toString(){
		return this.ch+"权重："+this.weight;
	}
	
	/**
	 * 在界面上画出JButton组件的方法（使用绝对定位）,画出父节点
	 * @param jf:界面对象
	 * @param ch：要显示的内容
	 * @param x
	 * @param y    定位点的坐标
	 */
//	public void drawRoot(JFrame jf,String ch,int x,int y){
//		JButton jbu_root=new JButton(ch);
//		jbu_root.setBounds(x, y, width, height);
//		jf.add(jbu_root);
//	}
//	
	
	
	
	/**
	 * 画哈树叶子
	 * @param jf：界面对象
	 * @param ch：要显示的内容
	 * @param x
	 * @param y   定位点的坐标
	 */
//	public void drawLeaves(JFrame jf,String ch,int x,int y){
//		JLabel jl_leaves=new JLabel(ch,JLabel.CENTER);
//		jl_leaves.setBounds(x, y, width, height);
//	//	jl_leaves.setEnabled(false);
//		jf.add(jl_leaves);
//	}
	
	
	/**
	 * 使用绝对定位画出父节点和子节点
	 * @param g:  画布对象
	 * @param ch：要显示的内容
	 * @param x
	 * @param y    定位点的坐标
	 */
	public void draw(Graphics g,String ch,int x,int y){
	
		char[] cs=ch.toCharArray();  //变为字符数组
		g.drawChars(cs, 0, cs.length,x,y);   //画出字符
		
	}
	

	

};

package hTreeDemo;
import javax.swing.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.util.List;
/**
 *  画出一个界面，输入字符串，然后输出这段字符串的哈弗曼码以及画出哈弗曼树：
 * 建一个界面类，在main方法里调用：实现字符串输入和画出哈树及输出哈弗曼码的功能。
 * @author Administrator
 *
 */
public class Interface extends JFrame{
	public Interface(){}

	/**
	 * 创建一个界面，其中调用画出哈树的方法
	 */
	public void creatUI(){
		final Demo demo=new Demo();
		this.setTitle("画哈树，出哈码 demo");
		Dimension d=new Dimension(600,600);
		this.setSize(d);
		Point p=new Point(300,300);
		this.setLocation(p);
		this.setDefaultCloseOperation(3);
		this.setLayout(null);   //使用绝对定位
		
		//用一个JTextField来接收输入的字符串
		final JTextField jt_input=new JTextField();
		this.add(jt_input);
		JButton jbu_toTree=new JButton("画哈树");
		jbu_toTree.setActionCommand("tree");
		this.add(jbu_toTree);
		JButton jbu_search=new JButton("查询");
		jbu_search.setActionCommand("search");
		jt_input.setBounds(200, 20, 200, 20);
		jbu_toTree.setBounds(410, 20, 80, 20);
		jbu_search.setBounds(500, 20, 80, 20);
		
		this.add(jbu_search);
		
		this.setVisible(true);
		g=this.getGraphics();  //获得画布对象
		
		//内部类实现动作时间监听器
		java.awt.event.ActionListener al=new  java.awt.event.ActionListener(){
			public void actionPerformed(ActionEvent e){
				if("tree".equals(e.getActionCommand())){
					list=demo.creatNodeList(jt_input.getText());//生成节点队列
					root=demo.creatTree(list,g,getInterface());   //在生成树的同时画出树的图
					demo.setHfmcode(root);
					System.out.println("生成了哈树");
				}else if("search".equals(e.getActionCommand())){
					String str=javax.swing.JOptionPane.showInputDialog("要查询的字符串是：");//弹出对话框,获得输入的字符串
					String code=demo.hfmcodeofSting(str, root);   //查询要查询的String对应的哈码
					javax.swing.JOptionPane.showMessageDialog(null,"查询结果是：哈码"+code);  //通过弹出对话框输出查询的到的哈码
				}
				
			}  
		};
		//给按钮添加监听器
		jbu_toTree.addActionListener(al);
		jbu_search.addActionListener(al);
		
		
	}
	

    
    
    public static void main(String args[]){
    	Interface face=new Interface();
    	face.creatUI();
    }
    
    public Interface getInterface(){
    	return this;
    }
    
    private Graphics g;   //画布属性
    private List<TreeNode> list;   //树节点队列
    private  TreeNode root=null;   //树的根节点

	
};

package hTreeDemo;
import java.awt.Graphics;
/**
 * 形状的统一接口
 * @author Administrator
 *
 */
public abstract class Shape {

	protected int x1,y1,x2,y2;   //两个坐标点的值
	
	public Shape(int x1,int y1,int x2,int y2){
		this.x1=x1;
		this.y1=y1;
		this.x2=x2;
		this.y2=y2;
	}
	
	public abstract void draw(Graphics g);    //画出图形的抽象方法
};

package hTreeDemo;

import java.awt.Graphics;
/**
 * 图形类的父类
 * @author Administrator
 *
 */
public class Line extends Shape{

	
	public Line(int x1, int y1, int x2, int y2) {
		super(x1, y1, x2, y2);
	}

	public void draw(Graphics g){
		g.drawLine(super.x1, super.y1, super.x2,super.y2);
	}
};