哈夫曼树地建立与操作

1、实验六哈夫曼树的建立与操作一、实验要求和实验内容1、输入哈夫曼树叶子结点（信息和权值）2、由叶子结点生成哈夫曼树内部结点3、生成叶子结点的哈夫曼编码4、显示哈夫曼树结点顺序表二、实验要点：根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左 孩子、右孩子、双亲，如图5-4所示。由于哈夫曼树中共有2n-1个结点，并且 进行n-1次合并操作，所以该数组的长度为 2n-1。weightIchildrcWdparentS5-4咱夹曼祠的皓点结构构造哈夫曼树的伪代码如下：级1初皓仏 所有元素餡点的収丢 左右孩子都宜为

2、7y 2数组huffTree的前n个元素的枚情置给定根1首wn：3一逬行次合并3J在二叉树熏合中选取两个枫值最十的根结点，耳下标分别沟山诰 将二叉帼认合并m新的二叉枫込在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵 哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。、.函数的功能说明及算法思路BTreeNode* CreateHuffma n(ElemType a,i nt n)构造哈夫曼树1. 对给定n个权值a1,a2,月的叶子结点，构成具有n棵二叉树的森林 F=T1,T2,Tn其中每棵二叉树Ti只有一个权值为ai的根结点，其左右子树 为空。2. 在F中选取两棵根结点的权值最

3、小的树作为左右子树构造一棵新的二叉 树，且新的二叉树的根结点的权值为其左右子树上根结点的权值之和。3. 从F中删除构成新树的两棵树，并把新树加入到F中。4. 重复2、3两步，直到F只有一棵树为止。则F中的树就是哈夫曼树。void Prin tBTree(BTreeNode *BT) 以广义表形式输出哈夫曼树主要用到了递归的思想。void HuffMa nCodi ng(BTreeNode *BT, i nt le n)求哈夫曼编码构造一棵二叉树，左分支标识为 0，右分支标识为1，把n个字符看成是 一棵树的n个叶子结点，把从根结点到每个叶子结点路径上的分支标识序列作 为字符的编码，则得到哈夫曼编

4、码。四、实验步骤和提示1、编写有关哈夫曼树操作的函数： 构造哈夫曼树 BTreeNode * CreateHuffma n(ElemType a,i nt n); 以广义表形式输出哈夫曼树void Prin tBTree(BTreeNode *BT); 求哈夫曼编码 void HuffMa nCodi ng(BTreeNode *BT, i nt le n)。把结构定 义以及这些哈夫曼树操作函数存放在头文件 Haffman.h中。2、设在一份电文中共使用5种字符，各字符在电文中出现的频率依次为2, 6, 3, 8, 7。编写相应的测试程序来输出编码哈夫曼树及各字符的哈夫曼编码。 测试程序(即主

5、函数)存放在文件test7.cpp中。#inelude #defi ne MAX20using namespacestd; typedef char valType ; typedef double wghType struct HFM nodevalType data;wghTypeweight;/每个节点的编码/code存储编码/start存储编码是从code数组的第几个开始/在编码过程中从叶子节点向根节点逆推struct HFMcodechar code MAXint start;；/建立哈夫曼树void createHFMtree( HFMnod node, int n)int i;m

6、1,m2为当前还没用到的节点中权值最小和次小的权值int ml, m2;l,r为每次构建一个父节点其左右儿子节点的序号int l, r;for (i = n + 1; i = 2 * n - 1; i+)ml = m2 = 32767;l = r = 0;int k;for (k = 1; k = i - 1; k+)if ( nodek.parent = 0)if ( nodek.weightm1)m2 = m1;r = l;m1 = no dek.weight;l = k;no dei.weight =no del.weight +no der.weight;no dei .l child

7、 = l;no dei.rchild = r;no del.pare nt = i;no der.pare nt = i;/求每个节点的哈夫曼编码void createHFMcode( HFMnod node, HFMcode* hcode, int n)int i;for (i = 1; i = n; i+)HFMcoded;/哈夫曼树最大层数就是元素的个数d.start = n;int num = i;int father =no de num.pare nt;while (father != 0)if ( nodefather.1 child = num)d.coded.start- =

8、Oelsed.coded.start- =1num = father;father =noden um.pare nt;hcodei = d;/打印每个节点的编码void printHFMcode( HFMnod0 node, HFMcode* hcode, int n)int i;for (i = 1; i = n; i+)cout nodei.data :;for ( int k =hcodei.start + 1; k v=n; k+)cout vvhcodei.codek;cout vv en dl;int _tmain (int argc , _TCHAR argv )- -HFMn odeiode2 * MAXHFMcodehcd MAXcout 请输入案例个数： cases;while (cases-)cout 请输入元素个数： endl;for (i = 1; i = n; i+)cout no dei.data;cout vv 输入它的权重：“ vv endl;createHFMtree (no de, n);/求每个节点的哈夫曼编码createHFMcode (no de,