数据结构中的树：Huffman Tree及其相关编码解析（C++实现）

#笔记整理

根据上文所述，关于树的基本概念将参考前文中的相关内容

哈夫曼树（也称赫夫曼树）

相关概念：

在树中任意两个结点之间存在的分支序列即为它们之间的路径，在此路径上所包含的分支数量即被定义为路径长度。

树中各节点至根节点的距离之和

为了便于后续分析和研究，在树形数据结构中对每个节点赋予一个具有实际意义的具体数值（即"权"），这一数值通常用小写字母w表示，并将其标记在对应的节点上。具体定义如下：在树形结构中，从某个特定节点到另一个节点（通常是根节点到叶子节点）沿着边上所经过的道路距离之总和与该目标节点所赋"权"值之乘积，则被称为该目标节点相对于起点 node 的带权路径长度（Weighted Path Length of Tree, WPL）。其中若以root表示根节点，则称此距离为root node到node node之间的加权距离，并记作w(root, node)；而相应的带权路径长度则记作wpl(node) = w(root, node) * w(node)。

假设一个二叉树拥有n个带有权重值的关键节点（leaf nodes），则将每个关键节点到根节点的距离与其对应的权重相乘后再累加起来的结果称为该二叉树的关键路径总权重（weighted path length）。

哈夫曼树(最优二叉树)

具有最小带权路径长度的*