哈夫曼树的建立与实现

哈夫曼树的建立与实现1．需求分析
本实验要求：
利用顺序存储结构(如：一维数组)实现n个带权结点的哈夫曼树的建立，输出各结点的Huffman编码。
哈夫曼树的建立与实现具体实现要求：
 1．首先，从键盘输入带权结点的个数n，根据n的大小动态分配用于存放Huffman树的一维数组。
2．对于从键盘输入n个带权结点，进行一维数组的初始化。
3．建立这n个结点的Huffman树，并依次输出各结点的Huffman编码。
2．概要设计
2.1为实现上述功能定义一元多项式的抽象数据类型如下：
ADT BinaryTree{
数据对象D：D是具有相同特性的数据元素的集合。
数据关系R：
  　若Ｄ= φ，则R= φ，称二叉树为空二叉树；
　  若Ｄ φ ，则R={H}，其中H是如下二元关系：
哈夫曼树的建立与实现在D中存在唯一的称为根的数据元素 root ，它在关系H下无前驱；
若D－{root}  φ ，则存在 D-{root}={Dl, Dr}，且Dl∩Dr=φ；
若Dl φ，则Dl中存在唯一的元素xl，<root, xl>∈H，且存在Dl上的关系
 Hl ∈H；若Dr  φ，则有类似的结论；H={<root,xl>,<root,xt>, Hl, Hr}。