带权路径长度是树的路径长度。树的路径长度是从树根到树中每一结点的路径长度之和。 在结点数目相同的二叉树中，完全二叉树的路径长度最短。
带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度若根结点为0层，叶结点到根结点的路径长度为叶结点的层数。
带权路径长度表示方法
树的带权路径长度记为WPL=(W1L1+W2L2+W3L3+...+WnLn)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
WPL是衡量一个带权二叉树优劣的关键。无论如何，对于n个带权节点，总可以用他们作为叶节点构造出一颗最小WPL值的树。
搜索了一下百度,树的带权外部路径长度就是指WPL吧,跟树的带权路径长度是同一个概念
8 5 13 2 6构造的哈夫曼树是
(34)
/ \
(13) (21)
/ \ / \
6 (7) 8 13
/ \
2 5
WPL = 62+23 + 53 + 82+ 132 = 75
哈夫曼树带权路径长度是WPL=（W1L1+W2L2+W3L3+...+WnLn）。
树的路径长度是从树根到每一结点的路径长度之和，N个权值Wi（i=1，2，...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1，2，...n）。
哈夫曼树应用
哈夫曼编码在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。
现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。
，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。
先是4和5合并为9，再就是6和7合并为13，接着是8和9合并为17，是13和17合并为30，所以WPL = (6+7+8)2 + (4+ 5)3= 69。
例如
假设有n个权值，则构造出的哈夫曼树有n个叶子结点，n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林。
扩展资料
哈夫曼动态编码动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树；
所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。
1．树的路径长度
树的路径长度是从树根到树中每一结点的路径长度之和.在结点数目相同的二叉树中,完全二叉树的路径长度最短.
2．树的带权路径长度(Weighted Path Length of Tree,简记为WPL)
结点的权在一些应用中,赋予树中结点的一个有某种意义的实数.
结点的带权路径长度结点到树根之间的路径长度与该结点上权的乘积.
树的带权路径长度(Weighted Path Length of Tree)定义为树中所有叶结点的带权路径长度之和,通常记为
其中
n表示叶子结点的数目
wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度.
树的带权路径长度亦称为树的代价.
3．最优二叉树或哈夫曼树
在权为wl,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树.
【例】给定4个叶子结点a,b,c和d,分别带权7,5,2和4.构造如下图所示的三棵二叉树(还有许多棵),它们的带权路径长度分别为
(a)WPL=72+52+22+42=36
(b)WPL=73+53+21+42=46
(c)WPL=71+52+23+43=35
其中(c)树的WPL最小,可以验证,它就是哈夫曼树.
注意
① 叶子上的权值均相,完全二叉树一定是最优二叉树,否则完全二叉树不一定是最优二叉树.
② 最优二叉树中,权越大的叶子离根越近.
③ 最优二叉树的形态不唯一,WPL最小
树的带权路径长度＝所有叶子节点带权路径长度之和
即所有叶子节点的权值乘以该叶子节点所在的层次（第一层为0）之和
带权路径长度也就是树的带权路径长度，树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。
结点的权在一些应用中，赋予树中结点的一个有某种意义的实数。
结点的带权路径长度结点到树根之间的路径长度与该结点上权的乘积。
注意事项
1、叶子上的权值均相，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。
2、最优二叉树中，权越大的叶子离根越近。
3、最优二叉树的形态不唯一，WPL最小。
在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小（即代价最小）的二叉树称为最优二叉树或哈夫曼树。
如果是树的带权路径长度，就是树中所有叶子结点的带权路径长度之和。比如像赫夫曼树又称最优树，是一类带权路径长度最短的树！
哈夫曼树带权路径长度是WPL =（9 + 12 + 15）2 + 6 3 + （3 + 5） 4 = 122。
1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。
2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
4）重复2）和3），直到集合F中只有一棵二叉树为止。
接下来进行带权路径长的计算
a，b，f（权值9,12,15）三个元素距父节点的距离都为2。
c（权值6）元素距父节点的距离为3。
d，e（权值3,5）元素距父节点的距离为4。
结点的权
在一些应用中，赋予树中结点的一个有某种意义的实数。
结点的带权路径长度结点到树根之间的路径长度与该结点上权的乘积。
树的带权路径长度（Weighted Path Length of Tree）定义为树中所有叶结点的带权路径长度之和，通常记为
其中
n表示叶子结点的数目
wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。
树的带权路径长度亦称为树的代价。
