哈夫曼树的建立与操作

实验六哈夫曼树的建立与操作

一、实验要求和实验内容

1、输入哈夫曼树叶子结点（信息和权值）2、由叶子结点生成哈夫曼树内部结点3、生成叶子结点的哈夫曼编码4、显示哈夫曼树结点顺序表

二、实验要点：

根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组hufftree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如图5-4所示。由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的长度为2n-1。

构造哈夫曼树的伪代码如下：

在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。

三、.函数的功能说明及算法思路

btreenode*createhuffman（elemtypea[]，intn）//构造哈夫曼树1.对给定n个权值{a1，a2，…，an}的叶子结点，构成具有n棵二叉树的森林f={t1，t2，…，tn}，其中每棵二叉树ti只有一个权值为ai的根结点，其左右子树为空。