数据结构——哈夫曼树、哈夫曼编码

    /** *	node类是哈夫曼树的节点类	 
     */
    class Node{
    	public Node lNode; //左孩子
    	public Node RNode; //右孩子
    	public Node parent; //双亲节点
    	public int weight; //权值
    }
    
    
    public class haffman {
    
    	//nodes是哈夫曼树的节点数组，也就是森林F，当nodes中的只含有一个双亲节点为空的节点是，
    	//以该结点为根的树就是哈夫曼树
    	public Node[] nodes ;
    	public Scanner input;
    
    	public haffman(){
    		input = new Scanner(System.in);
    	}
    
    	public void createHuffmanTree(int n){
    		int m = 2*n-1;
    		/** * nodes数组的初始长度为2n，之所以定义长度为2n是因为，对于二叉树来说
    		 * 总节点数=度数为1的节点数+度数为2的节点数+度数为0的节点数
    		 * 在哈夫曼树中，不存在度数为1的节点，因为除了初始输入的n个节点以外，其他的节点都是由
    		 * 两个节点拼成的一个新节点，所有哈夫曼树的节点总数为 n2+n0，又 n0 = n2+1，n = n0+n0-1，n=2n0-1.
    		 * 在这里，我们避免使用nodes[0]，所以数组长度为2n。同理m也就代表着哈弗曼树的节点总数
    		 */
    		nodes = new Node[m+1];
    		nodes[0]=new Node();
    		//n0的权值为一个最大值，方便求出每次的最小值和次小值
    		nodes[0].weight =Integer.MAX_VALUE;
    		//初始化nodes数组
    		for (int i = 1;i<=m;i++){
    			nodes[i] = new Node();
    			nodes[i].parent = null;
    			nodes[i].lNode = null;
    			nodes[i].RNode = null;
    		}
    		//给n个节点赋初值
    		for(int i =1;i<=n;i++){
    			nodes[i].weight = input.nextInt();
    		}
    		/** * 循环n-1次，每次都找出两个最小值生成新的节点
    		 */
    		for(int i = n+1;i<=m;i++){
    			int s1 = 0,s2 = 0;
    			int[] arr = this.select(i-1, s1, s2);
    			s1=arr[0];
    			s2=arr[1];
    			nodes[s1].parent = nodes[i];
    			nodes[s2].parent = nodes[i];
    			nodes[i].lNode = nodes[s1];
    			nodes[i].RNode = nodes[s2];
    			nodes[i].weight = nodes[s1].weight+nodes[s2].weight;
    		}
    	}
    
    	public int[] select(int n,int s1,int s2){
    		//找出最小值和次小值，这里用了最简单的选择比较
    		for(int i = 1;i<=n ;i++){
    			if( nodes[i].parent == null)
    				if(nodes[i].weight < nodes[s1].weight)
    					s1 = i;
    		}
    
    		for(int i = 1;i<=n;i++){
    			if(nodes[i].parent == null && i!=s1)
    				if(nodes[i].weight < nodes[s2].weight)
    					s2 = i;
    		}
    		int[] arr = {s1,s2};
    		return arr;
    	}
    	/** * 生成哈夫曼编码
    	  **/
    	public void createHuffmanCode(Node[] nodes,int n){
    		String[] strs = new String[n];
    	
    		//遍历所有的叶子节点，这里的n是指实际的叶子节点个数+1，以为存放节点的数组的0号元素不用，
    		//所以要加一，切记这个n不是存放节点的数组的长度，而是叶子节点的个数+1
    		for(int i = 1;i<n;i++){
    			String str = "";
    			Node f = nodes[i].parent;
    			Node c = nodes[i];
    			//while循环访问父节点
    			while(f != null){
    
    				//判断编码 左0右1
     				if(f.lNode.equals(c))
    					str += "0";
    				else
    					str += "1";
    				//迭代c和f的值，使得while循环可以向树的遍历那样向上访问节点
    				c = f;
    				f = f.parent;
    			}
    			strs[i] = str;
    		}
    		//输出
    		for(int i = 1;i<n;i++)
    			System.out.println(strs[i]);
    
    	}
    
    	public static void main(String[] args) {
    		haffman h = new haffman();
    		int n = h.input.nextInt();
    		h.createHuffmanTree(n);
    	}
    }