您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法
赫夫曼树(图文)
第十三双眼睛2023-10-20【数据结构与算法】人已围观
简介赫夫曼树
赫夫曼树
package com.xingchen.day011; 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); huffManTree.preOrder(); } public static Node createHuffManTree(int[] arr) { List<Node> list = new ArrayList<>(); for (int i = 0; i< arr.length; i++) { list.add(new Node(arr[i])); } while (list.size() > 1) { //排序,从小到大 Collections.sort(list); //取出权值最小的两颗二叉树 Node left = list.get(0); Node right = list.get(1); //构建一个新的二叉树 Node parent = new Node(left.value + right.value); parent.left = left; parent.right = right; //从list中删除过处理过的元素 list.remove(left); list.remove(right); list.add(parent); } return list.get(0); } } class Node implements Comparable<Node>{ public int value;//节点权值 public Node left;//指向左节点 public 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; } } |
Tags:
很赞哦! ()
上一篇:堆排序(图文)
下一篇:赫夫曼编码解码(图文)
相关文章
随机图文
-
两数之和
两数之和 给定一个整数数组和一个整数目标值,请你在数组中找出何为目标值的那两个整数,并返回,你可以假设每种输入只会对应一种答案,但是数组中的同一个元素不能在数组中出现多次,可以按任意顺序返回答案 -
环形链表(图文)
环形链表 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 ,则返回 true 。 否则,返回 false 。 -
同构字符串(图文)
同构字符串 给定两个字符串 s 和 t ,判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。 -
Excel表列名称(图文)
Excel表列名称 给你一个整数 columnNumber ,返回它在 Excel 表中相对应的列名称。