实验报告2二叉树及哈夫曼编码.docx
- 文档编号:6131069
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:38
- 大小:162.90KB
实验报告2二叉树及哈夫曼编码.docx
《实验报告2二叉树及哈夫曼编码.docx》由会员分享,可在线阅读,更多相关《实验报告2二叉树及哈夫曼编码.docx(38页珍藏版)》请在冰点文库上搜索。
实验报告2二叉树及哈夫曼编码
(此文档为word格式,下载后您可任意编辑修改!
)
实验报告
(20132014学年第二学期)
课程名称
数据结构A
实验名称
实验二二叉树的基本操作及哈夫曼编码译码系统的实现
实验时间
2014
年
4
月
8
日
指导单位
计算机学院计算机软件教学中心
指导教师
朱立华
学生姓名
高怡馨
班级学号
B
学院(系)
教育科学与技术学院
专业
教育技术学
实验报告
实验名称
实验二二叉树的基本操作及哈夫曼编码译码系统的实现
指导教师
朱立华
实验类型
设计
实验学时
2
实验时间
2014.4.8
一、实验目的和要求
(1)掌握二叉链表上实现二叉树基本去处的方法。
(2)学会设计基于遍历的求解二叉树应用问题的递归算法。
(3)理解哈夫曼树的构造算法,学习设计哈夫曼编码和译码系统。
二、实验环境(实验设备)
硬件:
微型计算机
软件:
MicrosoftVisualC++6.0
三、实验原理及内容
实验题一:
在二叉链表上实现二叉树运算
(1)设计递归算法,实现下列二叉树运算:
删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。
(2)设计算法,按自上到下,从左到右的顺序,按层次遍历一棵二叉树。
(3)设计main函数,测试上述每个运算。
内容:
1、建立头文件BTree.H,在该文件中定义二叉树的链式存储结构,并编写二叉树的各种基本操作实现函数。
同时建立一个验证操作实现的主函数文件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的高度
(一)概要设计
1.流程图及设计思想
实验报告
2.本程序包含的模块
(1)主程序模块
Voidmain()
{
初始化;
构造一棵二叉树;
各种遍历二叉树;
对二叉树进行各种常见运算;
删除二叉树;
}
(2)二叉树模块——实现二叉树的抽象数据类型和基本操作
(3)队列模块——实现队列的抽象数据类
(4)二叉树运算模块——求二叉树的结点,叶子数目
(二)详细设计
一.先序遍历:
A.自然语言描述:
1.判断根节点会否为空,如果为空,返回
2.如果根节点不为空
3.先输出根节点,再递归调用自身依次输出左孩子和右孩子
B.代码详细分析
template
voidBinaryTree
:
PreOrder(void(*Visit)(T&x))
{
PreOrder(Visit,root);
}
template
voidBinaryTree
:
PreOrder(void(*Visit)(T&x),BTNode
{
if(t)
{
Visit(t->element);
PreOrder(Visit,t->lChild);
PreOrder(Visit,t->rChild);
}
}}
实验报告
二.中序遍历:
A.自然语言描述:
1.判断根节点是否为空,如果为空,返回
2.如果根节点不为空
3.递归调用自身输出左孩子,再输出根结点,递归调用输出右孩子
B.代码详细分析:
template
voidBinaryTree
:
InOrder(void(*Visit)(T&x))
{
InOrder(Visit,root);
}
template
voidBinaryTree
:
InOrder(void(*Visit)(T&x),BTNode
{
if(t)
{
InOrder(Visit,t->lChild);
Visit(t->element);
InOrder(Visit,t->rChild);
}
}
三.后序遍历:
A.自然语言描述:
1.判断根节点是否为空,如果为空,返回
2.如果根节点不为空
3.递归调用自身输出左孩子和右孩子,再输出根结点
B.代码详细分析:
template
voidBinaryTree
:
PostOrder(void(*Visit)(T&x))
{
PostOrder(Visit,root);
}
template
voidBinaryTree
:
PostOrder(void(*Visit)(T&x),BTNode
{
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
{SeqQueue
se.EnQueue(t);
BTNode
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
{
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
{
if(!
t)
return;
BTNode
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
{
inttempl;
inttempr;
if(!
t)
return0;
templ=GetHeight(t->lChild);
tempr=GetHeight(t->rChild);
if(templ++>tempr++)
returntempl;
else
returntempr;
}
测试结果
实验报告
二叉树基本运算源代码:
BTree.>
usingnamespacestd;
template
structBTNode
{
Telement;
BTNode
BTNode()
{
lChild=rChild=NULL;
}
BTNode(constT&x)
{
element=x;
lChild=rChild=NULL;
}
BTNode(constT&x,BTNode
{
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
voidBreakTree(T&e,BinaryTree
voidLevelOrder(void(*Visit(T&x)));
voidPreOrder(void(*Visit)(T&x));
voidInOrder(void(*Visit)(T&x));
voidPostOrder(void(*Visit)(T&x));
实验报告
voidExchange();
intGetHeight();
protected:
BTNode
private:
voidClear(BTNode
intSize(BTNode
voidLevelOrder(void(*Visit)(T&x),BTNode
voidPreOrder(void(*Visit)(T&x),BTNode
voidInOrder(void(*Visit)(T&x),BTNode
voidPostOrder(void(*Visit)(T&x),BTNode
voidExchange(BTNode
intGetHeight(BTNode
};
template
voidBinaryTree
:
Clear(BTNode
{
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
{
if(root||&left==&right)
return;
root=newBTNode
实验报告
left.root=right.root=NULL;
}
template
voidBinaryTree
:
BreakTree(T&x,BinaryTree
{
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 { 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 实验报告 { 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 { 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 { SeqQueue se.EnQueue(t); BTNode 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 { if(! t) return0; else returnSize(t->lChild)+Size(t->rChild)+1; } template voidBinaryTree : Exchange() { Exchange(root); } template voidBinaryTree : Exchange(BTNode { if(! t) return; BTNode 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 实验报告 { inttempl; inttempr; if(! t) return0; templ=GetHeight(t->lChild); tempr=GetHeight(t->rChild); if(templ++>tempr++) returntempl; else returntempr; } Test.Cpp: #include"BTree.() { BinaryTree y.MakeTree('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 BTNode(){ lChild=rChild=NULL; } BTNode(constT&x){ element=x; lChild=rChild=NULL;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 报告 二叉 哈夫曼 编码