2023年6月29日发(作者：)

数据结构与算法—哈夫曼树详解与构造⽂章⽬录介绍定义：给定N个权值作为N个叶⼦结点，构造⼀棵⼆叉树，若该树的带权路径长度达到最⼩，称这样的⼆叉树为最优⼆叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较⼤的结点离根较近。简⽽⾔之，就是按照⼀个贪⼼思想和规则进⾏树的构造，⽽构造出来的这个树的权值最⼩！其中WPL表⽰计算出的权值。⾄于为什么按照哈夫曼树⽅法构造得到的权重最⼩。这⾥不进⾏证明。对于哈夫曼树，他的每个⾮叶⼦节点都有两个孩⼦因为哈夫曼树的构造就是⾃底向上的构造，两两合并。WPL计算⽅法:WPL=求和(wi li)其中wi是第i个节点的权值(value)。li是第i个节点的长(深)度.哈夫曼树的构造初始时候各个数直都是⼀个单节点森林！然后进⾏排序。放⼊优先队列(⾃⼰排序也⾏)每次取两个最⼩权值顶点，构造⽗节点(value=+).如果队列为空，那么返回节点，并且这个节点为根节点root。否则继续加⼊队列进⾏排序。重复上述操作，直到队列为空。在计算带权路径长度的时候，需要重新计算树的⾼度(从下往上)，因为哈夫曼树是从下往上构造的，所以对于⾼度不太好维护，可以构造好然后计算⾼度。⽐如上述的WPL为：2*3+3*3+6*2+8*2+9*2=(2+3)*3+(6+8+9)*2=61.代码实现：package ⼆叉树;import eque;import ist;import ator;import ;import tyQueue;import ;public class HuffmanTree {

public static class node { int value; node left; node right; int deep;//记录深度 public node(int value) { =value; =0; } public node(node n1, node n2, int value) { =n1; =n2; =value; } } private node root;//最后⽣成的根节点 Listnodes; public HuffmanTree() { =null; } } public HuffmanTree(Listnodes) { =nodes; } public void createTree() { Queueq1=new PriorityQueue(new Comparator() { public int compare(node o1, node o2) { return ; }}); (nodes); while(!y()) { node n1=(); node n2=(); node parent=new node(n1,n2,+); if(y()) { root=parent;return; } (parent); } } public int getweight() { Queueq1=new ArrayDeque(); (root); int weight=0; while (!y()) { node va=(); if(!=null) { =+1;=+1; ();(); } else { weight+=*; } } return weight; } public static void main(String[] args) { Listlist=new ArrayList(); (new node(2)); (new node(3)); (new node(6)); (new node(8));(new node(9)); HuffmanTree tree=new HuffmanTree(); =list; Tree(); n(ght()); }}哈夫曼树还是⽐较容易理解，主要构造利⽤贪⼼算法的思想。代码实现复杂度可能不太⾼，如果有⼤佬指正还希望指正！如果对数据结构，爬⾍等感兴趣，还请关注我的公众号：bigsai.⼀起学习交流！