实验报告2二叉树及哈夫曼编码Word格式.docx
- 文档编号:7890049
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:38
- 大小:162.90KB
实验报告2二叉树及哈夫曼编码Word格式.docx
《实验报告2二叉树及哈夫曼编码Word格式.docx》由会员分享,可在线阅读,更多相关《实验报告2二叉树及哈夫曼编码Word格式.docx(38页珍藏版)》请在冰点文库上搜索。
(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<
classT>
voidBinaryTree<
T>
:
PreOrder(void(*Visit)(T&
x))
{
PreOrder(Visit,root);
}
template<
x),BTNode<
*t)
if(t)
Visit(t->
element);
PreOrder(Visit,t->
lChild);
PreOrder(Visit,t->
rChild);
}}
二.中序遍历:
1.判断根节点是否为空,如果为空,返回
3.递归调用自身输出左孩子,再输出根结点,递归调用输出右孩子
B.代码详细分析:
InOrder(void(*Visit)(T&
InOrder(Visit,root);
InOrder(Visit,t->
lChild);
三.后序遍历:
A.自然语言描述:
3.递归调用自身输出左孩子和右孩子,再输出根结点
PostOrder(void(*Visit)(T&
PostOrder(Visit,root);
PostOrder(Visit,t->
Visit(t->
四.层次遍历二叉树:
1.定义头指针和尾指针和空指针p
2.根节点是否为空,如果是,结束
3.如果不是,根节点入队
4.取队首元素,输出队首元素
5.将队首的非空左右结点入队列,删除队首元素
6.循环下去,直到队列为空
FloorOrder(void(*Visit)(T&
x))
FloorOrder(Visit,root);
;
FloorOrder(void(*Visit)(Visit<
*x),BTNode<
*t)
{SeqQueue<
BTNode<
*>
se(100);
se.EnQueue(t);
BTNode<
*temp;
while(!
se.IsEmpty())
se.Front(temp);
Visit(temp);
se.DeQueue();
if(temp->
lchild)
se.EnQueue(temp->
lchild);
child)
rchild);
五.求二叉树的结点数:
A.自然语言描述:
1:
判断根节点是否为空,如果为空,返回0
2:
如果根节点不为空
3:
递归调用求二叉树的结点数的函数,参数改为根节点的左孩子
4:
递归调用求二叉树的结点数的函数,参数改为根节点的右孩子
5:
返回根节点的左右字数的结点数之和
B.代码详细分析:
intBinaryTree<
Size()
returnSize(root);
Size(BTNode<
if(!
t)
return0;
else
returnSize(t->
lChild)+Size(t->
rChild)+1;
六.二叉树的左右交换:
2.如果不为空,再判断该节点左右孩子是否同时为空,
3.如果是,返回
4.如果不为空,交换左右孩子
5.返回循环,遍历左右子树
Exchange()
Exchange(root);
Exchange(BTNode<
return;
*temp;
temp=t->
lChild;
t->
lChild=t->
rChild;
rChild=temp;
Exchange(t->
七.求二叉树的深度:
判断根节点是否为空,如果根节点为空,返回0
如果根节点不为空但是根节点的左右孩子同时为空,返回1
如果以上两个条件都不成立
递归调用求二叉树的深度,函数的参数改为根节点的左孩子,并且深度初始化为1
递归调用求二叉树的深度,函数的参数改为跟结点的右孩子,并且深度初始化为0
6:
返回4与5步中得出深度较大的那个数作为二叉树的深度数
B.代码详细分析:
GetHeight(BTNode<
inttempl;
inttempr;
templ=GetHeight(t->
tempr=GetHeight(t->
if(templ++>
tempr++)
returntempl;
returntempr;
测试结果
二叉树基本运算源代码:
BTree.>
usingnamespacestd;
structBTNode
Telement;
*lChild,*rChild;
BTNode()
lChild=rChild=NULL;
BTNode(constT&
x)
element=x;
BTNode(constT&
x,BTNode<
*l,BTNode<
*r)
lChild=l;
rChild=r;
};
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&
voidLevelOrder(void(*Visit(T&
x)));
voidPreOrder(void(*Visit)(T&
x));
voidInOrder(void(*Visit)(T&
voidPostOrder(void(*Visit)(T&
voidExchange();
intGetHeight();
protected:
*root;
private:
voidClear(BTNode<
*t);
intSize(BTNode<
voidLevelOrder(void(*Visit)(T&
voidExchange(BTNode<
intGetHeight(BTNode<
Clear(BTNode<
Clear(t->
deletet;
boolBinaryTree<
Root(T&
x)const
if(root)
x=root->
element;
returntrue;
returnfalse;
MakeTree(constT&
right)
if(root||&
left==&
right)
root=newBTNode<
(e,left.root,right.root);
left.root=right.root=NULL;
BreakTree(T&
x,BinaryTree<
root||&
right||left.root||right.root)
x=root->
left.root=root->
right.root=root->
deleteroot;
root=NULL;
voidVisit(T&
cout<
<
x<
"
"
emplate<
FloorOrder(void(*Visit)(T&
SeqQueue<
*tmp;
se.Front(tmp);
Visit(tmp);
if(tmp->
lChild)
se.EnQueue(tmp->
GetHeight()
returnGetHeight(root);
emplate<
Test.Cpp:
#include"
BTree.()
BinaryTree<
char>
a,b,x,y,z;
y.MakeTree('
E'
a,b);
z.MakeTree('
F'
x.MakeTree('
C'
y,z);
D'
B'
y,x);
前序遍历"
endl;
z.PreOrder(Visit);
中序遍历"
z.InOrder(Visit);
后序遍历"
z.PostOrder(Visit);
层次遍历"
z.LevelOrder(Visit);
cout<
结点数量:
z.Size()<
z.Exchange();
左右交换后的前序遍历"
z.PreOrder(Visit);
树的高度:
z.GetHeight()<
return0;
实验题二:
哈夫曼编码和译码系统
(1)所设计的系统重复显示以下菜单项:
B―――建树:
读入字符集和各字符频度,建立哈夫曼树。
T―――遍历:
先序和中序遍历二叉树。
E―――生成编码:
根据已建成的哈夫曼树,产生各字符的哈夫曼编码。
C―――编码:
输入由字符集中字符组成的任意字符串,利用已生成的哈夫曼编码进行编码,显示编码结果,并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中。
D―――译码:
读入codefile.txt,利用已建成的哈夫曼树进行译码,并将译码结果存入磁盘文件result.txt中。
P―――打印:
屏幕显示文件textfile.txt、codefile.txt和result.txt。
X―――退出。
源代码
#include<
iostream>
cstdlib>
queue>
string>
int*weightArray;
strings;
string*codeArray;
structBTNode{
*lChild,*rChild;
BTNode(){
lChild=rChild=NULL;
x){
element=x;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 报告 二叉 哈夫曼 编码