原创
赫夫曼树
温馨提示：
本文最后更新于 2018年07月05日，已超过 2,114 天没有更新。若文章内的图片失效（无法正常加载），请留言反馈或直接联系我。
什么是赫夫曼树？
创建一颗赫夫曼树
Node
package com.lzhpo.HuffmanTree;
/**
* <p>
* Create By IntelliJ IDEA
* Author：lzhpo
* </p>
*/
public class Node implements Comparable<Node>{
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public int compareTo(Node o){
//从小到大
return this.value - o.value;
//从大到小
// return -(this.value - o.value);
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}
TestHuffmanTree
package com.lzhpo.HuffmanTree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* 赫夫曼树
*
* <p>
* Create By IntelliJ IDEA
* Author：lzhpo
* </p>
*/
public class TestHuffmanTree {
/**
* 创建赫夫曼树
* @param arr
* @return
*/
public static Node createHuffmTree(int[] arr){
/**
* 先使用数组中所有的元素创建若干个二叉树（只有一个节点）
*/
List<Node> nodes = new ArrayList<Node>();
for (int value : arr){
nodes.add(new Node(value));
}
//循环处理
while (nodes.size() > 1){
/**
* 排序
*/
Collections.sort(nodes);
/**
* 取出权值最小的两个二叉树
*/
//取出权值最小的二叉树
Node left = nodes.get(nodes.size() - 1);
//取出权值次小的二叉树
Node right = nodes.get(nodes.size() - 2);
/**
* 创建一颗新的二叉树
*/
Node parent = new Node(left.value + right.value);
/**
* 把取出来的两个二叉树移除
*/
nodes.remove(left);
nodes.remove(right);
/**
* 放入原来的二叉树聚合中
*/
nodes.add(parent);
}
return nodes.get(0);
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
int[] arr = new int[]{3,7,8,29,5,11,23,14};
Node node = createHuffmTree(arr);
//打印赫夫曼树的根节点的值
System.out.println(node);
}
}
- 本文标签： Java 数据结构与算法
- 本文链接： http://www.lzhpo.com/article/56
- 版权声明： 本文由lzhpo原创发布，转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
热门推荐
相关文章
关于我
会打篮球的程序猿
Talk is cheap, show me the code.
