树的表示、哈夫曼树和哈夫曼编码
2024-07-07 18:15:45
发布于:北京
一.父节点表示法
(1)树中的节点数字化为他们的编号~。
(2)用一个一维数组存储每个节点的父节点。即:father[k]
中存放的是的父节点。
(3)由于树中每个节点的父节点是唯一的,所以父节点数组表示法可以唯一表示一棵树。
二.儿子链表表示法
把每个结点的孩子节点排列起来,看成是一个线性表,且以单链表作为存储结构,则n个节点有n个孩子链表(叶子节点的孩子链表为空表)。而n个头指针由组成一个线性表,为了便于查找,可采用顺序存储结构。
三.左儿子右兄弟表示法
用二叉链表作为树的存储结构,链表中每个结点的两个指针分别指向其最左儿子和右邻兄弟。
四.哈夫曼树的基本概念
哈夫曼树(Huffman Tree)又称最优二叉树,是一类带权路径长度最短的二叉树,在实际中有着广泛的用途,它们的带权路径长度可能一样,但形态不同。
(1)路径:从树中的一个节点到另外一个节点之间的分支构成这两个节点之间的路径。
(2)路径长度:路径上的分支数目。
(3)树的路径长度PL:从树根到每一个结点的路径长度之和。
(4)节点的权:给节点的赋予的具有意义的实数,称为节点的权。
(5)节点带权路径长度:把从树根到某一结点的路径长度与该节点权的乘积,称为该结点的带权路径长度。
(6)树的带权路径长度WPL:树中从树根到叶子结点的各个带权路径长度之和。
(7)哈夫曼树:带权路径长度最小的二叉树称作哈夫曼树。
五.哈夫曼树的构造
(1)初始化:用给定的n个权值{w1,w2,...wn}构造n棵二叉树并构成森林F={T1,T2,...Tn},其中每棵二叉树都是单节点二叉树。
(2)找最小数:在森林F中选出两个根节点的权值最小的二叉树合并,作为一棵新二叉树的左右子树,标记新二叉树的根节点权值为它左右子树根节点权值之和。
(3)删除与加入:从森林F中删除选取的那两棵二叉树,并将新二叉树加入森林F中。
(4)判断:重复(2)(3)步直到剩下最后一棵二叉树,此时得到的二叉树就是哈夫曼树。
六.哈夫曼编码
哈夫曼编码,又称霍夫曼编码(Huffman Coding)
是一种可变长编码(VLC,variable length coding)方式,比起定长编码的ASCII编码来说,哈夫曼编码能节省很多的空间,因为每一个字符出现的频率不是一样的。
是一种用于无损数据压缩的熵编码算法,通常用于压缩重复率比较高的字符数据。
如果我们通过转换成ACSII码对应的二进制数据将字符串BCAADDDCCACACAC
通过二进制编码进行传输,那么一个字符串数的二进制位数为8bits,那么总共需要120个二进制位;而如果使用哈夫曼编码,该串字符可压缩至28位。
哈夫曼编码是一种采用了贪心思想的算法。
我有止境,学无止境哦!我们下一个知识点再见!
制作不易,感谢支持❤❤❤
这里空空如也
有帮助,赞一个