1. Basic introduction

  1. 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 an optimal binary Tree, also called Huffman Tree, and also called Huffman Tree.

  2. Huffman tree is a tree with the shortest weight path length, and the node with higher weight is closer to the root

2. Several important concepts and examples of Huffman tree

1) Path and path length: In a tree, the path between children or grandchildren nodes that can be reached from one node down is called path. pathways

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

3) The weighted path length of the tree: The weighted path length of the tree is defined as the sum of the weighted path lengths of all leaf nodes, denoted as WPL(Weighted Path Length). The binary tree with higher weight is the optimal one.

3. Steps to form a Huffman tree

  1. Sort from smallest to largest, and treat every data, every data as a node, and every node can be viewed as the simplest binary tree

  2. Extract the two binary trees with the lowest root weights

  3. To form a new binary tree, the weight of the root node of the new binary tree is the sum of the weight of the previous two binary root nodes

  4. Then the new binary tree is sorted again by the weight of the root node, and the steps of 1-2-3-4 are repeated until all the data in the sequence are processed and a Huffman tree is obtained

Code 4.

4.1 Creating a node Class

To keep the Node object sorting the Collections collection

Let Node implement the Comparable interface

class Node implements Comparable<Node> {
	int value; // Node weights
	char c; / / character
	Node left; // point to the left child
	Node right; // point to the right child

	// Write a preorder traversal
	public void preOrder(a) {
		System.out.println(this);
		if(this.left ! =null) {
			this.left.preOrder();
		}
		if(this.right ! =null) {
			this.right.preOrder(); }}public Node(int value) {
		this.value = value;
	}

	@Override
	public String toString(a) {
		return "Node [value=" + value + "]";
	}

	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		// Indicates the order from smallest to largest
		return this.value - o.value; }}Copy the code

4.2 Method of creating a Huffman tree

/ * * * *@paramArr needs to create an array of Huffman trees *@returnCreate the root node of the Huffman tree */
	public static Node createHuffmanTree(int[] arr) {
		// The first step is for ease of operation
		// 1. Iterate through the ARR array
		// 2. Form each element of arR into a Node
		// 3. Add nodes to the ArrayList
		List<Node> nodes = new ArrayList<Node>();
		for (int value : arr) {
			nodes.add(new Node(value));
		}
		
		// The process we are dealing with is a circular process
		
		
		while(nodes.size() > 1) {
		
			// Sort from small to large
			Collections.sort(nodes);
			
			System.out.println("nodes =" + nodes);
			
			// Select the two binary trees with the lowest root weights
			//(1) select the node with the lowest weight (binary tree)
			Node leftNode = nodes.get(0);
			// Select the node with the second lowest weight (binary tree)
			Node rightNode = nodes.get(1);
			
			// create a new binary tree
			Node parent = new Node(leftNode.value + rightNode.value);
			parent.left = leftNode;
			parent.right = rightNode;
			
			//(4) Delete the processed binary tree from ArrayList
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			//(5) Add parent to Nodes
			nodes.add(parent);
		}
		
		// Return the root node of the Huffman tree
		return nodes.get(0);
		
	}
Copy the code

4.3 Write a preorder traversal method

public static void preOrder(Node root) {
		if(root ! =null) {
			root.preOrder();
		}else{
			System.out.println("It is an empty tree, cannot be traversed."); }}Copy the code

4.4 test

public static void main(String[] args) {
		int arr[] = { 13.7.8.3.29.6.1 };
		Node root = createHuffmanTree(arr);
		
		// Test
		preOrder(root); //
		
	}
Copy the code