哈夫曼树上机实验报告

霍夫曼树实验目的：掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译码的原理。基本要求：熟练掌握树的操作。程序实现：程序第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并把

霍夫曼树 实验目的： 掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译 码的原理。 基本要求： 熟练掌握树的操作。 程序实现： 程序第一遍统计原数据中各字符出现的频率，利用得到的频率值创建 哈夫曼树，并把树的信息保存起来，以便解压时创建同样的哈夫曼树 进行解压；第二遍，根据第一遍扫描得到的哈夫曼树进行编码，并把 编码后的码字存储。 : 要点分析 题目中涉及的主要知识点： 1、本程序参考霍夫曼算法（由给定的权值构造赫夫曼树）： （1）由给定的n个权值{w0,w1,w2,„,wn-1}，构造具有n棵二叉 树的集合F={T0,T1,T2,„,Tn-1}，其中每一棵二叉树Ti只有一 个带有权值wi的根结点，其左、右子树均为空。 （2）重复以下步骤,直到F中仅剩下一棵树为止:①在F中选取两 棵根结点的权值最小的二叉树,做为左、右子树构造一棵 新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点 的权值之和。②在F中删去这两棵二叉树。③把新的二叉树加入F。 2、用构造赫夫曼树以完成赫夫曼编码:把d1,d2,„,dn作为叶子结