AI教程——哈夫曼树基本概念与构造

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

  树的权值:每个树节点所在的那个数字。

  路径:两个节点之间所经过的分支。

  路径长度: 某一路径上的分支条数。

  节点带权路径长度: 节点的权值*该节点的路径长度。

  树带权路径长度:所有叶子节点的带全路径长度之和。

  树带权路径长度:所有叶子节点的带全路径长度之和。

人工智能教程

  a、路径和路径长度

  若在一棵树中存在着一个结点序列 k1,k2,……,kj, 使得 ki是ki+1 的双亲(1《=i《j),则称此结点序列是从 k1 到 kj 的路径。

  从 k1 到 kj 所经过的分支数称为这两点之间的路径长度,它等于路径上的结点数减1.

  b、结点的权和带权路径长度

  在许多应用中,常常将树中的结点赋予一个有着某种意义的实数,我们称此实数为该结点的权,(如下面一个树中的蓝色数字表示结点的权)

  结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积。

  c、树的带权路径长度

树的带权路径长度定义为树中所有叶子结点的带权路径长度之和,公式为:

人工智能教程

  其中,n表示叶子结点的数目,wi 和 li 分别表示叶子结点 ki 的权值和树根结点到 ki 之间的路径长度。

  如下图中树的带权路径长度 WPL=9 x 2 + 12 x 2 + 15 x 2 + 6 x 3 + 3 x 4 + 5 x 4=122

  d、哈夫曼树

如下图为一哈夫曼树示意图。

 人工智能教程

  哈夫曼树又称最优二叉树。它是 n 个带权叶子结点构成的所有二叉树中,带权路径长度 WPL 最小的二叉树。

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

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