Huffman tree
1. Basic introduction
2. Several important concepts and examples of Huffman tree
Steps to construct a Huffman tree
For example: take arr = {1 3 6 7 8 13 29}
public class HuffmanTree { public static void main(String[] args) { int[] arr = { 13, 7, 8, 3, 29, 6, 1 }; Node root = createHuffmanTree(arr); preOrder(root); } // 编写一个前序遍历的方法 public static void preOrder(Node root) { if (root != null) { root.preOrder(); } else { System.out.println("树是空树,无法遍历~~"); } } // 创建赫夫曼树的方法 /** * @param arr 需要创建成霍夫曼树的数组 * @return 创建好后的霍夫曼树的root节点 */ public static Node createHuffmanTree(int[] arr) { // 第一步为了操作方便 // 1.遍历 arr 数组 // 2.将 arr 的每个元素构成一个Node // 3.将Node 放入到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("nodes = " + nodes); // 取出根节点权值最小的两颗二叉树 //注意:如果是从大到小排列的:就应该取倒数第一个和倒数第二个 // (1) 取出权值最小的节点(二叉树) Node leftNode = nodes.get(0); // (2) 取出权值第二小的节点(二叉树) Node rightNode = nodes.get(1); // (3) 构建一颗新的二叉树 Node parent = new Node(leftNode.value + rightNode.value); parent.left = leftNode; parent.right = rightNode; // (4) 从ArrayList删除处理过的二叉树 nodes.remove(leftNode); nodes.remove(rightNode); // (5) 将parent加入到nodes nodes.add(parent); } // 返回赫夫曼树的root节点 return nodes.get(0); } } //创建节点类 //为了让Node对象支持排序Collections集合排序 //让Node实现Comparable接口 class Node implements Comparable<Node> { int value;// 节点权值 Node left;// 指向左子节点 Node right;// 指向右子节点 public Node(int value) { this.value = value; } // 写一个前序遍历 public void preOrder() { System.out.println(this); if (this.left != null) { this.left.preOrder(); } if (this.right != null) { this.right.preOrder(); } } @Override public String toString() { return "Node [value=" + value + "]"; } @Override public int compareTo(Node o) { // 表示从小到大排列 return this.value - o.value; } }
Huffman coding
1. Basic introduction
2. Principle analysis
The above is the detailed content of Example analysis of Huffman tree in java. For more information, please follow other related articles on the PHP Chinese website!

Start Spring using IntelliJIDEAUltimate version...

When using MyBatis-Plus or other ORM frameworks for database operations, it is often necessary to construct query conditions based on the attribute name of the entity class. If you manually every time...

Java...

How does the Redis caching solution realize the requirements of product ranking list? During the development process, we often need to deal with the requirements of rankings, such as displaying a...

Conversion of Java Objects and Arrays: In-depth discussion of the risks and correct methods of cast type conversion Many Java beginners will encounter the conversion of an object into an array...

Solutions to convert names to numbers to implement sorting In many application scenarios, users may need to sort in groups, especially in one...

Detailed explanation of the design of SKU and SPU tables on e-commerce platforms This article will discuss the database design issues of SKU and SPU in e-commerce platforms, especially how to deal with user-defined sales...

How to set the SpringBoot project default run configuration list in Idea using IntelliJ...


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

Dreamweaver Mac version
Visual web development tools

ZendStudio 13.5.1 Mac
Powerful PHP integrated development environment

SAP NetWeaver Server Adapter for Eclipse
Integrate Eclipse with SAP NetWeaver application server.

DVWA
Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software