哈夫曼树 java实现构建、查找、生成哈夫曼编码

我会带着你远行 2021-09-24 08:14 168阅读 0赞

哈夫曼树，又称最优二叉树。特点是每一个（叶子）节点都有一个权值，可以认为代表的是这个点被查询的概率。哈夫曼树要求所有（叶子节点）权值\*深度的和最短。

**为了说明方便，设节点的值与权值相等。**

![在这里插入图片描述][aHR0cDovL2hpLmNzZG4ubmV0L2F0dGFjaG1lbnQvMjAxMjAzLzExLzBfMTMzMTQzMjEwMDBFSVIuZ2lm]

#### 哈夫曼树的构建 ####

通过观察可以看出，权值小的在下，大的在上。由此可以很容易理解构建的规则：  
将所有的节点（或者说是只有根节点的子树）放入一个集合，每次取出两个最小的节点合成一个新子树并放入集合，循环，直到集合中只剩最后一个元素。

jdk已经提供了优先队列的实现，所以实现起来非常简单

创建测试代码，创建节点类

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.PriorityQueue;
    import java.util.Queue;
    
    public class HuffmanTree { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		List<Integer> val = new ArrayList<Integer>();
    		
    		val.add(2);
    		val.add(4);
    		val.add(5);
    		val.add(7);
    		
    		HuffmanTree tree = new HuffmanTree();
    		Node node = tree.init(val);
    		
    	}
    	
    	private class Node{ 
    		Node left;
    		Node right;
    		Integer value = null;//null代表无值节点
    		Integer weight;
    		boolean isLeaf;//是否为叶子节点，所有实际值都在叶子节点上
    		public Node(Node left, Node right, Integer value, Integer weight, boolean isLeaf) { 
    			super();
    			this.left = left;
    			this.right = right;
    			this.value = value;
    			this.weight = weight;
    			this.isLeaf = isLeaf;
    		}
    		
    	}
    	
    }

哈夫曼树构建

//构建哈夫曼树
    	public Node init(List<Integer> val) { 
    		Queue<Node> queue = new PriorityQueue<Node>((n1, n2) -> n1.weight - n2.weight);
    		val.stream().forEach(v -> queue.add(new Node(null, null, v, v, true)));
    		
    		while(queue.size() > 1) { 
    			Node n1 = queue.poll();
    			Node n2 = queue.poll();
    			queue.add(new Node(n1, n2, null, n1.weight + n2.weight, false));
    		}
    		
    		return queue.poll();
    	}

#### 查找 ####

网上相关资料比较少，只看到有一篇文章说了要用广度优先遍历。由于权值低的点深度都会相对较低，所以这应该是正确的。

查找

public boolean has(Node node, Integer value) { 
    		Queue<Node> queue = new LinkedList();
    		queue.add(node);
    		
    		while(queue.size() > 0) { 
    			Node temp = queue.poll();
    			if(temp.isLeaf && temp.value == value) { 
    				return true;
    			}else { 
    				if(temp.left != null)
    					queue.add(temp.left);
    				if(temp.right != null)
    					queue.add(temp.right);
    			}
    		}
    		
    		return false;
    	}

#### 生成哈夫曼编码 ####

从根节点到目标节点，按照依次经过的是左子树还是右子树，分别填0或1 。  
一个很直观的方法是，遍历每一个叶子节点，再从下向上逆向输出哈夫曼编码。但是这就要求节点为双向的，改起来有点麻烦。仔细一想，只要用前序遍历改一下就可以了

public void printHuffmanCode(Node node) { 
    		Stack<Integer> stack = new Stack();
    		recHuffmanCode(node, stack);
    	}
    	
    	private void recHuffmanCode(Node node, Stack<Integer> stack) { 
    		if(node == null)return;
    		if(node.isLeaf) { 
    			System.out.println(node.value + ": " + stack);
    		}
    		stack.add(0);
    		recHuffmanCode(node.left, stack);
    		stack.pop();
    		
    		stack.add(1);
    		recHuffmanCode(node.right, stack);
    		stack.pop();
    	}

经过测试后发现，其实中序和后序也是可行的  
中序

private void recHuffmanCode_mid(Node node, Stack<Integer> stack) { 
    		if(node == null)return;
    		
    		stack.add(0);
    		recHuffmanCode(node.left, stack);
    		stack.pop();
    		
    		if(node.isLeaf) { 
    			System.out.println(node.value + ": " + stack);
    		}
    		
    		stack.add(1);
    		recHuffmanCode(node.right, stack);
    		stack.pop();
    		
    	}

最后附上完整代码

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.PriorityQueue;
    import java.util.Queue;
    import java.util.Stack;
    
    public class HuffmanTree { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		List<Integer> val = new ArrayList<Integer>();
    		
    		val.add(2);
    		val.add(4);
    		val.add(5);
    		val.add(7);
    		
    // val.add(10);
    // val.add(11);
    // val.add(12);
    // val.add(13);
    		
    		HuffmanTree tree = new HuffmanTree();
    		Node node = tree.init(val);
    		
    		tree.prevPrint(node);
    		
    		System.out.println(tree.has(node, 8));
    		
    		tree.printHuffmanCode(node);
    	}
    	
    	public void printHuffmanCode(Node node) { 
    		Stack<Integer> stack = new Stack();
    		recHuffmanCode_mid(node, stack);
    	}
    	
    	private void recHuffmanCode(Node node, Stack<Integer> stack) { 
    		if(node == null)return;
    		if(node.isLeaf) { 
    			System.out.println(node.value + ": " + stack);
    		}
    		stack.add(0);
    		recHuffmanCode(node.left, stack);
    		stack.pop();
    		
    		stack.add(1);
    		recHuffmanCode(node.right, stack);
    		stack.pop();
    	}
    	
    	private void recHuffmanCode_mid(Node node, Stack<Integer> stack) { 
    		if(node == null)return;
    		
    		stack.add(0);
    		recHuffmanCode(node.left, stack);
    		stack.pop();
    		
    		if(node.isLeaf) { 
    			System.out.println(node.value + ": " + stack);
    		}
    		
    		stack.add(1);
    		recHuffmanCode(node.right, stack);
    		stack.pop();
    		
    	}
    	
    	public Node init(List<Integer> val) { 
    		Queue<Node> queue = new PriorityQueue<Node>((n1, n2) -> n1.weight - n2.weight);
    		val.stream().forEach(v -> queue.add(new Node(null, null, v, v, true)));
    		
    		while(queue.size() > 1) { 
    			Node n1 = queue.poll();
    			Node n2 = queue.poll();
    			queue.add(new Node(n1, n2, null, n1.weight + n2.weight, false));
    		}
    		
    		return queue.poll();
    	}
    
    	public void prevPrint(Node node) { 
    		if(node == null)return;
    		System.out.println("value: " + node.value + ", weight: " + node.weight);
    		prevPrint(node.left);
    		prevPrint(node.right);
    	}
    	
    	public boolean has(Node node, Integer value) { 
    		Queue<Node> queue = new LinkedList();
    		queue.add(node);
    		
    		while(queue.size() > 0) { 
    			Node temp = queue.poll();
    			if(temp.isLeaf && temp.value == value) { 
    				return true;
    			}else { 
    				if(temp.left != null)
    					queue.add(temp.left);
    				if(temp.right != null)
    					queue.add(temp.right);
    			}
    		}
    		
    		return false;
    	}
    	
    	private class Node{ 
    		Node left;
    		Node right;
    		Integer value = null;//null代表无值节点
    		Integer weight;
    		boolean isLeaf;//是否为叶子节点，所有实际值都在叶子节点上
    		public Node(Node left, Node right, Integer value, Integer weight, boolean isLeaf) { 
    			super();
    			this.left = left;
    			this.right = right;
    			this.value = value;
    			this.weight = weight;
    			this.isLeaf = isLeaf;
    		}
    		
    	}
    	
    }

[aHR0cDovL2hpLmNzZG4ubmV0L2F0dGFjaG1lbnQvMjAxMjAzLzExLzBfMTMzMTQzMjEwMDBFSVIuZ2lm]: /images/20210923/5c9a92f0d972476ca2fd58a76ec261a2.png