下载文档原格式
6.3哈夫曼树6.3.1基本术语1.路径和路径长度若在一棵中存在着一个结点序列k1 ,k2,…,kj，使得ki是k1+i 的双亲(1ji<≤)，则称此结点序列是从k1～kj的路径，因树中每个结点只有一个双亲结点，所以它也是这两个结点之间k 1～kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1(实际就是边数)。
如在图5-19(a)所示的二叉树中，从树根结点L到叶子结点P的路径为结点序列L、M、S、P，路径长度为3。
(a) (b)(c) (d)图5-19 二叉排序树的删除2.结点的权和带权路径长度在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，我们称此实数为该结点的权。
结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积3.树的带权路径长度树的带权路径长度定义为树中所有叶子结点的带权路径长度这和，通常记为：2 WPL = ∑=n i i i lw 1其中n 表示叶子结点的数目，i w 和i l 分别表示叶子结点i k 的权值和根到i k 之间的路径长度 。
4.哈夫曼树哈夫曼(Huffman)树又称最优二叉树。
它是n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树。
因为构造这种树的算法是最早由哈夫曼于1952年提出的，所以被称之为哈夫曼树。
例如，有四个叶子结点a 、b 、c 、d ，分别带权为9、4、5、2，由它们构成的三棵不同的二叉树（当然还有其它许多种）分别如图5-20(a)到图5-20(c)所示。
b ac a b cd d c a b d(a) (b) (c)图5-20 由四个叶子结点构成的三棵不同的带权二叉树 每一棵二叉树的带权路径长度WPL 分别为：(a) WPL = 9×2 + 4×2 + 5×2 + 2×2 = 40(b) WPL = 4×1 + 2×2 + 5×3 + 9×3 = 50(c) WPL = 9×1 + 5×2 + 4×3 + 2×3 = 37其中图5-20(c)树的WPL 最小，稍后便知，此树就是哈夫曼树。
数据结构树的知识点总结一、树的基本概念。
1. 树的定义。
- 树是n（n ≥ 0）个结点的有限集。
当n = 0时，称为空树。
在任意一棵非空树中：- 有且仅有一个特定的称为根（root）的结点。
- 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、…、Tm，其中每个集合本身又是一棵树，并且称为根的子树（sub - tree）。
2. 结点的度、树的度。
- 结点的度：结点拥有的子树个数称为结点的度。
- 树的度：树内各结点的度的最大值称为树的度。
3. 叶子结点（终端结点）和分支结点（非终端结点）- 叶子结点：度为0的结点称为叶子结点或终端结点。
- 分支结点：度不为0的结点称为分支结点或非终端结点。
- 除根结点之外，分支结点也称为内部结点。
4. 树的深度（高度）- 树的层次从根开始定义起，根为第1层，根的子结点为第2层，以此类推。
树中结点的最大层次称为树的深度（或高度）。
二、二叉树。
1. 二叉树的定义。
- 二叉树是n（n ≥ 0）个结点的有限集合：- 或者为空二叉树，即n = 0。
- 或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
2. 二叉树的特点。
- 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
- 二叉树的子树有左右之分，次序不能颠倒。
3. 特殊的二叉树。
- 满二叉树。
- 一棵深度为k且有2^k - 1个结点的二叉树称为满二叉树。
满二叉树的特点是每一层上的结点数都是最大结点数。
- 完全二叉树。
- 深度为k的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
完全二叉树的叶子结点只可能在层次最大的两层上出现；对于最大层次中的叶子结点，都依次排列在该层最左边的位置上；如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子。
三、二叉树的存储结构。
1. 顺序存储结构。
- 二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。
数据结构实验报告实验名称：实验3——哈夫曼编码学生姓名：班级：班内序号：学号：日期：2013年11月24日1．实验要求利用二叉树结构实现赫夫曼编/解码器。
基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。
3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。
5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。
2. 程序分析2.1存储结构：struct HNode{char c;//存字符内容int weight;int lchild, rchild, parent;};struct HCode{char data;char code[100];}; //字符及其编码结构class Huffman{private:HNode* huffTree; //Huffman树HCode* HCodeTable; //Huffman编码表public:Huffman(void);void CreateHTree(int a[], int n); //创建huffman树void CreateCodeTable(char b[], int n); //创建编码表void Encode(char *s, string *d); //编码void Decode(char *s, char *d); //解码void differ(char *,int n);char str2[100];//数组中不同的字符组成的串int dif;//str2[]的大小~Huffman(void);};结点结构为如下所示：三叉树的节点结构：struct HNode//哈夫曼树结点的结构体{ int weight;//结点权值int parent;//双亲指针int lchild;//左孩子指针int rchild;//右孩子指针char data;//字符};示意图为：int weight int parent int lchild int rchild Char c 编码表节点结构：struct HCode//编码表结构体{char data;//字符char code[100];//编码内容};示意图为：基本结构体记录字符和出现次数:struct node{int num;char data;};示意图为:2.关键算法分析(1).初始化:伪代码：1.输入需要编译的文本内容2.将输入的内容保存到数组str1中3.统计出现的字符数目,并且保存到变量count中4.统计出现的不同的字符，存到str2中，将str2的大小存到dif中时间复杂度O(n！)（2）.创建哈夫曼树算法伪代码：1.创建一个长度为2*n-1的三叉链表2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将对应结点的孩子域和双亲域赋为空3.从三叉链表的第n个结点开始，3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。
数据结构之⼆叉树（BinaryTree）⽬录导读 ⼆叉树是⼀种很常见的数据结构，但要注意的是，⼆叉树并不是树的特殊情况，⼆叉树与树是两种不⼀样的数据结构。
⽬录 ⼀、⼆叉树的定义 ⼆、⼆叉树为何不是特殊的树 三、⼆叉树的五种基本形态 四、⼆叉树相关术语 五、⼆叉树的主要性质（6个） 六、⼆叉树的存储结构（2种） 七、⼆叉树的遍历算法（4种） ⼋、⼆叉树的基本应⽤：⼆叉排序树、平衡⼆叉树、赫夫曼树及赫夫曼编码⼀、⼆叉树的定义 如果你知道树的定义（有限个结点组成的具有层次关系的集合），那么就很好理解⼆叉树了。
定义：⼆叉树是n(n≥0)个结点的有限集，⼆叉树是每个结点最多有两个⼦树的树结构，它由⼀个根结点及左⼦树和右⼦树组成。
（这⾥的左⼦树和右⼦树也是⼆叉树）。
值得注意的是，⼆叉树和“度⾄多为2的有序树”⼏乎⼀样，但，⼆叉树不是树的特殊情形。
具体分析如下⼆、⼆叉树为何不是特殊的树 1、⼆叉树与⽆序树不同 ⼆叉树的⼦树有左右之分，不能颠倒。
⽆序树的⼦树⽆左右之分。
2、⼆叉树与有序树也不同（关键） 当有序树有两个⼦树时，确实可以看做⼀颗⼆叉树，但当只有⼀个⼦树时，就没有了左右之分，如图所⽰：三、⼆叉树的五种基本状态四、⼆叉树相关术语是满⼆叉树；⽽国际定义为，不存在度为1的结点，即结点的度要么为2要么为0，这样的⼆叉树就称为满⼆叉树。
这两种概念完全不同，既然在国内，我们就默认第⼀种定义就好）。
完全⼆叉树：如果将⼀颗深度为K的⼆叉树按从上到下、从左到右的顺序进⾏编号，如果各结点的编号与深度为K的满⼆叉树相同位置的编号完全对应，那么这就是⼀颗完全⼆叉树。
如图所⽰：五、⼆叉树的主要性质 ⼆叉树的性质是基于它的结构⽽得来的，这些性质不必死记，使⽤到再查询或者⾃⼰根据⼆叉树结构进⾏推理即可。
性质1：⾮空⼆叉树的叶⼦结点数等于双分⽀结点数加1。
证明：设⼆叉树的叶⼦结点数为X，单分⽀结点数为Y，双分⽀结点数为Z。
树和二叉树习题及答案一、填空题1. 不相交的树的聚集称之为森林。
2. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_树可采用孩子-兄弟链表（二叉链表）做存储结构，目的是利用二叉树的已有算法解决树的有关问题。
3. 深度为k的完全二叉树至少有2 k-1个结点。
至多有2 k-1个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2 k-2+1。
4. 在一棵二叉树中，度为零的结点的个数为n，度为2的结点的个数为n2，则有n= n2+1。
5. 一棵二叉树的第i（i≥1）层最多有2 i-1个结点；一棵有n （n>0）个结点的满二叉树共有（n+1）/2个叶子和（n-1）/2个非终端结点。
6.现有按中序遍历二叉树的结果为abc，问有5种不同形态的二叉树可以得到这一遍历结果。
7. 哈夫曼树是带权路径最小的二叉树。
8. 前缀编码是指任一个字符的编码都不是另一个字符编码的前缀的一种编码方法，是设计不等长编码的前提。
9. 以给定的数据集合{4，5，6，7，10，12，18}为结点权值构造的Huffman树的加权路径长度是 165 。
10. 树被定义为连通而不具有回路的（无向）图。
11. 若一棵根树的每个结点最多只有两个孩子，且孩子又有左、右之分，次序不能颠倒，则称此根树为二叉树。
12. 高度为k，且有个结点的二叉树称为二叉树。
2k-1 满13. 带权路径长度最小的二叉树称为最优二叉树，它又被称为树。
Huffman14. 在一棵根树中，树根是为零的结点，而为零的结点是结点。
入度出度树叶15. Huffman树中，结点的带权路径长度是指由到之间的路径长度与结点权值的乘积。
结点树根16. 满二叉树是指高度为k，且有个结点的二叉树。
二叉树的每一层i上，最多有个结点。
2k-1 2i-1二、单选题1. 具有10个叶结点的二叉树中有 (B) 个度为2的结点。
(A)8 (B)9 (C)10 (D)112．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_（3）次序的遍历实现编号。
《数据结构》第五章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、知道一颗树的先序序列和后序序列可唯一确定这颗树。
( ×)2、二叉树的左右子树可任意交换。
（×）3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发生改变。
（√）4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。
（√）5、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
( ×)6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。
( √)7、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。
（×）8、度为2的树就是二叉树。
（×）二、单项选择题1．具有10个叶结点的二叉树中有（ B ）个度为2的结点。
A．8 B．9 C．10 D．112．树的后根遍历序列等同于该树对应的二叉树的( B )。
A. 先序序列B. 中序序列C. 后序序列3、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG 。
该二叉树根的右子树的根是：( C )A. EB. FC. GD. H04、在下述结论中，正确的是（ D ）。
①具有n个结点的完全二叉树的深度k必为┌log2(n+1)┐；②二叉树的度为2；③二叉树的左右子树可任意交换；④一棵深度为k(k≥1)且有2k-1个结点的二叉树称为满二叉树。
A．①②③B．②③④C．①②④D．①④5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树一定是（ D ）。
A．空或只有一个结点B．完全二叉树C．二叉排序树D．高度等于其结点数三、填空题1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为__2n____个，其中___n-1_____个用于指向孩子结点，___n+1___个指针空闲着。
2、一棵深度为k(k≥1)的满二叉树有_____2k-1______个叶子结点。
数据结构复习题：一、判断题1、（）采用循环链表作为存储结构的队列就是循环队列。
2、（）哈夫曼树一定是完全二叉树。
3、（）选择排序是一种稳定的排序方法。
4、（）在顺序存储结构的线性表中，取第i个元素操作的时间复杂度为O(1)。
5、（）有向图中第i个顶点的出度等于其邻接矩阵中第i行非0元素的个数。
6、（）在按值有序的线性链表中可以采用折半查找法进行查找。
7、（）只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。
8、（）在具有n个结点的完全二叉树中，无法确定其叶子结点的个数。
9、（）一棵树转换成二叉树后，该二叉树的根结点一定没有右子树。
10、（）对任意一个图，从它的某个顶点出发进行一次深度或广度优先搜索遍历时，均可访问到该图的每个结点。
11、（）二叉树的存储结构必须采用二叉链表结构。
12、（）给定一组关键字序列，按顺序构造二叉排序树，其树的形态与关键字的排列顺序无关。
13、（）当初始序列为逆序时，简单选择排序的比较次数达到最多。
14、（）在单链表表示的线性表中，取线性表第i个元素操作的时间复杂度为O(n)（n为链表长度）。
15、（）具有n结点的二叉树，其最大深度为n。
16、（）在具有13个叶子结点的二叉树中，其度为2的结点个数一定为12。
17、（）具有n个顶点无向图，其生成树中一定存在n-1条边。
18、（）能采用折半查找法进行查找的查找表必须是有序并为顺序存储。
19、（）若一棵二叉树中不存在度为1的结点，则该二叉树一定是一棵完全二叉树。
20、（）快速排序是目前所有排序方法中效率最高的稳定排序。
二、选择填空1、下列排序方法中，排序所花时间不受数据初始排列特性影响的算法是＿＿＿＿。
A）冒泡排序B）简单选择排序C）快速排序D）直接插入排序2、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为＿＿＿＿个。
A）4 B）5 C）6 D）73、对于给定的8个元素：34，76，45，18，26，54，92，65，按给定顺序生成一棵二叉排序树，该树的深度为＿＿＿＿。
哈夫曼树的存储结构1. 哈夫曼树简介哈夫曼树是一种特殊的二叉树，它被广泛应用于数据压缩和编码算法中。
哈夫曼树的主要特点是，频率越高的字符或数据在树中越靠近根节点，频率越低的字符或数据在树中越靠近叶子节点。
哈夫曼树是通过构建最优前缀编码来实现数据压缩的。
最优前缀编码指的是每个字符或数据都有唯一对应的编码，且任何一个字符或数据的编码都不是其他字符或数据编码的前缀。
2. 哈夫曼树的构建算法哈夫曼树的构建算法可以分为以下几个步骤：步骤1：统计字符或数据出现频率首先需要统计待编码的字符或数据出现的频率。
可以通过扫描待编码的文本或文件，记录每个字符或数据出现的次数。
步骤2：创建叶子节点列表将每个字符或数据及其对应的频率作为一个叶子节点，并将它们放入一个列表中。
步骤3：构建哈夫曼树重复以下步骤，直到列表中只剩下一个节点：1.从列表中选择两个频率最低的叶子节点作为左右子节点。
2.将这两个叶子节点的频率之和作为新节点的频率，并将新节点插入到列表中。
3.从列表中删除这两个被选中的叶子节点。
步骤4：生成哈夫曼编码通过遍历哈夫曼树，可以生成每个字符或数据对应的哈夫曼编码。
从根节点开始，遍历左子树时添加0，遍历右子树时添加1，直到达到叶子节点。
3. 哈夫曼树的存储结构哈夫曼树的存储结构可以使用数组或链表来实现。
以下是两种常见的存储结构：数组表示法在数组表示法中，将哈夫曼树的每个节点都保存在一个数组元素中。
假设有n个字符或数据，则需要2n-1个元素来保存所有的节点。
具体存储方式如下：1.使用一个二维数组tree来保存所有的节点信息。
tree[i][0]表示第i个节点的权值（频率），tree[i][1]表示第i个节点的父亲节点索引，tree[i][2]表示第i个节点的左孩子索引，tree[i][3]表示第i个节点的右孩子索引。
2.哈夫曼树的根节点存储在tree[n-1][0]中，叶子节点存储在tree[0]到tree[n-2]中。
7数据结构复习题（二叉树）一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）树结构中每个结点最多只有一个直接前驱。
（ㄨ）（2）完全二叉树一定是满二查树。
（ㄨ）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。
（√）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。
（√）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。
（√）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。
（√）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。
（ㄨ）（8）在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。
（ㄨ）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。
（√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。
二．填空题（1）在树中，一个结点所拥有的子树数称为该结点的度。
（2）度为零的结点称为叶（或叶子，或终端）结点。
（3）树中结点的最大层次称为树的深度（或高度）。
（4）对于二叉树来说，第i层上至多有2i-1个结点。
（5）深度为h的二叉树至多有2h-1 个结点。
（6）由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。
（7）有20个结点的完全二叉树，编号为10的结点的父结点的编号是 5 。
（8）哈夫曼树是带权路径长度最小的二叉树。
（9）由二叉树的后序和中序遍历序列，可以唯一确定一棵二叉树。
（10）某二叉树的中序遍历序列为: DEBAC，后序遍历序列为：EBCAD。
则前序遍历序列为：DABEC 。
（11）设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是：E、F、H 。
（12）已知完全二叉树的第8层有8个结点，则其叶结点数是68 。
（13）由树转换成二叉树时，其根结点无右子树。
（14）采用二叉链表存储的n个结点的二叉树，一共有2n 个指针域。
