---

One 、 What is a Huffman tree ？

   Given N The weight of N Leaf node , Construct a binary tree , If the weighted path length of the tree (WPL) To achieve the minimum , Call such a binary tree an optimal binary tree , Also known as Huffman tree (Huffman Tree). Huffman tree is the tree with the shortest weight path length , Nodes with larger weights are closer to the root .
chart 1 A Huffman tree

1. Path and path length

   In a tree , The path between children or grandchildren that can be reached from one node down , Called the path .
For example, figure 1 Root node to b The path between nodes is called a path .

   In one path , Every time we pass through a node , The length of the path should be added 1 . 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.
For example, figure 1 Root node to c The path length of the node is 4 - 1 = 3

2. Node weight 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 .
For example, figure 1 in abcd The weights of nodes are 12、5、6、21
   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 example, figure 1 node c The weighted path length of is 3 * 6 = 18

3. 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.
For example, the tree in the figure above WPL = （5 + 6）* 3 + 12 * 2 + 21 = 78

Two 、 Create the Huffman tree

1. Graphic creation process

   Suppose there is n Weight , The Huffman tree constructed has n Leaf node . n The weights are set to w1、w2、…、wn, The construction rule of Huffman tree is ：

For example, there are four leaf nodes a b c d The weights are 12、5、6、21
Create the forest in front of Huffman tree as follows

  (1) take w1、w2、…,wn Think of it as having n A forest of trees ( Each tree has only one node );

  (2) Select the tree with the least weight of two root nodes in the forest to merge , As the left side of a new tree 、 Right subtree , And the weight of the root node of the new tree is its left 、 Right subtree root node weight sum ;

Take out... From the forest b c node Form a new tree M

  (3) Remove the two selected trees from the forest , And add new trees to the forest ;

New tree M After adding to the forest The forest is as follows

(4) repeat (2)、(3) Step , Until there is only one tree left in the forest , This tree is the obtained Huffman tree .
  **  4.1 Repeat step （2）

The right to take out in the forest is 11 And a Nodes form a new tree N

  **  4.2 Repeat step （3）

New tree N Add to forest The forest is as follows

  **  4.3 Repeat step （2）

Take out... From the forest b Nodes and weights are 23 The nodes form a new tree S

Then a new tree S That's the Huffman tree we're going to create

2. Code implementation

   In the process of creating Huffman tree , To ensure that the minimum number of nodes taken from the forest each time , Here, a quick sort algorithm is used , Before taking out the node every time , Rearrange the trees in the forest according to the weight from small to large

The structure of the node is as follows :

class Node implements Comparable<Node> {
    
    private int element; // The right of the node 
    private Node left; // The left subtree of the node 
    private Node right; // The right subtree of the node 

    // Constructors 
    public Node(int aElement) {
    
        this.element = aElement;
    }

    public int getElement() {
    
        return element;
    }

    public void setElement(int element) {
    
        this.element = element;
    }

    public Node getLeft() {
    
        return left;
    }

    public void setLeft(Node left) {
    
        this.left = left;
    }

    public Node getRight() {
    
        return right;
    }

    public void setRight(Node right) {
    
        this.right = right;
    }

    // The former sequence traversal 
    public void preOrder() {
    
        System.out.print(this + " ");
        if (this.getLeft() != null) {
    
            this.getLeft().preOrder();
        }
        if (this.getRight() != null) {
    
            this.getRight().preOrder();
        }
    }

    @Override
    public String toString() {
    
        return element + "";
    }


    @Override
    public int compareTo(Node o) {
    
        return this.getElement() - o.getElement(); // From small to large 
    }
}

The complete code is as follows ：

package com.xx.huffmantree;

import java.util.*;

/** * @author  Xie Xin  * @version 1.0 * @date 2021/12/7 16:31 *  Huffman tree  */
public class HuffmanTreeDemo {
    
    public static void main(String[] args) {
    
        int[] arr = {
    12, 5, 6, 21};
        HuffmanTree huffmanTree = new HuffmanTree();
        Node root = huffmanTree.creTree(arr);
        huffmanTree.preOrder(root);
    }
}

class HuffmanTree {
    

    public Node creTree(int[] aArr) {
    

        List<Node> list = new ArrayList<>(); // Used to hold array elements 

        // Put the array in list in 
        for (int element : aArr) {
    
            list.add(new Node(element));
        }

        while (list.size() > 1) {
     // Loop to create tree 
            Collections.sort(list); // Sort from small to large 

            // from list Take out two nodes from the small 
            Node left = list.get(0);
            Node right = list.get(1);

            // Initialize the root node of the small tree 
            Node root = new Node(left.getElement() + right.getElement()); // The root node of the small tree is the left and right subtree nodes element It's worth it and 

            // Build a small tree 
            root.setLeft(left);
            root.setRight(right);

            list.add(root); // Add the small tree root node to list in 
            // Remove the nodes in the collection that have participated in building the tree 
            list.remove(left);
            list.remove(right);

// list.remove(0);
// list.remove(0); // Take out two team leader elements   Can also be 

        }
        return list.get(0);
    }

    // The former sequence traversal 
    public void preOrder(Node aRoot) {
    
        if (aRoot != null) {
    
            aRoot.preOrder();
        } else {
    
            System.out.println(" This tree is empty ,  Unable to complete preorder traversal ！");
        }
    }
}

class Node implements Comparable<Node> {
    
    private int element; // The right of the node 
    private Node left; // The left subtree of the node 
    private Node right; // The right subtree of the node 

    // Constructors 
    public Node(int aElement) {
    
        this.element = aElement;
    }

    public int getElement() {
    
        return element;
    }

    public void setElement(int element) {
    
        this.element = element;
    }

    public Node getLeft() {
    
        return left;
    }

    public void setLeft(Node left) {
    
        this.left = left;
    }

    public Node getRight() {
    
        return right;
    }

    public void setRight(Node right) {
    
        this.right = right;
    }

    // The former sequence traversal 
    public void preOrder() {
    
        System.out.print(this + " ");
        if (this.getLeft() != null) {
    
            this.getLeft().preOrder();
        }
        if (this.getRight() != null) {
    
            this.getRight().preOrder();
        }
    }

    @Override
    public String toString() {
    
        return element + "";
    }


    @Override
    public int compareTo(Node o) {
    
        return this.getElement() - o.getElement(); // From small to large 
    }
}

Finally, we use preorder traversal to output the Huffman tree we created , give the result as follows