huffman tree

Basic introduction

Given n weights as n leaf nodes, a binary tree is constructed. If the weighted path length (wpl) of the tree reaches the minimum, such a binary tree is called the optimal binary tree, also known as Huffman tree. Other books are translated as Huffman tree.

In other words, Huffman tree is the tree with the shortest weighted path length, and the node with larger weight is closer to the root

Some concepts

Path and path length: the path between children or grandchildren that can be reached from one node down in a tree is called path. The number of branches in a path is called the path length. If the specified number of layers of the root node is 1, the path length from the root node to the L-th layer node is L-1

Node weight and weighted path length: if a node in the tree is assigned a value with a certain meaning, this value is called the weight of the node. The weighted path length of a node is the product of the path length from the root node to the node and the weight of the node

for instance:

Node weight: 13 14 5 16

Take the weighted path length of node 13 as an example. Its path is 2 from the first layer to the third layer, so it is 13 * 2 = 26

Weighted path length of the tree: the weighted path length of the tree is specified as the sum of the weighted path lengths of all leaf nodes, which is recorded as WPL(weighted path length). The binary tree with greater weight and closer to the root node is the optimal binary tree.

The idea of creating Huffman tree

Given a sequence {13,7,8,3,29,6,1}, we need to convert it into a Huffman tree

Steps:

1. Sort from small to large, and treat each data as a node. Each node can be regarded as the simplest binary tree

2. Take out the two binary trees with the smallest weight of the root node

3. Form a new binary tree. The weight of the root node of the new binary tree is the sum of the weight of the root node of the previous two binary trees

4. Sort the new binary tree again according to the weight of the root node, and repeat the steps of 1-2-3-4 until all the data in the sequence are processed to get a Huffman tree

Steps:

1. Sort 1,3,4,7,8,13,29

2. Pick out 1 and 3 to build a new binary tree

Combined with No. 6

7,8 is smaller than 10. Take it out alone to form a new binary tree, and so on

code

package huffman tree ;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTree {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[] = {13,7,8,3,29,6,1};
		Node node = createHuffmanTree(arr);
		preOrder(node);
	}
	
	
	//Method of creating Huffman tree
	public static Node createHuffmanTree(int[] arr) {
		//First, take out all the elements in the array and build it into Node type
		//Put it into ArrayList to sort
		List<Node> nodes = new ArrayList<Node>();
		for(int value : arr){
			nodes.add(new Node(value));
		}
		while(nodes.size() > 1){
			//We are from small to large
			Collections.sort(nodes);
			System.out.println(nodes);
			//Take the two binary trees with the smallest weight of the root node
			//Take out the smallest binary tree node (binary tree)
			Node leftNode = nodes.get(0);
			Node rightNode = nodes.get(1);
			//Build a new binary tree
			Node parent = new Node(leftNode.value+rightNode.value);
			parent.left = leftNode;
			parent.right = rightNode;
			//Delete the processed binary tree from our ArrayList
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			
			//Add the parent to the nodes collection
			nodes.add(parent);
			System.out.println("After the first treatment"+nodes);
		}
		//Returns the root node of the Huffman tree
		return nodes.get(0);
	}
	//Preamble convenience method
	public static void preOrder(Node root) {
		if(root != null){
			root.preOrder();
		}else
		{
			System.out.println("Empty tree");
		}
	}

}
//Create node class
//To enable Node to support sorting Collections
//Let Node implement Comparable interface
class Node implements Comparable<Node>{
	int value;//Node weight
	Node left;//Point to the left child node
	Node right;//Point to the right child node
	public Node(int value) {
		this.value = value;
	}
	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}
	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		return this.value - o.value;//Sort from small to large
	}
	
	//Preorder traversal method
	public void preOrder() {
		System.out.println(this);
		if(this.left != null){
			this.left.preOrder();
		}
		if(this.right != null){
			this.right.preOrder();
		}
	}
	
}

results of enforcement

[Node [value=1], Node [value=3], Node [value=6], Node [value=7], Node [value=8], Node [value=13], Node [value=29]]
After the first treatment[Node [value=6], Node [value=7], Node [value=8], Node [value=13], Node [value=29], Node [value=4]]
[Node [value=4], Node [value=6], Node [value=7], Node [value=8], Node [value=13], Node [value=29]]
After the first treatment[Node [value=7], Node [value=8], Node [value=13], Node [value=29], Node [value=10]]
[Node [value=7], Node [value=8], Node [value=10], Node [value=13], Node [value=29]]
After the first treatment[Node [value=10], Node [value=13], Node [value=29], Node [value=15]]
[Node [value=10], Node [value=13], Node [value=15], Node [value=29]]
After the first treatment[Node [value=15], Node [value=29], Node [value=23]]
[Node [value=15], Node [value=23], Node [value=29]]
After the first treatment[Node [value=29], Node [value=38]]
[Node [value=29], Node [value=38]]
After the first treatment[Node [value=67]]
Node [value=67]
Node [value=29]
Node [value=38]
Node [value=15]
Node [value=7]
Node [value=8]
Node [value=23]
Node [value=10]
Node [value=4]
Node [value=1]
Node [value=3]
Node [value=6]
Node [value=13]