实验报告2二叉树及哈夫曼编码.docx
《实验报告2二叉树及哈夫曼编码.docx》由会员分享，可在线阅读，更多相关《实验报告2二叉树及哈夫曼编码.docx（40页珍藏版）》请在冰点文库上搜索。
实验报告2二叉树及哈夫曼编码
实验报告
（2013/2014学年第二学期）
课程名称
数据结构A
实验名称
实验二二叉树的基本操作及哈夫曼编码译码系统的实现
实验时间
2014
年
4
月
8
日
指导单位
计算机学院计算机软件教学中心
指导教师
朱立华
学生姓名
高怡馨
班级学号
B12140113
学院（系）
教育科学与技术学院
专业
教育技术学
实验报告
实验名称
实验二二叉树的基本操作及哈夫曼编码译码系统的实现
指导教师
朱立华
实验类型
设计
实验学时
2
实验时间
.8
一、实验目的和要求
（1）掌握二叉链表上实现二叉树基本去处的方法。
（2）学会设计基于遍历的求解二叉树应用问题的递归算法。
（3）理解哈夫曼树的构造算法，学习设计哈夫曼编码和译码系统。
二、实验环境（实验设备）
硬件:
微型计算机
三、实验原理及内容
实验题一：
在二叉链表上实现二叉树运算
（1）设计递归算法，实现下列二叉树运算：
删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。
（2）设计算法，按自上到下，从左到右的顺序，按层次遍历一棵二叉树。
（3）设计main函数，测试上述每个运算。
内容：
1、建立头文件，在该文件中定义二叉树的链式存储结构，并编写二叉树的各种基本操作实现函数。
同时建立一个验证操作实现的主函数文件Test.cpp，编译并调试程序，直到正确运行。
注意：
需要用到队列的有关操作。
实验报告
说明：
二叉树的基本操作可包括：
（1）voidClear（BTreeNode*BT）//清除一棵二叉树，并释放结点空间
（2）voidMakeTree（BTreeNode*BT）//构造一棵二叉树BT
（3）voidBreakTree（BTreeNode*BT）//撤销一棵二叉树BT
（4）voidPreOrder（BTreeNode*BT）//先序遍历二叉树BT
（5）voidInOrder（BTreeNode*BT）//中序遍历二叉树BT
（6）voidPostOrder（BTreeNode*BT）//后序遍历二叉树BT
（7）voidFloorOrder（BTreeNode*BT）//层次遍历二叉树BT
（8）intSize（BTreeNode*BT）//求二叉树BT的结点数量
（9）voidExchange（BTreeNode*BT）//把二叉树BT的左右子树进行交换
（10）intGetHeight（BTreeNode*BT）//求二叉树BT的高度
（一）概要设计
实验报告
2.本程序包含的模块
（1）主程序模块
Voidmain（）
{
初始化；
构造一棵二叉树；
各种遍历二叉树；
对二叉树进行各种常见运算；
删除二叉树；
}
（2）二叉树模块——实现二叉树的抽象数据类型和基本操作
（3）队列模块——实现队列的抽象数据类
（4）二叉树运算模块——求二叉树的结点，叶子数目
（二）详细设计
一．先序遍历：
A．自然语言描述:
1.判断根节点会否为空，如果为空，返回
3.先输出根节点，再递归调用自身依次输出左孩子和右孩子
B．代码详细分析
template
voidBinaryTree:
:
PreOrder（void（*Visit）（T&x））
{
PreOrder（Visit,root）;
}
template
voidBinaryTree:
:
PreOrder（void（*Visit）（T&x）,BTNode*t）
{
if（t）
{
Visit（t->element）;
PreOrder（Visit,t->lChild）；
PreOrder（Visit,t->rChild）;
}
}}
实验报告
二．中序遍历：
A．自然语言描述:
1.判断根节点是否为空，如果为空，返回
3.递归调用自身输出左孩子，再输出根结点，递归调用输出右孩子
B．代码详细分析：
template
voidBinaryTree:
:
InOrder（void（*Visit）（T&x））
{
InOrder（Visit,root）;
}
template
voidBinaryTree:
:
InOrder（void（*Visit）（T&x）,BTNode*t）
{
if（t）
{
InOrder（Visit,t->lChild）;
Visit（t->element）;
InOrder（Visit,t->rChild）;
}
}
三．后序遍历：
A．自然语言描述：
1.判断根节点是否为空，如果为空，返回
3.递归调用自身输出左孩子和右孩子，再输出根结点
B．代码详细分析：
template
voidBinaryTree:
:
PostOrder（void（*Visit）（T&x））
{
PostOrder（Visit,root）;
}
template
voidBinaryTree:
:
PostOrder（void（*Visit）（T&x）,BTNode*t）
{
if（t）
{
PostOrder（Visit,t->lChild）;
PostOrder（Visit,t->rChild）;
实验报告
Visit（t->element）;
}
}
四．层次遍历二叉树：
A．自然语言描述：
1．定义头指针和尾指针和空指针p
2.根节点是否为空，如果是，结束
3.如果不是，根节点入队
4.取队首元素，输出队首元素
5.将队首的非空左右结点入队列，删除队首元素
6.循环下去，直到队列为空
B．代码详细分析：
template
voidBinaryTree:
:
FloorOrder（void（*Visit）（T&x））
{
FloorOrder（Visit,root）;
}
template
voidBinaryTree:
;FloorOrder（void（*Visit）（Visit*x）,BTNode*t）
{SeqQueue*>se（100）;
se.EnQueue（t）;
BTNode*temp;
while（!
se.IsEmpty（））
{
se.Front（temp）;
Visit（temp）;
se.DeQueue（）;
if（temp->lchild）
se.EnQueue（temp->lchild）;
if（temp->child）
se.EnQueue（temp->rchild）;
}
}
五．求二叉树的结点数：
A.自然语言描述：
1：
判断根节点是否为空，如果为空，返回0
2：
如果根节点不为空
3：
递归调用求二叉树的结点数的函数，参数改为根节点的左孩子
4：
递归调用求二叉树的结点数的函数，参数改为根节点的右孩子
实验报告
5：
返回根节点的左右字数的结点数之和
B．代码详细分析:
template
intBinaryTree:
:
Size（）
{
returnSize（root）;
}
template
intBinaryTree:
:
Size（BTNode*t）
{
if（!
t）
return0;
else
returnSize（t->lChild）+Size（t->rChild）+1;
}
六．二叉树的左右交换:
A．自然语言描述：
1.判断根节点是否为空，如果为空，返回
2.如果不为空，再判断该节点左右孩子是否同时为空，
3.如果是，返回
4.如果不为空，交换左右孩子
5.返回循环，遍历左右子树
B．代码详细分析：
template
voidBinaryTree:
:
Exchange（）
{
Exchange（root）;
}
template
voidBinaryTree:
:
Exchange（BTNode*t）
{
if（!
t）
return;
BTNode*temp;
temp=t->lChild;
t->lChild=t->rChild;
t->rChild=temp;
Exchange（t->lChild）;
Exchange（t->rChild）;}
实验报告
七．求二叉树的深度：
A．自然语言描述：
1：
判断根节点是否为空，如果根节点为空，返回0
2：
如果根节点不为空但是根节点的左右孩子同时为空，返回1
3：
如果以上两个条件都不成立
4：
递归调用求二叉树的深度，函数的参数改为根节点的左孩子，并且深度初始化为1
5：
递归调用求二叉树的深度，函数的参数改为跟结点的右孩子，并且深度初始化为0
6：
返回4与5步中得出深度较大的那个数作为二叉树的深度数
B．代码详细分析:
template
intBinaryTree:
:
GetHeight（BTNode*t）
{
inttempl;
inttempr;
if（!
t）
return0;
templ=GetHeight（t->lChild）;
tempr=GetHeight（t->rChild）;
if（templ++>tempr++）
returntempl;
else
returntempr;
}
测试结果
实验报告
二叉树基本运算源代码：
:
#include
usingnamespacestd;
template
structBTNode
{
Telement;
BTNode*lChild,*rChild;
BTNode（）
{
lChild=rChild=NULL;
}
BTNode（constT&x）
{
element=x;
lChild=rChild=NULL;
}
BTNode（constT&x,BTNode*l,BTNode*r）
{
element=x;
lChild=l;
rChild=r;
}
};
template
classBinaryTree
{
public:
BinaryTree（）{root=NULL;}
~BinaryTree（）{Clear（root）;}
boolIsEmpty（）const;
voidClear（）;
boolRoot（T&x）const;
intSize（）;
voidMakeTree（constT&e,BinaryTree&left,BinaryTree&right）;
voidBreakTree（T&e,BinaryTree&left,BinaryTree&right）;
voidLevelOrder（void（*Visit（T&x）））;
voidPreOrder（void（*Visit）（T&x））;
voidInOrder（void（*Visit）（T&x））;
voidPostOrder（void（*Visit）（T&x））;
实验报告
voidExchange（）;
intGetHeight（）;
protected:
BTNode*root;
private:
voidClear（BTNode*t）;
intSize（BTNode*t）;
voidLevelOrder（void（*Visit）（T&x）,BTNode*t）;
voidPreOrder（void（*Visit）（T&x）,BTNode*t）;
voidInOrder（void（*Visit）（T&x）,BTNode*t）;
voidPostOrder（void（*Visit）（T&x）,BTNode*t）;
voidExchange（BTNode*t）;
intGetHeight（BTNode*t）;
};
template
voidBinaryTree:
:
Clear（BTNode*t）
{
if（!
t）
return;
Clear（t->lChild）;
Clear（t->rChild）;
deletet;
}
template
boolBinaryTree:
:
Root（T&x）const
{
if（root）
{
x=root->element;
returntrue;
}
else
returnfalse;
}
template
voidBinaryTree:
:
MakeTree（constT&e,BinaryTree&left,BinaryTree&right）
{
if（root||&left==&right）
return;
root=newBTNode（e,left.root,right.root）;
实验报告
left.root=right.root=NULL;
}
template
voidBinaryTree:
:
BreakTree（T&x,BinaryTree&left,BinaryTree&right）
{
if（!
root||&left==&right||left.root||right.root）
return;
x=root->element;
left.root=root->lChild;
right.root=root->rChild;
deleteroot;
root=NULL;
}
template
voidVisit（T&x）
{
cout<}
template
voidBinaryTree:
:
PreOrder（void（*Visit）（T&x））
{
PreOrder（Visit,root）;
}
template
voidBinaryTree:
:
PreOrder（void（*Visit）（T&x）,BTNode*t）
{
if（t）
{
Visit（t->element）;
PreOrder（Visit,t->lChild）;
PreOrder（Visit,t->rChild）;
}
}
template
voidBinaryTree:
:
InOrder（void（*Visit）（T&x））
{
InOrder（Visit,root）;
}
emplate
voidBinaryTree:
:
InOrder（void（*Visit）（T&x）,BTNode*t）
实验报告
{
if（t）
{
InOrder（Visit,t->lChild）;
Visit（t->element）;
InOrder（Visit,t->rChild）;
}
}
template
voidBinaryTree:
:
PostOrder（void（*Visit）（T&x））
{
PostOrder（Visit,root）;
}
template
voidBinaryTree:
:
PostOrder（void（*Visit）（T&x）,BTNode*t）
{
if（t）
{
PostOrder（Visit,t->lChild）;
PostOrder（Visit,t->rChild）;
Visit（t->element）;
}
}
template
voidBinaryTree:
:
FloorOrder（void（*Visit）（T&x））
{
FloorOrder（Visit,root）;
}
template
voidBinaryTree:
:
FloorOrder（void（*Visit）（T&x）,BTNode*t）
{
SeqQueue*>se（100）;
se.EnQueue（t）;
BTNode*tmp;
while（!
se.IsEmpty（））
{
se.Front（tmp）;
Visit（tmp）;
se.DeQueue（）;
if（tmp->lChild）
实验报告
se.EnQueue（tmp->rChild）;
}
}
template
intBinaryTree:
:
Size（）
{
returnSize（root）;
}
template
intBinaryTree:
:
Size（BTNode*t）
{
if（!
t）
return0;
else
returnSize（t->lChild）+Size（t->rChild）+1;
}
template
voidBinaryTree:
:
Exchange（）
{
Exchange（root）;
}
template
voidBinaryTree:
:
Exchange（BTNode*t）
{
if（!
t）
return;
BTNode*temp;
temp=t->lChild;
t->lChild=t->rChild;
t->rChild=temp;
Exchange（t->lChild）;
Exchange（t->rChild）;
}
template
intBinaryTree:
:
GetHeight（）
{
returnGetHeight（root）;
}
emplate
intBinaryTree:
:
GetHeight（BTNode*t）
实验报告
{
inttempl;
inttempr;
if（!
t）
return0;
templ=GetHeight（t->lChild）;
tempr=GetHeight（t->rChild）;
if（templ++>tempr++）
returntempl;
else
returntempr;
}
Test.Cpp：
#include"BTree.h"
intmain（）
{
BinaryTreea,b,x,y,z;
ee（'E',a,b）;
z.MakeTree（'F',a,b）;
x.MakeTree（'C',y,z）;
y.MakeTree（'D',a,b）;
z.MakeTree（'B',y,x）;
cout<<"前序遍历"<z.PreOrder（Visit）;
cout<cout<<"中序遍历"<z.InOrder（Visit）;
cout<cout<<"后序遍历"<z.PostOrder（Visit）;
cout<cout<<"层次遍历"<z.LevelOrder（Visit）;
cout<cout<<"结点数量:
";
cout<z.Exchange（）;
cout<<"左右交换后的前序遍历"<实验报告
z.PreOrder（Visit）;
cout<<"树的高度:
";
cout<cout<return0;
}
实验报告
实验题二：
哈夫曼编码和译码系统
（1）所设计的系统重复显示以下菜单项：
B―――建树：
读入字符集和各字符频度，建立哈夫曼树。
T―――遍历：
先序和中序遍历二叉树。
E―――生成编码：
根据已建成的哈夫曼树，产生各字符的哈夫曼编码。
C―――编码：
输入由字符集中字符组成的任意字符串，利用已生成的哈夫曼编码进行编码，显示编码结果，并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中。
D―――译码：
读入codefile.txt，利用已建成的哈夫曼树进行译码，并将译码结果存入磁盘文件result.txt中。
P―――打印：
屏幕显示文件textfile.txt、codefile.txt和result.txt。
X―――退出。
源代码
#include
#include
#include
#include
#include
usingnamespacestd;
int*weightArray;
strings;
string*codeArray;
template
structBTNode{
Telement;
BTNode*lChild,*rChild;
BTNode（）{
lChild=rChild=NULL;
}
BTNode（constT&x）{
element=x;
lChild=rChild=NULL;
}
B
升级会员 