哈夫曼树及其应用
路径
从书中一个节点到另一个节点之间的分支构成两个节点的路径
结点的路径长度
两节点间路径的分支
树的路径长度
从树根到每一个结点的路径之和
节点数目相等时,完全二叉树最路径长度最短
节点的带权路径长度
路径长度x权重
树的带权路径长度
所有结点的带权路径长度之和
哈夫曼树
带权路径长度最小的二叉树
哈夫曼树的构造方法
说人话就是从小到大,合并(搭建)哈夫曼树
需要注意的是,每次合并,都是选择权值最小的两个树(无论是否为单节点)
哈夫曼编码
构造不等长的前缀编码
从书中一个节点到另一个节点之间的分支构成两个节点的路径
两节点间路径的分支
从树根到每一个结点的路径之和
节点数目相等时,完全二叉树最路径长度最短
路径长度x权重
所有结点的带权路径长度之和
带权路径长度最小的二叉树
说人话就是从小到大,合并(搭建)哈夫曼树
需要注意的是,每次合并,都是选择权值最小的两个树(无论是否为单节点)
构造不等长的前缀编码