1 赫夫曼树定义及其原理
我们先把这两棵二叉树简化成 叶子结点带权的二叉树, 如下图所示
A表示不及格, B表示及格, C表示中等, D表示良好, E表示优秀。
从树中一个结点到另一个结点之间的分支构成两个结点之间的路径， 路径上的分支数目称为路径长度，
二叉树a中, 从根节点到D的路径长度为4, 二叉树b中, 从根节点到D的路径长度为2, 数的路径长度就是从树根 到每一个结点的路径长度之和, 二叉树 a的树路径长度为 1 + 1 +2+2+3+3+4+4 = 20
二叉树 b的树路径长度就是 1+2+3+3+2+1+2+2 = 16
如果考虑到带权的结点, 结点的带权的路径长度为从该节点到树根之间的路径长度与结点上权的乘机, 数的带权路径长度为树中所有叶子结点的带权路径长度之和。 假设有n个权值,(w1, w2, ... wn), 构造一棵有n个结点的二叉树, 每个叶子结点带权 wk, 每个叶子结点的路径长度为 lk, 我们通常记做, 其中带权路径长度 WPL最小的二叉树为赫夫曼树
2 如何构建赫夫曼树
- 先把有权值的叶子结点按照从小到大的顺序排成一个有序序列, 即: A5 E10 B15 D30 C40
- 取头两个最小权值的结点作为一个新结点N1的两个子节点, 注意取相对较小的是左孩子, 这里就是A为N1的左孩子, E为N1的右孩子, 新结点的权值为两个叶子权值的和 5 + 10 = 15
- 将N1替换A与E, 插入有序序列中, 保持从小到大排列, 即 N115, B15, D30, C40
- 重复步骤2, 将N1和B作为一个新结点N2 的两个子节点, 如图所示:
N2的权值为 15 +15 = 30
image.png
5.将N2 替换 N1 和B, 插入有序序列中, 保持从小到大排序, 即: N230, D30, C40
- 重复步骤2, 将N2 与D作为一个新结点, N3的两个子结点, N3的权值是 60
7.将N3 替换N2 和D, 插入有序序列中, 保持从小到大排列, 即 C40, N360
8 重复步骤2, 将C于N3作为一个新结点T的两个子节点, 用于T即是跟结点, 完成赫夫曼树的构造。
此时构造出来的树的权值 WPL = 401 +302 + 153 +104 + 5*4 = 205
通过刚才的步骤分析， 可以得出构造赫夫曼树的算法描述：
- 根据给定的N个权值{w1, w2, w3, ... wn} 构成n棵二叉树的集合 F={T1,T2,...Tn}, 其中每棵二叉树 Ti 中, 只有一个带权wi 根节点, 其左右子树均为空
- 在F中, 选取两个根节点的权值最小的树作为左右子树构成一个新的二叉树, 且置新的二叉树的根节点的权值为其左右子树的权值的和
- 在F中删除这两棵树, 同时将新得到的二叉树加入F中
4 重复2 和3步骤, 直到F中只含一棵树为止, 这棵树就是 赫夫曼树。
假设 6个字母的频率为 A27， B8, C15, D15, E30 , F5
如果我们中序遍历这个赫夫曼树的叶子结点, 则其结果应该是
DAFBCE
注意事项: 在生成哈夫曼树的时候, 每次都要取权重最小的结点, 所以每次从集合 F中取结点时， 都要先对结点进行排序， 然后再取最小的两个值。
第一次做的时候， 先对最原始的结点按照权重进行排序， 然后生成哈夫曼树， 生成错了， 耽误了好久.
代码如下:
代码 参考地址:
https://gitee.com/babyb/data_srtuct/tree/master/012Huffman
package main
import (
"fmt"
)
type Node struct{
value rune
weight int
lchild *Node
rchild *Node
}
//Nodes 用于Node, 按照weight 排序
type Nodes []Node
//Tree 就是整棵Huffman树的根节点
type Tree struct{
Root *Node
}
// 哈夫曼树
func main() {
a := Node{
value: 'A',
weight: 27,
}
b := Node{
value: 'B',
weight: 8,
}
c := Node{
value: 'C',
weight: 15,
}
d := Node{
value: 'D',
weight: 15,
}
e := Node{
value: 'E',
weight: 30,
}
f := Node{
value: 'F',
weight: 5,
}
nodes :=[]Node{a,b,c,d,e,f}
// //按照权重排序
// sorted := sortNodes(nodes);
// //展示排序后的切片
// showNodes(sorted);
//生成哈夫曼树
tree := makeHuffManTree(nodes);
//中序遍历二叉树, 展示叶子结点
root := tree.Root;
showLeafNode(root)
}
//返回排好序的 Nodes
func sortNodes(nodes Nodes) (sorted []Node){
for _, v := range nodes{
if len(sorted) == 0{
sorted = append(sorted, v);
}else{
i:=0;
for i<len(sorted) {
if v.weight < sorted[i].weight {
break;
}
i++
}
// 遍历完之后, 根据i的位置, 把v 插入到 temp当中
if i==0{
//头部插入元素
// fmt.Println("元素插入到头部");
temp := []Node{v}
sorted =append(temp, sorted...);
}else if i== len(sorted){
//尾部插入元素
// fmt.Println("元素插入到尾部");
sorted = append(sorted, v);
}else{
//
// fmt.Println("元素插入到中间位置");
// fmt.Println("前半截", sorted[:i]);
// fmt.Println("后半截", sorted[i:]);
var pre []Node;
pre = append(pre, sorted[:i]...);
var after []Node
after = append(after, sorted[i:]...);
//插入元素
temp :=append(pre, v);
sorted = append(temp, after...)
}
}
// fmt.Println("排序之后的切片:")
// showNodes(sorted)
}
return sorted;
}
func showNodes(nodes Nodes){
for _, v := range nodes{
fmt.Printf("value: %c, weight: %d \n" ,v.value, v.weight)
}
}
//返回哈夫曼树
func makeHuffManTree(nodes Nodes) *Tree{
/*
1 拿出权重最小的两个结点, a, b, 组成新结点; N1,N1的权重 = a.weight + b.weight , 把N1 放到nodes 切片中
2 在 nodes中再拿出两个权重最小的结点, 构成新树, 新树放回node中,
3 重复步骤2 , 直到 nodes 中只剩一个结点, 则这个结点就是树的根节点
*/
var root Node;
for {
if len(nodes) == 1{
// 当 nodes中只有一个元素时, 这个元素必然是根元素
break;
}else{
// 按照从权重小到大的顺序对 nodes进行排序, 这样, 取出的前两个就是权重最小的两个结点了
nodes = sortNodes(nodes);
pre := nodes[:2];
after := nodes[2:];
// fmt.Println("pre", pre[0].weight, pre[1].weight)
newNode := Node{}
newNode.weight = pre[0].weight + pre[1].weight;
newNode.lchild = &pre[0]
newNode.rchild = &pre[1]
//新结点放回到nodes中, 进入下一波循环
var temp []Node;
temp = append(temp, newNode)
//生成的结点放入到 nodes 中
nodes = append(temp, after...)
// var left Node
// var right Node
// //权重小的放左边
// if pre[0].weight < pre[1].weight{
// left = pre[0]
// right = pre[1]
// }else{
// left = pre[1]
// right = pre[0]
// }
// fmt.Printf("左: %c 左边重 %d 右: %c 右边重: %d 新结点权重: %d \n", left.value, left.weight, right.value, right.weight , newNode.weight)
}
}
// for 循环结束后, node中只有一个根元素
root = nodes[0];
//打印根元素的权重
// fmt.Println("root weight", root.weight);
tree := &Tree{ Root: &root }
return tree;
}
/**
遍历叶子结点
**/
func showLeafNode(node *Node) {
//左节点
if node.lchild != nil{
showLeafNode(node.lchild)
}
//右子节点
if node.rchild != nil{
showLeafNode(node.rchild)
}
//
if node.lchild == nil && node.rchild == nil {
fmt.Printf("%c", node.value)
}
}
