Huffman 编码Java实现（贪心算法）

﹏ヽ暗。殇╰゛Y 2023-02-14 10:23 2阅读 0赞

# Huffman 编码 #

## 问题分析 ##

*  可参考 [数据结构——HuffmanTree][HuffmanTree]

## Java 代码实现 ##

> 内含详细注释

/* * 若尘 */
    package huffmancode;
    
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.Scanner;
    
    /** * 哈夫曼编码 * @author ruochen * @version 1.0 */
    public class Test { 
    
    	/** 用来存放节点值 */
    	private static LinkedList<HuffNode> huffList = new LinkedList<HuffNode>();
    	
    	public static void main(String[] args) { 
    		// 第一个输入元素个数
    		// 然后换行输入 对应权值 元素
    		/** 如 * 5 * 10 a * 6 b * 4 c * 19 d * 1 e * **/
    		System.out.println("Please input: ");
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt();
    		for (int i = 0; i < n; i++) { 
    			huffList.add(new Test().new HuffNode(sc.nextInt(), sc.next()));
    		}
    		huffmanCode();
    		decode(huffList.get(0), "");
    	}
    	
    	class HuffNode implements Comparable<HuffNode> { 
    		/** 权值 */
    		int value;
    		String name;
    		/** 左孩子节点 */
    		HuffNode lChild = null;
    		/** 右孩子节点 */
    		HuffNode rChild = null;
    		
    		public HuffNode(int value, String name) { 
    			this.value = value;
    			this.name = name;
    		}
    		
    		public HuffNode(HuffNode lChild, HuffNode rChild) { 
    			this.lChild = lChild;
    			this.rChild = rChild;
    			// 权值之和，即合并两个叶子节点
    			this.value = lChild.value + rChild.value;
    		}
    		
    		/** * 按照权值大小非递减序列 * @param o * @return */
    		@Override
    	    public int compareTo(HuffNode o) { 
    	    	if (this.value < o.value) { 
    	    		return -1;
    	    	} else if (this.value == o.value) { 
    	    		return 0;
    	    	} else { 
    	    		return 1;
    	    	}
    	    }
    	}
    	
    	/** * 哈夫曼编码 */
    	public static void huffmanCode() { 
    		if (huffList.size() == 1) { 
    			return ;
    		}
    		while (huffList.size() > 1) { 
    			// 排序
    			Collections.sort(huffList);
    			// 将前两个节点进行合并
    			HuffNode node = new Test().new HuffNode(huffList.get(0), huffList.get(1));
    			// 删除前两个节点
    			huffList.remove();
    			huffList.remove();
    			// 将新生成的节点添加到列表中
    			huffList.add(node);
    		}
    		// 编码完成后，此时huffList中只剩一个根节点
    	}
    	
    
    	/** * 解码 * @param n * @param code */
    	public static void decode(HuffNode n, String code) { 
    		if ((n.lChild == null) && (n.rChild == null)) { 
    			// 叶子节点， 此时输出其对应编码
    			System.out.print(n.name + "--->" + code);
    			System.out.println();
    			return ;
    		}
    		// 遍历左子树
    		decode(n.lChild, code + "0");
    		// 遍历右子树
    		decode(n.rChild, code + "1");
    		return ;
    	}
    }

Please input: 
    5
    10 a
    6 b
    4 c
    19 d
    1 e
    d--->0
    a--->10
    e--->1100
    c--->1101
    b--->111

[HuffmanTree]: https://blog.csdn.net/qq_29339467/article/details/103681071