哈夫曼树是二叉树的一种。被称为最优二叉树。实际应用中最重要的是带权路径长度。
基本术语:
树的路径长度:树中每个结点的路径长度之和。
权:附加在树节点上,表示出现的概率。
树的带权路径长度:所有叶子结点带权长度之和。
看实例:
D的结点路径长度:从d到A的路径,共走了两条边,所以为2。树中的叶子结点有D,E和F。结点路径都为2。假设子结点的权都为2,那么树的带权路径长度=2*2+2*2+2*2=12;
哈夫曼树实现:
实质是求树的带权路径长度的最小值。使算法更简便,访问的路径最小。
描述:
1)从给定值中构造森林F,且森林中的每个二叉树只有根结点。
2)从F中选择最小的两个二叉树构成新的二叉树T,权值为两个二叉树的和。
3)重复上述2,直到F中只含有一个二叉树。
实例
1)首先看给定的权值7,4,3,8,9.
转为只有根结点的二叉树。
2)找到最小的两个二叉树进行合并,成为新的二叉树。
可以查出4,3量权值是最小的。
构造二叉树
再将合并的二叉树和剩下二叉树中找合并的最小值进行合并,依次类推。顺序图如下
8,9合并最小17,
Notice:合并的时候,要考虑合并的权值是否为最小.
主要应用:
通信领域中,哈夫曼编码。左子树标识0,右子树标识为1.
总括:
哈夫曼树的学习,刚开始看上去我也很是头晕,完全傻眼了一样,但是不要被外表所迷惑,相信自己可以。不要被公式所吓倒,公式也是从算法出推到推导出来的,只要理解本质,完全可以深刻掌握的。
相关推荐
数据结构--哈夫曼树的基本代码 数据结构的重点算法之一
C语言实现的哈夫曼树
学习数据结构中的哈夫曼树,需要编写头文件。我们
目 录 摘 要 1 前 言 2 正 文 3 1. 采用类C语言定义相关的数据类型 3 2. 各模块的伪码算法 7 ...进一步理解和熟练掌握课本中所学的各种数据结构,学会如何把学到的知识用于解决实际问题,培养学生的动手能力。
数据结构-哈夫曼树和哈夫曼编码.ppt
Java基础复习笔记09数据结构-哈夫曼树
一、问题描述 运用哈夫曼算法构造哈夫曼树,并得到哈夫曼编码。 输入格式:10,5,21,18,8,13 ...1、构造哈夫曼树和哈夫曼编码的存储结构。 2、实现哈夫曼算法,实现哈夫曼树的存储并求出哈夫曼编码。
1、训练学生灵活应用所学数据结构知识,独立完成问题分析,结合数据结构理论知识,编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; 3.提高综合运用所学的...
数据结构哈夫曼树的实现,数据结构哈夫曼树的实现,数据结构哈夫曼树的实现
数据结构实验报告6-二叉树与哈夫曼树.doc
(1)能够通过键盘或者纯文本文件读入字符集的大小 n,以及 n 个字符和权值来建立 哈夫曼树,并且把建立好的哈夫曼树存入到 HuffmanTree.txt 中去。 (2)利用已经建立好的哈夫曼树,对文件中的正文进行编码,将结果存入...
北邮数据结构实验三-哈夫曼树.pdf北邮数据结构实验三-哈夫曼树.pdf
北邮数据结构实验三-哈夫曼树.docx北邮数据结构实验三-哈夫曼树.docx
数据结构-实验三-题目二:哈夫曼树.docx
北邮数据结构实验三-哈夫曼树 (2).docx北邮数据结构实验三-哈夫曼树 (2).docx
2. 实现哈夫曼树数据结构,使用哈夫曼树完成如下文档的编码与译码,假设该文档由5种符号字符(A、B、C、D、E)构成 ABACDEABBCEABAACCCDEACCBAABCCCA 3. 选做:实现二叉树的中序遍历线索化数据结构 4. 选做:使用...
哈夫曼树数据结构_哈夫曼信源编解码 数据结构实验报告.pdf哈夫曼树数据结构_哈夫曼信源编解码 数据结构实验报告.pdf
哈夫曼树数据结构_哈夫曼信源编解码 数据结构实验报告.docx哈夫曼树数据结构_哈夫曼信源编解码 数据结构实验报告.docx