Introduction and creation of Huffman tree

1、 Basic introduction

• Huffman tree , Alias “ Huffman tree ”、“ Hoffman tree ”、“ The best tree ” as well as “ The best binary tree ”

• Given n The weight of n Leaf node , Construct a binary tree , If so Weighted path length of tree (wpl) To achieve the minimum , Call such a binary tree an optimal binary tree , Also known as Huffman tree (Huffman Tree), Other books are translated as Hoffman trees .

• Huffman tree is the shortest weighted path tree , Nodes with larger weights are closer to the root .

• Several important concepts and examples of Huffman tree

  • route and The length of the path ：
    • In a tree , The path between children or grandchildren that can be reached from one node down , Called the path .
    • The number of branches in a path is called path length . If the specified number of layers of root node is 1, From the root node to the L The path length of the layer node is L-1
  • The right of the node And Weighted path length ：
    • If you assign a node in a tree to a value with a certain meaning , Then 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
  • Weighted path length of tree ： The weighted path length of a tree is defined as the sum of the weighted path lengths of all leaf nodes , Write it down as WPL(weighted path length) , The higher the weight is, the closer the node is to the root, the best binary tree is .
  • WPL The smallest is the Huffman tree

2、 Huffman tree creation idea

• A sequence of {13,7,8,3,29,6,1}, Ask to turn it into a Huffman tree .

• The steps that make up the heffman tree ;

  • Sort from small to large , Put every data , Each data is a node , Each node can be regarded as the simplest binary tree
  • Take out the two binary trees with the minimum weight of the root node
  • 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 tree root nodes
  • And the new binary tree , Sort again according to the weight of the root node , Keep repeating 1-2-3-4 Steps for , Up to the sequence , All the data is processed , You get a Huffman tree

3、 Code implementation

// Huffman tree   establish 
public class HuffmanTree {
    
    public static void main(String[] args) {
    
        int[] arr = {
    13, 7, 8, 3, 29, 6, 1};
        Node root = createHuffmanTree(arr);
        // test 
        preOrder(root);

    }

    // Write a preorder traversal method 
    public static void preOrder(Node root){
    
        if(root != null){
    
            root.preOrder();
        }else{
    
            System.out.println(" It's an empty tree , Can not traverse ");
        }
    }

    // Method of creating Huffman tree 
    /** * * @param arr  You need to create an array of Huffman trees  * @return  Created Huffman tree root node  */
    public static Node createHuffmanTree(int[] arr) {
    
        //1. For ease of operation 
        //1.1  Traverse arr Array 
        //1.2  take arr Each element of forms a Node
        //1.3  take Node Put in ArrayList in 
        List<Node> nodes = new ArrayList<>();

        for (int value : arr) {
    
            nodes.add(new Node(value));
        }

        while (nodes.size() > 1) {
    

            // Sort from small to large 
            Collections.sort(nodes);
            System.out.println("nodes =" + nodes);

            // Take out the two binary trees with the minimum weight of the root node 
            //(1) Take out the node with the smallest weight （ Binary tree )
            Node leftNode = nodes.get(0);
            //(2） Take out the node with the second smallest weight ( Binary tree )
            Node rightNode = nodes.get(1);
            //(3) Build a new binary tree 
            Node parent = new Node(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;

            //(4) from ArrayList Delete the processed binary tree 
            nodes.remove(leftNode);
            nodes.remove(rightNode);

            //(5) take parent Add to nodes
            nodes.add(parent);
        }
        // Back to Huffman's root node 
        return nodes.get(0);
    }

}

// Create node class 
// In order to make Node Object supports sorting Collections Collection sorting 
// Give Way  Node  Realization  Comparable Interface 
class Node implements Comparable<Node> {
    
    int value; // Node weights 
    Node left; // Point to left child node 
    Node right; // Point to the right child node 

    // The former sequence traversal 
    public void preOrder() {
    
        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() {
    
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node o) {
    
        // To rank from small to large , If it is sorted from large to small, it will be taken as negative 【-(this.value - o.value)】
        return this.value - o.value;
    }
}