# Creation of Huffman tree (Huffman tree) (Java implementation)

2022-01-27 02:58:24 _ No two

# 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) {

}

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);

// 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