霍夫曼树的介绍man霍夫曼树，中文名称为霍夫曼树或霍夫曼树，是最好的二叉树。定义：给定n个权重作为n个叶节点，构造一个二叉树。如果树的加权路径长度达到最小，则该树称为霍夫曼树。这个定义涉及几个不熟悉的概念。以下是霍夫曼树。让我们看一下要回答的图片。 （1）路径和路径长度定义：在树中，可以从一个节点向下到达的子节点或孙节点之间的路径称为路径。路径中的分支数称为路径长度。如果将根节点的层数指定为1，则从根节点到第L层节点的路径长度为L-1。示例：路径长度100和80为1，路径长度50和30为2，路径长度20和10为3。（2）节点的权重和加权路径的长度定义：如果为树中的节点分配了具有特定含义的值，则该值称为节点的权重。节点的加权路径长度是：从根节点到该节点的路径长度与该节点的权重的乘积。示例：节点20的路径长度为3，其加权路径长度=路径长度*权重= 3 * 20 =60。（3）树的加权路径长度定义：树的加权路径长度定义为所有叶节点的加权路径长度的总和，记录为WPL。示例：在示例中，树的WPL = 1 * 100 + 2 * 50 + 3 * 20 + 3 * 10 = 100 + 100 + 60 + 30 = 290.比较下面的两棵树上面的两棵树都是树以{10，20，50，100}作为叶节点。左侧WPL的树= 2 * 10 + 2 * 20 + 2 * 50 + 2 * 100 = 360右侧WPL的树= 290左侧WPL的树“右侧WPL的树”。您也可以计算上述两个示例以外的条件，但实际上，右侧的树是与{10，20，50，100}对应的霍夫曼树。在这一点上，您应该对霍夫曼树的概念有一定的了解，让我们看看如何构造霍夫曼树。