哈工大数据结构大作业 - 哈夫曼树生成、编码、遍历

。

一、 问题描述

1. 用户输入字母及其对应的权值，生成哈夫曼树；

2. 通过最优编码的算法实现，生成字母对应的最优0、1编码； 3. 先序、中序、后序遍历哈夫曼树，并打印其权值。

二、 方法思路

1.哈夫曼树算法的实现 §存储结构定义

#define n 100 /* 叶子树*/

#define m 2*(n) –1 /* 结点总数*/ typedef struct { /* 结点型*/ double weight ; /* 权值*/ int lchild ; /* 左孩子链*/ int rchild ; /* 右孩子链*/ int parent; /* 双亲链*/ 优点？ }HTNODE ;

typedef HTNODE HuffmanT[ m ] ; /* huffman树的静态三叉链表表示*/

算法要点

1)初始化：将T[0]，…T[m-1]共2n-1个结点的三个链域均置空( -1 ),权值为0；

2)输入权值：读入n 个叶子的权值存于T的前n 个单元 T[0]，…T[n], 它们是n 个独立的根结点上的权值； 3)合并：对森林中的二元树进行n-1次合并，所产生的新结点

依次存放在T[i](n<=i<=m-1)。每次合并分两步：

-可编辑修改-

。

(1) 在当前森林中的二元树T [0]，…T[i-1]所有结点中选取权值

最小和次最小的两个根结点T[p1]和T[p2]作为合并对象，这

里0<= p1，p2<= i –1;

(2) 将根为T[p1]和T[p2]的两株二元树作为左、右子树合并为一

株新二元树，新二元树的根结点为T[i]。即

T[p1].parent =T[p2].parent = i ,T[i].lchild= p1, T[i].rchild=p2， T[p2].weight。

2.用huffman算法求字符集最优编码的算法：

1) 使字符集中的每个字符对应一株只有叶结点的二叉树，

叶的权值为对应字符的使用频率；

2) 利用huffman算法来构造一株huffman树； 3) 对huffman树上的每个结点，左支附以0，右支附以

1（或者相反），则从根到叶的路上的0、1序列就是相应字符的编码 Huffman编码实现： 存储结构

typedef struct{ char ch; //存储字符

char bits[n+1]; //字符编码位串 }CodeNode;

typedef CodeNode HuffmanCode[n]; HuffmanCode H; 3.二叉树遍历的递归定义

T[i].weight

=T[p1].weight

+

-可编辑修改-

。

先根顺序遍历二叉树： 若二叉树非空则： {

访问根结点； 先根顺序遍历左子树； 先根顺序遍历右子树； }

中根顺序遍历二叉树： 若二叉树非空则：

{

中根顺序遍历左子树； 访问根结点；

中根顺序遍历右子树； } 后根顺序遍历二叉树： 若二叉树非空则： { 后根顺序遍历左子树； 后根顺序遍历右子树； 访问根结点； } ；

三、主要数据结构及源程序代码及其注释 1.扩充二叉树：内结点、外结点 （增长树）

-可编辑修改-

。

2.哈夫曼树

3. Huffman编码实现

源程序代码及注释

#include \#include #include #include #define n 10

-可编辑修改-