Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "how to use Java Huffman tree technology". Many people will encounter such a dilemma in the operation of actual cases, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

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, the binary tree is called the optimal binary tree, which is also called the Huffman tree (Huffman Tree), and some books are translated into Huffman trees.

Huffman tree is the shortest tree with weighted path length, and the node with larger weight is very close to the root.

Several important concepts

* * path and path length: * * in a tree, the path between child or grandchild nodes that can be reached from a node down is called a path. The number of branches in a path is called path length. If the number of layers of the root node is specified to be 1, the path length from the root node to the L-layer node is: Lmur1.

* * weight of node and length of weighted path: * * if a node of a tree species is assigned to a value that has a certain meaning, this value is called the weight of that 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.

The weighted path length of the tree: the weighted path length of the tree is defined as the sum of the weighted path lengths of all leaf nodes, that is, WPL (weighted path length). The binary tree with larger weight is the optimal binary tree.

The smallest WPL is the Huffman tree.

Wpl=59 's is the Huffman tree.

The idea of establishing Huffman Tree

Given a sequence of {13pm 7pm 8pm 3pm 29pm 6pm 1}, it is required to transform it into a Huffman tree.

Sort from small to large, each data is regarded as a node, and each node can be regarded as the simplest binary tree.

Take out the two binary trees with the least weight of the root node.

To form a new binary tree, the weight of the root node of the new binary tree is the sum of the root node weights of the previous two binary trees.

Then sort the new binary tree according to the weight of the root node and repeat the steps of 1-2-3-4 until all the data in the series is processed to get a Huffman tree. As shown in the following figure:

Code case package com.xie.huffmantree; import java.util.ArrayList; 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 huffmanTree = createHuffmanTree (arr); / / preorder traversal preOrder (huffmanTree) / * * Node {value=67} * Node {value=29} * Node {value=38} * Node {value=15} * Node {value=7} * Node {value=8} * Node {value=23} {value=10} * Node {value=4} * Node {value=1} * Node {value=3} * Node {value=6} * Node {value=13} * / / create Huffman tree public static Node createHuffmanTree (int [] arr) {/ / the first step is to facilitate operation / / 1. Traverse the arr array / / 2. Compose each element of arr into a Node / / 3. Put Node in ArrayList List nodes = new ArrayList (); for (int value: arr) {nodes.add (new Node (value));} while (nodes.size () > 1) {/ / sort from smallest to largest Collections.sort (nodes); System.out.println ("nodes =" + nodes) / / take out the two binary trees with the lowest root node weight / / (1) take out the node with the lowest 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.roght = rightNode; / (4) delete the processed binary tree nodes.remove (leftNode) from the ArrayList; nodes.remove (rightNode) / / (5) add parent to nodes nodes.add (parent);} / / return the root node return nodes.get (0) of Huffman tree;} public static void preOrder (Node node) {if (node! = null) {node.preOrder () } else {System.out.println ("is an empty tree and cannot be traversed ~");} / / create a node class. In order to enable the Node object to support sorting, the Comparble interface class Node implements Comparable {/ / weight int value; / / points to the left child node Node left; / / points to the right child node Node roght / / write a preorder to traverse public void preOrder () {System.out.println (this); if (this.left! = null) {this.left.preOrder ();} if (this.roght! = null) {this.roght.preOrder ();}} public Node (int value) {this.value = value } @ Override public String toString () {return "Node {" + "value=" + value +'}';} @ Override public int compareTo (Node o) {/ / sort return this.value-o.value from small to large This is the end of "how to use Java Huffman Tree Technology". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.