Huffman Tree:
package Tree;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
public class HuffmanTree {
public static void main(String[] args) {
int[] arr = {13, 7, 8, 3, 29, 6, 1};
Node root = createHuffmanTree(arr);
preOrder(root);
}
//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 and cannot be traversed");
}
}
//Method to create Huffman numbers
public static Node createHuffmanTree(int[] arr) {
//1. Traverse the arr array
//2. Construct each element of arr into a Node
//3. Put Node into ArrayList
List<Node> nodes = new ArrayList<Node>();
for (int value : arr) {
nodes.add(new Node(value));
}
while (nodes.size() > 1) {
Collections.sort(nodes);
System.out.println("node=" + nodes);
//Get the two binary trees with the smallest root nodes
//1 Take the smallest node
Node leftNode = nodes.get(0);
//Get the next smallest node
Node rightNode = nodes.get(1);
//Construct a new binary tree
Node parent = new Node(leftNode.value + rightNode.value);
parent.left = leftNode;
parent.right = rightNode;
//Delete the processed binary tree from ArrayList
nodes.remove(leftNode);
nodes.remove(rightNode);
//Add parent to nodes
nodes.add(parent);
}
return nodes.get(0);
}
}
//Create node class
class Node implements Comparable<Node> {
int value;//node weight
Node left;//points to the left child node
Node right;//points to the right child node
//Write a preorder 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) {
return this.value - o.value;//Sort from small to large
}
}
Huffman coding:
Detailed explanation of ideas:
Code actual
package Tree;
import java.util.*;
public class HuffmanCode {
public static void main(String[] args) {
String content = "i like like like java do you like a java";
byte[] contentBytes = content.getBytes();
System.out.println(contentBytes.length);//40
List<Node> nodes = getNodes(contentBytes);
System.out.println("nodes=" + nodes);
System.out.println("Huffman Tree");
Node huffmanTreeRoot = createHuffmanTree(nodes);
System.out.println("Preorder traversal");
huffmanTreeRoot.preOrder();
Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
System.out.println("Generated Huffman coding table" + huffmanCodes);
}
//Generate the Huffman code corresponding to the Huffman tree
//1. Place the Huffman coding table in the form of Map<Byte, String> 32--01 97--100 100--11000
static Map<Byte,String> huffmanCodes=new HashMap<Byte,String>();
//2. When generating Huffman coding to represent the need to splice the path, define a StringBuilder to store the path of a certain leaf node.
static StringBuilder stringBuilder=new StringBuilder();
//Encapsulate a handful
private static Map<Byte,String> getCodes(Node root){
if(root==null){
return null;
}
//Process the left subtree of root
getCodes(root.left,"0",stringBuilder);
getCodes(root.right,"1",stringBuilder);
return huffmanCodes;
}
private static void getCodes(Node node,String code,StringBuilder stringBuilder){
StringBuilder stringBuilder2=new StringBuilder(stringBuilder);
//Add code to stringBuilder2
stringBuilder2.append(code);
if (node!=null){//If node==null is not processed
//Determine whether the current node is a leaf node or a non-leaf node
if(node.data==null){//Non-leaf node
getCodes(node.left,"0",stringBuilder2);
getCodes(node.right,"1",stringBuilder2);
}else {//Indicates that it is a leaf node
huffmanCodes.put(node.data, stringBuilder2.toString());
}
}
}
//preorder traversal
private static void preOrder(Node root){
if (root!=null){
root.preOrder();
}else {
System.out.println("Huffman tree is empty");
}
}
private static List<Node> getNodes(byte[] bytes) {
ArrayList<Node> nodes = new ArrayList<>();
Map<Byte, Integer> counts = new HashMap<>();
for (byte b : bytes) {
Integer count = counts.get(b);
if (count == null) {
counts.put(b, 1);
} else {
counts.put(b, count + 1);
}
}
for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
//Create Huffman tree
private static Node createHuffmanTree(List<Node> nodes) {
while (nodes.size() > 1) {
Collections.sort(nodes);
Node leftNode = nodes.get(0);
Node rightNode = nodes.get(1);
//Create a binary tree whose root node only has weights and no date.
Node parent = new Node(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parent);
}
return nodes.get(0);
}
}
//Create Node to store data and weights
class Node implements Comparable<Node> {
Byte data;
int weight;
Node left;
Node right;
public Node(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", weight=" + weight +
'}';
}
//preorder traversal
public void preOrder() {
System.out.println(this);
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
}
Now: