数据结构 哈夫曼树
对学生的成绩进行分段
例如成绩分段如上图所示
且成绩比例为0.05(60) 0.15(60-69) 0.4(70-79) 0.3(80-89) 0.1(90-100)
那么查找效率=0.05x1 + 0.15x2 + 0.4x3 + 0.1x4
如果换用另一种构造方法:
此时查找效率明显上升
带权路径的长度算法(WPL):
如图所示: 该树的WPL为 1x3 + 2x3 + 3x2 + 4x2 +5x2 = 33
哈夫曼树的构造:
每次把权值最小的两棵二叉树合并
比如有权重分别为1 2 3 4 5这样5个节点
先把1和2合并为1棵树,得到权重为3的新树
之后把3和3和并 得到权重为6的树
之后把4和5合并(因为6 4 5中4和5权重最小)
得到权重为9的树
最终把9和6合并 得到权重为15的树
哈夫曼树的特点:
没有度的节点为1
节点总数为2n-1
哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树