南邮数据结构上机实验二二叉树的基本操作及哈夫曼编码译码系统的(2)

void BinaryTree::Exchange(BTNode*&t) //左右子树交换 { if(t) { BTNode*q = t -> lChild; t -> lChild = t->rChild; t -> rChild = q; Exchange(t -> lChild); Exchange(t -> rChild); } }

template

void BinaryTree::Level_traversal(void(*Visit)(T&x)) //层次遍历{ Level_traversal(Visit, root); cout << endl; }

template

void BinaryTree::Level_traversal(void(*Visit)(T&x),BTNode*t) { BTNode *a; Visit(t -> element); if(t -> lChild) s.EnQueue(t -> lChild); if(t -> rChild) s.EnQueue(t -> rChild); while(s.Front(a) == true) { if(a -> lChild) s.EnQueue(a -> lChild); if(a -> rChild) s.EnQueue(a -> rChild); Visit(a -> element); s.DeQueue(); } }

五、测试和调试

1. 测试用例和结果

测试结果如下图

//层次遍历

2. 结果分析

1) 程序能够正确的实现二叉树的基本的建立、删除、复制、遍历以及结点计算等

基本操作。

2) 由测试结果来看，可以在输出数据时以二叉树图形的形式输出，更简单直观，

因此程序还有待改进。

实习题名: 哈夫曼编码和译码系统 班级 姓名 学号 日期2016.04.14 一、 问题描述 所设计的系统重复显示以下菜单项：

B―――建树：读入字符集和各字符频度，建立哈夫曼树。 T―――遍历：先序和中序遍历二叉树。

E―――生成编码：根据已建成的哈夫曼树，产生各字符的哈夫曼编码。

C―――编码：输入由字符集中字符组成的任意字符串，利用已生成的哈夫曼编码进行编码，显示编码结果，并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中。

D―――译码：读入codefile.txt，利用已建成的哈夫曼树进行译码，并将译码结果存入磁盘文件result.txt中。

P―――打印：屏幕显示文件textfile.txt、codefile.txt和result.txt。 X―――退出。

二、 概要设计

文件Huffman.cpp中定义了四个类,分别是优先权队列类PrioQueue和结点类BTNode、二叉树类BinaryTree以及哈夫曼树类HfmTree，其中哈夫曼树类HfmTree继承了二叉树类BinaryTree。主函数mian的代码如图所示：

三、 详细设计

1. 类和类的层次结构

程序定义了优先权队列类PrioQueue存储元素，为便于实哈夫曼树的建树运算，定义了哈夫曼树类HfmTree是二叉树类BinaryTree的派生类，新增私有的数据成员weight保存二叉树根的权值。成员函数getW和putW用于存取该值。

PrioQueue -T *q -int n, maxSize +PrioQueue(int mSize = 20); +~PrioQueue(){ delete []q; } +bool IsEmpty() const{ return n == 0; } +bool IsFull() const{ return n == maxSize; } +void Append(const T&x); +void Serve(T&x); -void AdjustDown(int r, int j); -void AdjustUp(int j); T T BinaryTree -int i; +BinaryTree(){root = NULL; i = -1;} +~BinaryTree(){} +void MakeTree(const T&x, const char &y, BinaryTree&left, BinaryTree& right); +void PreOrder(void (*Visit)(T&x)); +void InOrder(void (*Visit)(T&x)); +void Create_code(); +void Create_code_out(); +void Code(); +void Compile(); +void Print(); -void PreOrder(void (*Visit)(T&x), BTNode*t); -void InOrder(void (*Visit)(T&x), BTNode*t); -void Create_code(BTNode*t); -void Create_code_out(BTNode*t); -void Code(BTNode*t); -void Make(BTNode*t,char a); -void Compile(BTNode*t); T HfmTree -T weight +operator T() const{ return weight; } +T getW(){ return weight; } +void putW(const T&x){ weight = x; } +void SetNull(){ root = NULL; } 2. 核心算法

定义了类之后，通过函数Make_Ht建树，将相应的字符和权值录入。通过遍历哈夫曼树，产生每个叶子节点的哈夫曼编码，当遍历访问某个叶节点是，从该结点到根的路径可以确定该叶结点所代表的字符的编码。实现译码时，首先将字符读入一维数组，根据0或1向左走向右走直到叶子结点，并将结果写入文件中。其中关键函数编码code和译码Compile以及打印Print的流程图如下。

code()