给定 n 个权值作为 n 个叶子节点,构造一颗二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,也成为哈夫曼树(Huffman Tree),还有的书翻译成霍夫曼树。
赫夫曼树是带权路径长度最短的树,权值较大的节点离根很近。
wpl=59的是赫夫曼树
给定一个数列{13,7,8,3,29,6,1},要求转成一个赫夫曼树
- 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(huffmanTree);
- /**
- * Node{value=67}
- * Node{value=29}
- * Node{value=38}
- * Node{value=15}
- * Node{value=7}
- * Node{value=8}
- * Node{value=23}
- * Node{value=10}
- * Node{value=4}
- * Node{value=1}
- * Node{value=3}
- * Node{value=6}
- * Node{value=13}
- */
- }
- //创建赫夫曼树
- public static Node createHuffmanTree(int[] arr) {
- //第一步为了操作方便
- //1.遍历 arr 数组
- //2.将 arr 的每个元素构成一个Node
- //3.将 Node 放入 ArrayList中
- List<Node> nodes = new ArrayList<>();
- 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.roght = rightNode;
- //(4) 从ArrayList中删除处理过的二叉树
- nodes.remove(leftNode);
- nodes.remove(rightNode);
- //(5) 将parent加入nodes
- nodes.add(parent);
- }
- //返回赫夫曼树的root节点
- return nodes.get(0);
- }
- public static void preOrder(Node node) {
- if (node != null) {
- node.preOrder();
- } else {
- System.out.println("是空树,不能遍历~~");
- }
- }
- }
- //创建节点类,为了让Node对象支持排序,实现了Comparble接口
- class Node implements Comparable<Node> {
- //权值
- int value;
- //指向左子节点
- Node left;
- //指向右子节点
- Node roght;
- //写一个前序遍历
- 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) {
- //从小到大进行排序
- return this.value - o.value;
- }
- }
作者 | 楚奕 来源 | 阿里技术公众号 这篇文章主要从技术视角介绍下跨平台WebCanv...
背景 有时候我会碰到快速搭建测试服务的需求,比如像这样: 搭建一个 HTTP Servi...
3月24日,腾讯发布2020年Q4及全年财报,其中金融科技及企业服务第四季收入385亿...
1.某女生寝室门口贴着一个告示男生与饭盒不得入内,问何解?答曰两者都会搞大女...
创业与投资的本质,都是追寻一种能够穿越时空,抵达未来的高效方式。 德勤管理咨...
1.百度是个大骗子,我抄了十几年的满分作文却从未得过满分。 2.学神在刷难题,...
基于阿里巴巴的互联网架构、大数据技术,利用混合云架构打造全新的云化电子税 务...
1.在报名的路上,我看见远处的学校,轰!的一声没了。希望如此。 2.男:我一直...
前言 微服务成了互联网架构的标配模式,对微服务之间的调用的流量治理和管控就尤...
本文转载自微信公众号「后端Q」,作者conan。转载本文请联系后端Q公众号。 概述 ...