二叉树之哈夫曼树

男娘i 2022-07-13 14:14 172阅读 0赞

一、定义  
节点之间的路径长度：在树中从一个结点到另一个结点所经历的分支，构成了这两个结点间的路径上的经过的分支数称为它的路径长度。  
树的路径长度：从树的根节点到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。  
结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。  
结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。  
树的带权路径长度(Weighted Path Length of Tree：WPL)：定义为树中所有叶子结点的带权路径长度之和。

最优二叉树：从已给出的目标带权结点(单独的结点) 经过一种方式的组合形成一棵树.使树的权值最小.。最优二叉树是带权路径长度最短的二叉树。根据结点的个数，权值的不同，最优二叉树的形状也各不相同。它们的共同点是：带权值的结点都是叶子结点。权值越小的结点，其到根结点的路径越长，深度越大。

![20170112144334312][]

如，给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如上图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：  
(a)WPL=7\*2+5\*2+2\*2+4\*2=36  
(b)WPL=7\*3+5\*3+2\*1+4\*2=46  
(c)WPL=7\*1+5\*2+2\*3+4\*3=35

可以验证其中(c)树的WPL最小，可以验证，它就是哈夫曼树。

注意：  
① 叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。  
② 最优二叉树中，权越大的叶子离根越近。  
③ 最优二叉树的形态不唯一，WPL最小。

二、利用哈夫曼树来进行哈夫曼编码

哈夫曼编码通常用来实现数据压缩，编码时，我们通常希望出现次数最多的字符所占的内存位数最少。但是如果字符位太少又会导致他能够表示的实际字符数不够，因为每一位只有0和1两个状态，n位有2的n次方个状态。所以采用定长编码时数据压缩率不是很高。使用哈夫曼编码可以解决这个问题。

下面是一个编码实例：

原句子为SUSIE SAYS IT IS EASY

句子中每个字符出现次数

![Center][]

相应的哈夫曼编码：

![Center 1][]

可以看出出现频率越高的字符所用的编码字符数越少。

创建哈夫曼树：

1.设计节点类Node：

Node中包含两个数据项：存储的字符和字符出现的频率（也就是权值）。

2、为每一个字符创建一个相应的Node对象，并把为其创建一个单独的树，树的根就是当前的节点。N个字符就创建N个相应的树。

3、把这些树都插入一个优先级队列中，按照权值排列。权值小的优先级高，排在队列的前方。每次移除队列的一项时，都是移除权值最小的那颗树。

4、从优先级队列中按顺序移除两个树，并将其作为一个新节点的两个子节点。新节点的权值（频率）是这两个子节点的权值和，至于新节点中存储的字符可以设为空。

5、把第四步形成的新树重新插入优先级队列中（自动插入到了相应位置）。

6、重复第四步和第五步，直到队列中只剩一棵树，这棵树就是要创建的哈夫曼树。

图解：

![20170112152219863][]

最后将图h中的两个树合并为1个就得到哈夫曼树。

根据哈夫曼树得到哈夫曼编码表：

所有字符在哈夫曼树中都被表示为树中的叶结点。遍历所有叶结点即可得到相应字符的哈夫曼编码，从而形成编码表。编码规则：从根节点到叶结点，记录向左和向右走的顺序，向左走用0表示，向右走用1表示。到达叶结点时的01字符串就是对应的哈夫曼编码。

例如字符U的编码是01111，字符Y的编码是1110。

代码实现：

Node节点代码，此处权值放到了Tree中。

class Node {
    	public char cchar;      //存储的字符
    	public Node leftChild;         // 左子结点引用
    	public Node rightChild;        // 右子节点引用
    
    	public Node() {
    	}
    
    	public Node(char c) {
    		cchar = c;
    	}
    
    	public void displayNode()      // 输出节点信息
    	{
    		System.out.print('{');
    		System.out.print(cchar);
    		System.out.print("} ");
    	}
    }

Tree代码：

class Tree implements Comparable {
    	public Node root;             // 根节点
    	public int weight;            // 权重
    
    	// -------------------------------------------------------------
    	public Tree()                  // 无参构造函数
    	{
    		root = null;
    	}      
    
    	public String toString() {//转换为字符串
    		return root.cchar + "";
    	}
    
    	// -------------------------------------------------------------
    	public void traverse(int traverseType) { // 三种遍历
    		switch (traverseType) {
    		case 1:
    			System.out.print("\nPreorder traversal: ");
    			preOrder(root);
    			break;
    		case 2:
    			System.out.print("\nInorder traversal:  ");
    			inOrder(root);
    			break;
    		case 3:
    			System.out.print("\nPostorder traversal: ");
    			postOrder(root);
    			break;
    		}
    		System.out.println();
    	}
    
    	// -------------------------------------------------------------
    	private void preOrder(Node localRoot) {//先序遍历
    		if (localRoot != null) {
    			System.out.print(localRoot.cchar + " ");
    			preOrder(localRoot.leftChild);
    			preOrder(localRoot.rightChild);
    		}
    	}
    
    	// -------------------------------------------------------------
    	private void inOrder(Node localRoot) {//中序遍历
    		if (localRoot != null) {
    			System.out.print("(");
    			inOrder(localRoot.leftChild);
    			System.out.print(localRoot.cchar + " ");
    			inOrder(localRoot.rightChild);
    			System.out.print(")");
    		}
    	}
    
    	// -------------------------------------------------------------
    	private void postOrder(Node localRoot) {//后序遍历
    		if (localRoot != null) {
    			postOrder(localRoot.leftChild);
    			postOrder(localRoot.rightChild);
    			System.out.print(localRoot.cchar + " ");
    		}
    	}
    
    	// -------------------------------------------------------------
    	public void displayTree() {               //利用栈输出树
    		Stack globalStack = new Stack();
    		globalStack.push(root);
    		int nBlanks = 32;
    		boolean isRowEmpty = false;
    		System.out
    				.println("......................................................");
    		while (isRowEmpty == false) {
    			Stack localStack = new Stack();
    			isRowEmpty = true;
    
    			for (int j = 0; j < nBlanks; j++)
    				System.out.print(' ');
    
    			while (globalStack.isEmpty() == false) {
    				Node temp = (Node) globalStack.pop();
    				if (temp != null) {
    					System.out.print(temp.cchar);
    					localStack.push(temp.leftChild);
    					localStack.push(temp.rightChild);
    
    					if (temp.leftChild != null || temp.rightChild != null)
    						isRowEmpty = false;
    				} else {
    					System.out.print("--");
    					localStack.push(null);
    					localStack.push(null);
    				}
    				for (int j = 0; j < nBlanks * 2 - 2; j++)
    					System.out.print(' ');
    			}  // end while globalStack not empty
    			System.out.println();
    			nBlanks /= 2;
    			while (localStack.isEmpty() == false)
    				globalStack.push(localStack.pop());
    		}  // end while isRowEmpty is false
    		System.out
    				.println("......................................................");
    	}  // end displayTree()
    		// -------------------------------------------------------------
    
    	@Override
    	public int compareTo(Object o) {  //重写比较函数
    		if (o == null) {
    			return -1;
    		}
    		return weight - ((Tree) o).weight;
    	}
    }  // end class Tree
    // //

Huffman编码主体：

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map;
    import java.util.PriorityQueue;
    import java.util.Queue;
    import java.util.Set;
    import java.util.TreeMap;
    
    public class Huffman {
    	public static Map<Character, String> map_char_code;//key为字符（Character是char类型的类封装），value为相应的哈夫曼编码
    	public static Map<String, Character> map_code_char;//key为哈夫曼编码，value为相应的字符
    	static {
    		map_char_code = new HashMap<Character, String>(); // 编码用代码表
    		map_code_char = new HashMap<String, Character>(); // 解码用代码表
    	}
    
    	// 编码分为四步
    	// 1.统计字符频率
    	// 2.生成Huffman树
    	// 3.生成编解码用代码表
    	// 4.编码字符串
    	
    	//编码函数
    	public static String encode(String str) {
    		char[] cchar = str.toCharArray();//将待编码的字符串转为字符数组。
    
    		// 1.统计字符频率
    		TreeMap<Character, Integer> map = new TreeMap<Character, Integer>();
    		//TreeMap是有序的，按照key来进行排序。Character类中实现了Comparable接口，该接口中只有一个
    		//public int compareTo(T o);方法，对象的大小关系由返回值来确定，返回负整数，零，正整数表示当前对象小于，
    		//等于，大于指定对象。这里按照字典顺序排序。
    		for (int i = 0; i < cchar.length; i++) {
    			if (map.containsKey(cchar[i])) {//map中包含该字符
    				map.put(cchar[i], map.get(cchar[i]).intValue() + 1);//统计数加1
    			} else {
    				map.put(cchar[i], 1);//加入新字符，频率设为1
    			}
    		}
    
    		// 2.生成Huffman树
    		// 先由所有字符生成单节点树
    		// 然后根据优先级合成单节点树为一棵树
    		Queue<Tree> forest = new PriorityQueue<Tree>();//定义一个队列，存储数据类型为树
    		Set<Map.Entry<Character, Integer>> set = map.entrySet();
    /*		Set<Map.Entry<Character, Integer>> set = map.entrySet();返回映射所包含的映射关系的Set集合（一个关系就是一个键-值对），就是把(key-value)作为一个整体一对一对地存放到Set集合当中的。entrySet是 键-值对的集合，Set里面的类型是Map.Entry
    */		
    		Iterator<Map.Entry<Character, Integer>> it = set.iterator();//转为迭代器
    		while (it.hasNext()) {                // 遍历迭代器，生成单节点树
    			Map.Entry<Character, Integer> en = it.next();
    			Tree temp = new Tree();
    			temp.root = new Node(en.getKey());//创建相应节点为树的根
    			temp.weight = en.getValue();//设置权重
    			forest.add(temp);//加入队列
    			//因为Tree实现了Comparable接口，重写了CompareTo的方法，所以在加入队列时，会比较权重。最后形成基于权重的优先级队列。
    		}
    		while (forest.size() > 1) { // 把单节点树合并为一棵树
    			Tree t1 = forest.remove();//移除第一个数据项
    			Tree t2 = forest.remove();//移除第二个数据项
    			Tree t3 = new Tree();
    			t3.root = new Node();
    			t3.weight = t1.weight + t2.weight;//新节点的权重是子节点之和
    			t3.root.leftChild = t1.root;
    			t3.root.rightChild = t2.root;
    			forest.add(t3); //重新加入队列
    		}
    		Tree t = forest.remove(); // 获得队列中最后一棵树，也就是哈夫曼树
    
    		// 3.生成编码和解码用的map
    		String code = "";
    		preOrder(t.root, code, map_char_code, map_code_char);
    
    		// 4.编码字符串
    		StringBuffer output = new StringBuffer();
    		for (int i = 0; i < cchar.length; i++) {//获取每个字符的哈夫曼编码
    			output.append(map_char_code.get(cchar[i]));//append(String str)，连接一个字符串到末尾。
    		}
    		return output.toString();//转为字符串
    	}
    
    	// 遍历Huffman树生成编码和解码代码表
    	private static void preOrder(Node localRoot, String code,
    			Map<Character, String> map_char_code,
    			Map<String, Character> map_code_char) {
    		if (localRoot != null) {
    			if (localRoot.cchar != '\0') {//'\0'代表空字符,在哈夫曼树，非叶节点没存储数据，相应的cchar为空。所以程序只操作了叶结点
    				map_char_code.put(localRoot.cchar, code);//加入编码表
    				map_code_char.put(code, localRoot.cchar);//加入解码表
    			}
    			preOrder(localRoot.leftChild, code + "0", map_char_code,
    					map_code_char);//向左走code末尾加上0
    			preOrder(localRoot.rightChild, code + "1", map_char_code,
    					map_code_char);//向右走code末尾加上1
    		}
    	}
    
    	// 解码
    	// 根据解码代码表还原信息
    	public static String decode(String str) {
    		StringBuffer result = new StringBuffer();
    		StringBuffer sb = new StringBuffer();
    		for (int i = 0; i < str.length(); i++) {
    			sb.append(str.charAt(i));
    			if (map_code_char.get(sb.toString()) != null) {//获取编码对应的字符
    				result.append(map_code_char.get(sb.toString()));
    				sb = new StringBuffer();
    			}
    		}
    		return result.toString();
    	}
    
    	public static void main(String[] args) {
    		String code = encode("SUSIE SAYS IT IS EASY!");
    		System.out.println(code);
    		String str = decode(code);
    		System.out.println(str);
    	} 
    
    	// -------------------------------------------------------------
    
    	public static String getString() throws IOException {
    		InputStreamReader isr = new InputStreamReader(System.in);
    		BufferedReader br = new BufferedReader(isr);
    		String s = br.readLine();
    		return s;
    	}
    }
    // =============================================================================

[20170112144334312]: /images/20220713/81b61c8045db4331bcea9e8afe8dc9c4.png
[Center]: /images/20220713/ac8e9a86d4a7417aa74d2ee82ef36821.png
[Center 1]: /images/20220713/1e8111eae8a14e61b05709407a9f5b6f.png
[20170112152219863]: /images/20220713/56f84dfde3e6416898d9ea887fde3aee.png