二叉树的基本操作及哈夫曼编码译码系统的实现Word下载.docx
《二叉树的基本操作及哈夫曼编码译码系统的实现Word下载.docx》由会员分享，可在线阅读，更多相关《二叉树的基本操作及哈夫曼编码译码系统的实现Word下载.docx（15页珍藏版）》请在冰点文库上搜索。
软件：
Windows操作系统、MicrosoftVisualC++6.0
三、实验原理及内容
实验源代码：
#include<
assert.h>
#include<
iostream.h>
template<
classT>
classQueue
{
public:
Queue（）{};
~Queue（）{};
virtualvoidEnQueue（constT&
x）=0;
virtualvoidDeQueue（）=0;
virtualTFront（）=0;
virtualboolIsEmpty（）const=0;
virtualboolIsFull（）const=0;
};
classSeqQueue:
publicQueue<
T>
SeqQueue（intMaxQueSize）;
~SeqQueue（）{delete[]q;
}
voidEnQueue（constT&
x）;
voidDeQueue（）;
TFront（）;
boolIsEmpty（）const;
boolIsFull（）const;
private:
intfront,rear;
intMaxSize;
T*q;
SeqQueue<
:
SeqQueue（intMaxQueSize）
MaxSize=MaxQueSize;
q=newT[MaxSize];
front=rear=0;
boolSeqQueue<
IsEmpty（）const
returnfront==rear;
IsFull（）const
return（rear+1）%MaxSize==front;
voidSeqQueue<
EnQueue（constT&
x）
assert（!
IsFull（））;
q[（rear=（rear+1）%MaxSize）]=x;
DeQueue（）
IsEmpty（））;
front=（front+1）%MaxSize;
TSeqQueue<
Front（）
returnq[（front+1）%MaxSize];
classBTree;
classBTNode
BTNode（）{lchild=rchild=0;
}
BTNode（constT&
e）
{
element=e;
lchild=rchild=0;
}
BTNode（constT&
e,BTNode<
*l,BTNode<
*r）
lchild=l;
rchild=r;
Telement;
BTNode<
*lchild,*rchild;
friendclassBTree<
;
friendvoidVisit（BTNode<
*）;
};
template<
voidVisit（BTNode<
*p）
cout<
<
p->
element<
"
"
classBTree
BTree（）{root=NULL;
}
~BTree（）{}
boolIsEmpty（）const;
boolRoot（T&
x）const;
voidMakeTree（constT&
e,BTree<
&
left,BTree<
right）;
voidBreakTree（T&
left,BTree<
voidPreOrder（void（*Visit）（BTNode<
*u））
PreOrder（Visit,root）;
voidInOrder（void（*Visit）（BTNode<
InOrder（Visit,root）;
voidPostOrder（void（*Visit）（BTNode<
*u））
PostOrder（Visit,root）;
voidExchange（）;
voidLayerOrder（）;
intHigh（）;
intLeaves（）;
voidDeltree（）;
BTree<
CopyBTree（）;
*root;
voidPreOrder（void（*Visit）（BTNode<
*u）,BTNode<
*t）;
*u）,BTNode<
voidExch（BTNode<
*）;
voidLeaf（BTNode<
*,int&
）;
intHighs（BTNode<
boolBTree<
returnroot==NULL;
//返回根节点
Root（T&
x）const
if（root）
{
x=root->
element;
returntrue;
elsereturnfalse;
//构造二叉树
voidBTree<
MakeTree（constT&
e,BTree<
right）
{
*p;
p=newBTNode<
（e,left.root,right.root）;
left.root=right.root=0;
root=p;
//删除二叉树的所有节点
BreakTree（T&
e,BTree<
left,BTree<
right）
p=root;
if（p）
e=p->
left.root=p->
lchild;
right.root=p->
rchild;
}
//线序遍历二叉树
PreOrder（void（*Visit）（BTNode<
*u）,BTNode<
*t）
if（t）
Visit（t）;
if（t->
lchild）
PreOrder（Visit,t->
lchild）;
rchild）
rchild）;
//中序遍历二叉树
InOrder（void（*Visit）（BTNode<
if（t）
if（t->
InOrder（Visit,t->
Visit（t）;
//后序遍历二叉树
PostOrder（void（*Visit）（BTNode<
PostOrder（Visit,t->
//层次遍历
LayerOrder（）
if（root==0）
cout<
TreeisEmpty!
!
endl;
return;
*p=root;
x;
SeqQueue<
>
sq（10）;
sq.EnQueue（*p）;
while（!
sq.IsEmpty（））
x=sq.Front（）;
x.element<
if（x.lchild）
sq.EnQueue（*x.lchild）;
if（x.rchild）
sq.EnQueue（*x.rchild）;
sq.DeQueue（）;
//求二叉树树高
intBTree<
High（）
inth=Highs（root）;
returnh;
Highs（BTNode<
*u）
if（u==0）return0;
intlch,rch;
lch=Highs（u->
rch=Highs（u->
if（lch>
rch）returnlch+1;
elsereturnrch+1;
//求二叉树叶子节点数
Leaves（）
intcount=0;
Leaf（root,count）;
returncount;
Leaf（BTNode<
*t,int&
count）
if（（t->
lchild==0）&
（t->
rchild==0））
{Visit（t）;
count++;
Leaf（t->
lchild,count）;
rchild,count）;
//删除二叉树
Deltree（）
if（root==NULL）return;
Tx;
BTree<
left,right;
BreakTree（x,left,right）;
left.Deltree（）;
right.Deltree（）;
delete（root）;
root=NULL;
//二叉树的复制
BTree<
CopyBTree（）
if（root==NULL）
zero;
returnzero;
chleft,chright;
change,changeleft,changeright;
BreakTree（x,chleft,chright）;
changeleft=chleft.CopyBTree（）;
changeright=chright.CopyBTree（）;
change.MakeTree（x,changeleft,changeright）;
returnchange;
//二叉树左右子树的交换
Exchange（）
Exch（root）;
Exch（BTNode<
*p）
if（p!
=NULL）
BTNode<
*temp;
temp=p->
p->
lchild=p->
rchild;
rchild=temp;
Exch（p->
voidmain（）
char>
a,b,c,d,e,f,g,h,j,k,left,right;
j.MakeTree（'
J'
left,right）;
g.MakeTree（'
G'
f.MakeTree（'
F'
j,g）;
h.MakeTree（'
H'
e.MakeTree（'
E'
h,f）;
d.MakeTree（'
D'
e,right）;
k.MakeTree（'
K'
c.MakeTree（'
C'
k,right）;
b.MakeTree（'
B'
left,c）;
a.MakeTree（'
A'
d,b）;
LayerOrder：
a.LayerOrder（）;
树A高度:
a.High（）<
树A叶子:
endl<
树A叶子结点数：
a.Leaves（）<
CopyAtoB：
CheckTreeB:
b=a.CopyBTree（）;
ThePreOrderofTreeBis：
b.PreOrder（Visit）;
TheInOrderofTreeBis：
b.InOrder（Visit）;
DeleteTreeA:
a.Deltree（）;
CheckTreeA:
ExchangeTreeB,Successful!
b.Exchange（）;
ChecktheresultofTreeB:
b.LayerOrder（）;
四、实验小结（包括问题和解决方法、心得体会、意见与建议等）
五、指导教师评语
成绩
批阅人
日期
升级会员 