哈夫曼树的建立与操作.docVIP

. . 实验六 哈夫曼树的建立与操作 一、实验要求和实验内容 1、输入哈夫曼树叶子结点（信息和权值） 2、由叶子结点生成哈夫曼树内部结点 3、生成叶子结点的哈夫曼编码 4、显示哈夫曼树结点顺序表 二、实验要点： 根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如图5-4所示。由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的长度为2n-1。 ??????????????? 　　构造哈夫曼树的伪代码如下： ??????在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。 ? 三、.函数的功能说明及算法思路 BTreeNode* CreateHuffman(ElemType a[],int n)//构造哈夫曼树 1.对给定n个权值{a1,a2,…,an}的叶子结点，构成具有n棵二叉树的森林F={T1,T2,…,Tn}, 其中每棵二叉树Ti只有一个权值为ai的根结点，其左右子树为空。 2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 3.从F中删除构成新树的两棵树，并把新树加入到F中。 4.重复 2、3两步，直到F只有一棵树为止。则F中的树就是哈夫曼树。 void PrintBTree(BTreeNode *BT)//以广义表形式输出哈夫曼树 主要用到了递归的思想。 void HuffManCoding(BTreeNode *BT, int len)//求哈夫曼编码 构造一棵二叉树，左分支标识为0，右分支标识为1，把 n 个字符看成是一棵树的 n个叶子结点，把从根结点到每个叶子结点路径上的分支标识序列作为字符的编码，则得到哈夫曼编码。 四、实验步骤和提示 1、编写有关哈夫曼树操作的函数： ①构造哈夫曼树 BTreeNode? * CreateHuffman(ElemType a[],int n); ②以广义表形式输出哈夫曼树 void PrintBTree(BTreeNode *BT); ③求哈夫曼编码 void HuffManCoding(BTreeNode *BT, int len)。把结构定义以及这些哈夫曼树操作函数存放在头文件Haffman.h中。 2、 设在一份电文中共使用5种字符，各字符在电文中出现的频率依次为2, 6, 3, 8, 7。编写相应的测试程序来输出编码哈夫曼树及各字符的哈夫曼编码。测试程序（即主函数）存放在文件test7.cpp中。 ? #includeiostream #define MAX 20 using namespace std; typedef char valType; typedef double wghType; struct HFMnode { valType data; wghType weight; int parent; int lchild; int rchild; }; //每个节点的编码 //code存储编码 //start存储编码是从code数组的第几个开始 //在编码过程中从叶子节点向根节点逆推 struct HFMcode { char code[MAX]; int start; }; //建立哈夫曼树 void createHFMtree(HFMnode *node, int n) { int i; //m1,m2为当前还没用到的节点中权值最小和次小的权值 int m1, m2; //l,r为每次构建一个父节点其左右儿子节点的序号 int l, r; for (i = n + 1; i = 2 * n - 1; i++) { m1 = m2 = 32767; l = r = 0; int k; for (k = 1; k = i - 1; k++) if (node[k].parent == 0) { if (node[k].weightm1) { m2 = m1; r = l; m1 = node[k].weight; l = k; } else if(node[k].weightm2) { m2 = node[k].weight; r = k; } } node[i].weight = node[l].weight + node[r].weight; node[i].lchild = l; node[i]