二叉树基本操作以及哈夫曼编码译码系统.docx
- 文档编号:4610281
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:40
- 大小:150.68KB
二叉树基本操作以及哈夫曼编码译码系统.docx
《二叉树基本操作以及哈夫曼编码译码系统.docx》由会员分享,可在线阅读,更多相关《二叉树基本操作以及哈夫曼编码译码系统.docx(40页珍藏版)》请在冰点文库上搜索。
二叉树基本操作以及哈夫曼编码译码系统
实验报告
(2015/2016学年第二学期)
课程名称
数据结构
实验名称
二叉树基本操作以及哈夫曼编码译码系统
实验时间
2016
年
4
月
14
日
指导单位
南京邮电大学
指导教师
骆健
学生姓名
吴佳瑶
班级学号
B14111708
学院(系)
管理学院
专业
信息管理与信息系统
二叉树的基本运算:
1、问题描述
1.设计递归算法,实现二叉树的运算:
删除一棵二叉树,求一棵二叉树的高度,求一棵二叉树中叶子节点数,复制一棵二叉树,交换一棵二叉树的左右子树
2.设计算法,自上而下,自左向右即按层次遍历一棵二叉树
3.设计main函数,测试上述每个运算
二、系统分析和概要设计
首先用maketree构造一棵二叉树,然后遍历二叉树,然后交换每个结点的左右子树,接着算出输得高度和叶子节点,最后删除。
三、详细设计
1.类和类的层次结构
BinaryTree
#BTNode
-staticintnumber
+BinaryTree()
+~BinaryTree()
+voidCopy(BinaryTree
+boolIsEmpty()const
+voidClear()
+voidExchange()
+boolRoot(T&x)const;
+intGetHeight()
+voidMakeTree(constT&x,BinaryTree
+voidBreakTree(T&x,BinaryTree
+voidPreOrder(void(*Visit)(T&x))
+voidLevelOrder(void(*Visit)(T&x))
+intSize()
+BinaryTree
+BTNode
-voidClear(BTNode
-voidExchange(BTNode
-intGetHeight(BTNode
-intSize(BTNode
-voidPreOrder(void(*Visit)(T&x),BTNode
-voidLevelOrder(void(*Visit)(T&x),BTNode
2.核心算法
建立二叉树的voidMakeTree(constT&x,BinaryTree
3.算法分析
删除一棵二叉树,求一棵二叉树的高度,求一棵二叉树中叶子节点数,复制一棵二叉树等都是用递归的方法实现。
四、程序代码
一.先序遍历:
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);
}
template
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)(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);
}
}
五.求二叉树的结点数:
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(BTNode
{
inttempl;
inttempr;
if(!
t)
return0;
templ=GetHeight(t->lChild);
tempr=GetHeight(t->rChild);
if(templ++>tempr++)
returntempl;
else
returntempr;
五、测试用例和运行结果
测试用例结果如下图所示。
哈夫曼编码和译码系统:
一、问题描述
1.所设计的系统重复显示以下菜单
B-----建树:
读入字符集和各字符频度
T-----遍历:
先序和中序遍历二叉树
E-----生成代码:
根据已经简称的哈夫曼数生成代码,产生各字符的哈夫曼树
C-----编码:
输入由字符集中字符组成的任意字符串,利用已经生成的哈夫曼编码进行编码,显示编码结果,并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中
D-----译码:
读入codefile.txt,利用已经建成的哈夫曼树进行译码,并将译码结果存入磁盘文件result.txt
P-----打印:
屏幕显示文件textfile.txt、codefile.txt、resultfile.txt
X-----退出
二、系统分析和概要设计
主要包括实现主菜单以及菜单里每个函数的功能(创建函数实现接收字符,接收权值,构建哈夫曼树并保存文件,编码函数实现对用户输入的秘文进行哈夫曼编码,即对每个字符翻译出其密文代码并保存文件,译码函数实现译码即输出密文的源码)。
三、详细设计
1.类和类的层次结构
BinaryTree
#BTNode
-staticintnumber
+BinaryTree()
+~BinaryTree()
+boolIsEmpty()const
+voidClear()
+boolRoot(T&x)const;
+voidMakeTree(constT&x,BinaryTree
+voidBreakTree(T&x,BinaryTree
+voidPreOrder()
+voidinOrder()
+voidleaf()
+voidvisit(T&x)+
-voidpostOrder()
-voidClear(BTNode
-voidPreOrder(,BTNode
-voidprePrint(BTNode
-voidinOrder(BTNode
-voidpostOrder(BTNode
PrioQueue
-T*q;
-intn,maxSize;
+PrioQueue(intmSize=20)
+~PrioQueue()
+boolIsEmpty()const
+boolIsFull()const
+voidAppend(constT&x)
+voidServe(T&x)
-voidAdjustDown(intr,intj)
-voidAdjustUp(intj)
HfmTree
-Tweight
+operatorT()const
+TgetW()
+voidputW(constT&x)
+voidSetNull()
+voidcode(string&c)
+voiddecode(strings)
-voidcode(BTNode
2.核心算法
实现优先权队列的Append(x)以及Serve(x)函
数以及AdjustUp()、AdjustDown()函数
3.算法分析
时间复杂度均为O(n)
四、程序代码
#include
#include
usingnamespacestd;
int*weightArray;
strings;
string*codeArray;
template
structBTNode
{
BTNode()
{
lChild=rChild=NULL;
}
BTNode(constT&x)
{
element=x;
lChild=rChild=NULL;
}
BTNode(constT&x,BTNode
{
element=x;
lChild=l;
rChild=r;
}
Telement;
BTNode
};
template
classBinaryTree
{
public:
BinaryTree()
{
root=NULL;
}
~BinaryTree(){Clear();}
boolisEmpty()const
{
returnroot==NULL;
}
voidClear()
{
Clear(root);
}
boolRoot(T&x)const;
voidmakeTree(const&x,BinaryTree
voidbreakTree(T&x,BinaryTree
voidpreOrder()
{
preOrder(root);
}
voidinOrder()
{
inOrder(root);
}
voidpostOrder()
{
postOrder(root);
}
voidleaf()
{
prePrint(root);
}
voidvisit(T&x)
{
cout< } protected: BTNode private: voidClear(BTNode voidprePrint(BTNode voidpreOrder(BTNode voidinOrder(BTNode voidpostOrder(BTNode }; template boolBinaryTree : Root(T&x)const { if(root) { x=root->element; returntrue; } else returnfalse; } template voidBinaryTree : makeTree(const&x,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 voidBinaryTree : preOrder(BTNode { if(t) { visit(t->element); preOrder(t->lChild); preOrder(t->rChild); } } template voidBinaryTree : inOrder(BTNode { if(t) { inOrder(t->lChild); visit(t->element); inOrder(t->rChild); } } template voidBinaryTree : postOrder(BTNode { if(t) { postOrder(t->lChild); postOrder(t->rChild); visit(t->element); } } template voidBinaryTree : Clear(BTNode { if(t) { Clear(t->lChild); Clear(t->rChild); deletet; t=NULL; } } template voidBinaryTree : prePrint(BTNode { if(t) { if((t->lChild==NULL)&&(t->rChild==NULL)){ visit(t->element); return; } prePrint(t->lChild); prePrint(t->rChild); } } template classPrioQueue { public: PrioQueue(intmSize=20); ~PrioQueue(){delete[]q;}; boolIsEmpty()const{returnn==0;} boolIsFull()const{returnn==maxSize;} voidAppend(constT&x); voidServe(T&x); private: voidAdjustDown(intr,intj); voidAdjustUp(intj); T*q; intn,maxSize; }; template PrioQueue : PrioQueue(intmSize) { maxSize=mSize; n=0; q=newT[maxSize]; } template voidPrioQueue : AdjustUp(intj) { inti=j;Ttemp=q[i]; while(i>0&&temp { q[i]=q[(i-1)/2]; i=(i-1)/2; } q[i]=temp; } template voidPrioQueue : Append(constT&x) { if(IsFull()) { cout<<"Overflow"; return; } q[n++]=x; AdjustUp(n-1); } template voidPrioQueue : Serve(T&x) { if(IsEmpty()) { cout<<"Underflow"; return; } x=q[0];q[0]=q[--n]; AdjustDown(0,n-1); } template voidPrioQueue : AdjustDown(intr,intj) { intchild=2*r+1; Ttemp=q[r]; while(child<=j) { if((child if(temp<=q[child])break; q[(child-1)/2]=q[child]; child=2*child+1; } q[(child-1)/2]=temp; } template classHfmTree: publicBinaryTree { public: operatorT()const{returnweight;} TgetW(){returnweight;} voidputW(constT&x) { weight=x; } voidSetNull(){root=NULL;} voidcode(string&c) { code(root,c); } voiddecode(strings); private: Tweight; voidcode(BTNode }; template voidHfmTree : decode(stringdecodeString) { if(codeArray==NULL) { cout<<"尚未编码! "< return; } BTNode for(inti=0;i { if(decodeString[i]! ='0'&&decodeString[i]! ='1') { cout<<"码格式不正确! "< return; } if(searchNode->lChild==NULL&&searchNode->rChild==NULL) { Tvalue=searchNode->element; for(intj=0;j<
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 基本 操作 以及 哈夫曼 编码 译码 系统
![提示](https://static.bingdoc.com/images/bang_tan.gif)