AI教程——哈夫曼树带权路径长度怎么计算

开课吧开课吧锤锤2021-02-03 15:52

  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=7*2+5*2+2*2+4*2=36

  (b)WPL=7*3+5*3+2*1+4*2=46

  (c)WPL=7*1+5*2+2*3+4*3=35

  其中(c)树的WPL最小,可以验证,它就是哈夫曼树。

  注意:

  ① 叶子上的权值均相同时,完全二叉树一定是最优二叉树,否则完全二叉树不一定是最优二叉树。

  ② 最优二叉树中,权越大的叶子离根越近。

  ③ 最优二叉树的形态不唯一,WPL最小

  【问题描述】

  已知输入两行正整数,第二行正整数之间用空格键分开,请建立一个哈夫曼树,以输入的数字为叶节点,求这棵哈夫曼树的带权路径长度。

  【输入形式】

  首先第一行为输入正整数的个数,然后接下来的一行正整数,代表叶结点,正整数个数不超过1000个

  【输出形式】

  输出相应的权值

  【样例输入】

  5

  4 5 6 7 8

  【样例输出】

  69

  1、 路径长度

  从树中一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称做路径长度。

  1、 树的路径长度

  路径长度就是从树根到每一结点的路径长度之和。

人工智能在计算机领域内,得到了愈加广泛的重视。并在机器人,经济政治决策,控制系统,仿真系统中得到应用。发展前景很可观,有对人工智能感兴趣的同学就赶快学习起来吧。以上就是小编今天为大家整理发布的“AI教程——哈夫曼树带权路径长度怎么计算”一文,希望为正在学习人工智能的朋友提供学习参考,更多人工智能教程尽在开课吧广场人工智能教程频道!

有用
分享
全部评论快来秀出你的观点
登录 后可发表观点…
发表
暂无评论,快来抢沙发!
AI项目实战精讲