深入学习数据结构中的哈夫曼树编码技术

霍夫曼树，亦称为最优二叉树，是一种在所有二叉树中具有最短带权路径长度的特殊结构。所谓带权路径长度，指的是该树中每一个叶节点所对应的权值与其到根节点路径长度的乘积之和（若将根节点定义为第0层，则叶节点到根节点的路径长度即为其所在层数）。整棵树的路径长度则表示从根节点出发至各个节点路径长度的总和，通常用WPL=（W1L1+W2L2+W3L3+...+WnLn）来表示。当有N个权值Wi（i=1,2,...,n）时，可构建一棵包含N个叶节点的二叉树，每个叶节点对应的路径长度为Li（i=1,2,...,n）。研究表明，霍夫曼树所对应的WPL值在所有可能构造的二叉树中是最小的。由于在《信息论》课程中已经学习过霍夫曼编码的相关知识，因此对于其基本概念已有一定了解。接下来将详细介绍霍夫曼树的具体构建步骤，并通过层次遍历的方式验证所建立的树结构是否正确。

 package edu.njupt.zhb;

    
  
    
 import java.util.LinkedList;
    
 import java.util.List;
    
 import java.util.Queue;
    
 import java.util.concurrent.ArrayBlockingQueue;
    
 import java.util.concurrent.Li