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 Lth layer node is L1
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 1234 until all the data in the sequence are processed to get a Huffman tree
Steps:

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

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 Autogenerated 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 Autogenerated 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]