山东大学数据结构实验报告五.docx
《山东大学数据结构实验报告五.docx》由会员分享，可在线阅读，更多相关《山东大学数据结构实验报告五.docx（21页珍藏版）》请在冰点文库上搜索。
山东大学数据结构实验报告五
数据结构实验报告——实验五
实验题目：
排序算法
学号：
1
日期：
2015.12.11
班级：
计机14.1
：
方铮
Email：
liu3.
实验目的：
二叉树操作
任务要求：
一、实验目的
1、掌握二叉树的基本概念，链表描述方法；遍历方法。
二、实验容
创建二叉树类。
二叉树的存储结构使用链表。
提供操作:
前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。
对建立好的二叉树，执行上述各操作。
接收键盘录入的二叉树前序序列和中序序列（各元素各不相同），输出该二叉树的后序序列。
软件环境：
Win7操作系统
开发工具：
visualC++6.0
实验代码：
#include
#include
#include
#include
usingnamespacestd;
#defineMaxSize100
#defineMaxWidth40
#include
#include
#include
#include
typedefcharElemType;
typedefstructtnode
{
ElemTypedata;
structtnode*lchild,*rchild;
}BTNode;
/*建立二叉树算法描述：
用ch扫描采用括号表示法表示二叉树的字符串Str。
分以下几种情况：
1、若ch='（'则将前面刚创建的结点作为双亲结点进栈，并置k=1,表示其后创建的结点将做为这个结点的左孩子
结点。
2、若ch='）'表示栈中结点的左右孩子结点处理完毕，退栈。
3、若ch=','表示其后创建的结点为右孩子结点
4、其他情况表示要创建一个结点，并根据k值建立它与栈中结点之间的关系，当k=1时，表示这个结点作为栈中
结点的左孩子结点，当k=2时，表示这个结点作为栈中结点的右孩子结点。
如此循环直到str处理完毕。
算法中
使用一个栈st保存双亲结点，top为其栈指针，k指定其后处理的结点是双亲结点（保存在栈中）的左孩子结点
（k=1）还是右孩子结点（k=2）。
*/
voidCreateBtree（BTNode*&bt,char*str）//由str创建二叉链bt
{
BTNode*st[MaxSize],*p=NULL;
inttop=-1,k,j=0;
charch;
bt=NULL;//建立的二叉树初始为空
ch=str[j];
while（ch!
='\0'）//str未扫描完时循环
{
switch（ch）
{
case'（':
top++;st[top]=p;k=1;break;//为左孩子结点
case'）':
top--;break;
case',':
k=2;break;
default:
p=（BTNode*）malloc（sizeof（BTNode））;
p->data=ch;p->lchild=p->rchild=NULL;
if（bt==NULL）
bt=p;
else
{
switch（k）
{
case1:
st[top]->lchild=p;break;
case2:
st[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
/*求二叉树高度算法：
递归模型如下
if（b==NULL）f（b）=0;
elsef（b）=max{f（b）->lchild,f（b）->rchild}+1;
*/
intBTHeight（BTNode*bt）
{
intlchilddep,rchilddep;
if（bt==NULL）
return0;
else
{
lchilddep=BTHeight（bt->lchild）;
rchilddep=BTHeight（bt->rchild）;
return（lchilddep>rchilddep）?
（lchilddep+1）:
（rchilddep+1）;
}
}
/*求二叉树结点个数算法：
递归模型如下
if（bt==NULL）f（b）=1;
elsef（bt）=f（bt->lchild）+f（bt->rchild）+1;
*/
intNodeCount（BTNode*bt）
{
intnum1,num2;
if（bt==NULL）
return0;
else
{
num1=NodeCount（bt->lchild）;
num2=NodeCount（bt->rchild）;
returnnum1+num2+1;
}
}
/*求二叉树叶子结点个数算法：
递归模型如下
if（bt==NULL）f（bt）=0;
if（bt为叶子结点）f（bt）=1;
elsef（bt）=f（bt->lchild）+f（bt->rchild）;
*/
intLeafCount（BTNode*bt）
{
intnum1,num2;
if（bt==NULL）
return0;
else
if（bt->lchild==NULL&&bt->rchild==NULL）
return1;
else
{
num1=LeafCount（bt->lchild）;
num2=LeafCount（bt->rchild）;
returnnum1+num2;
}
}
/*以括号表示法输出二叉树运算算法*/
voidDispBtreel（BTNode*bt）
{
if（bt!
=NULL）
{
cout<data;
if（bt->lchild!
=NULL||bt->rchild!
=NULL）
{
cout<<"（";
DispBtreel（bt->lchild）;
if（bt->rchild!
=NULL）
cout<<",";
DispBtreel（bt->rchild）;
cout<<"）";
}
}
}
/*===========================================================================
*Functionname:
BT_PreOrder
*Parameter:
root:
树根节点指针
*Precondition:
None
*Description:
前序遍历
===========================================================================*/
voidBT_PreOrder（BTNode*bt）
{
if（NULL!
=bt）
{
cout<data;//visit（bt）;
BT_PreOrder（bt->lchild）;
BT_PreOrder（bt->rchild）;
}
}
/*===========================================================================
*Functionname:
BT_InOrder
*Parameter:
root:
树根节点指针
*Precondition:
None
*Description:
中序遍历
*Returnvalue:
void
===========================================================================*/
voidBT_InOrder（BTNode*bt）
{
if（NULL!
=bt）
{
BT_InOrder（bt->lchild）;
cout<data;//visit（bt）;
BT_InOrder（bt->rchild）;
}
}
/*===========================================================================
*Functionname:
BT_PostOrder
*Parameter:
root:
树根节点指针
*Precondition:
None
*Description:
后序遍历
*Returnvalue:
void
===========================================================================*/
voidBT_PostOrder（BTNode*bt）
{
if（NULL!
=bt）
{
BT_PostOrder（bt->lchild）;
BT_PostOrder（bt->rchild）;
cout<data;//visit（bt）;
}
}
/*===========================================================================
*Functionname:
BT_LevelOrder
*Parameter:
root:
树根节点指针
*Precondition:
NULL!
=root
*Description:
层序遍历
*Returnvalue:
void
===========================================================================*/
voidBT_LevelOrder（BTNode*bt）
{
queueq;
tnode*treePtr;
assert（NULL!
=bt）;
q.push（bt）;
while（!
q.empty（））
{
treePtr=q.front（）;
q.pop（）;
cout<data;//visit（bt）;treePtr;
if（NULL!
=treePtr->lchild）
{
q.push（treePtr->lchild）;
}
if（NULL!
=treePtr->rchild）
{
q.push（treePtr->rchild）;
}
}
}
//先序中序求后序
intfind（charc,charA[],ints,inte）/*找出中序中根的位置。
*/
{
inti;
for（i=s;i<=e;i++）
if（A[i]==c）
returni;
}
/*其中pre[]表示先序序，pre_s为先序的起始位置，pre_e为先序的终止位置。
*/
/*其中in[]表示中序，in_s为中序的起始位置，in_e为中序的终止位置。
*/
/*pronum（）求出pre[pre_s～pre_e]、in[in_s～in_e]构成的后序序列。
*/
voidpronum（charpre[],intpre_s,intpre_e,charin[],intin_s,intin_e）
{
charc;
intk;
if（in_s>in_e）return;/*非法子树，完成。
*/
if（in_s==in_e）{printf（"%c",in[in_s]）;/*子树子仅为一个节点时直接输出并完成。
*/
return;
}
c=pre[pre_s];/*c储存根节点。
*/
k=find（c,in,in_s,in_e）;/*在中序中找出根节点的位置。
*/
pronum（pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1）;/*递归求解分割的左子树。
*/
pronum（pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e）;/*递归求解分割的右子树。
*/
printf（"%c",c）;/*根节点输出。
*/
}
#include
#include
#include
#include
#include
#include"tree.h"
#defineSIZE100
usingnamespacestd;
typedefstructBiTNode//定义二叉树节点结构
{
chardata;//数据域
structBiTNode*lchild,*rchild;//左右孩子指针域
}BiTNode,*BiTree;
intvisit（BiTreet）;
voidCreateBiTree（BiTree&T）;//生成一个二叉树
voidPreOrder（BiTree）;//递归先序遍历二叉树
voidInOrder（BiTree）;//递归中序遍历二叉树
voidPostOrder（BiTree）;//递归后序遍历二叉树
voidLeverTraverse（BiTreeT）;//非递归层次遍历
intTreeDepth（BiTreeT）
{
inthl,hr,max;
if（T）{
hl=TreeDepth（T->lchild）;//求左深度
hr=TreeDepth（T->rchild）;//求右深度
max=hl>hr?
hl:
hr;//取左右深度的最大值
//求结点数
return（max+1）;
}
elsereturn（0）;
}
intTreeNodeNUM（BiTreeT）
{intN=0;
inthl,hr,max;
if（T）
{
if（T）
{
cout<data;N=N+1;//访问结点
PreOrder（T->lchild）;//遍历左子树
PreOrder（T->rchild）;//遍历右子树
}
returnN;
}
else
return（0）;
}
//主函数
voidmain（）
{
BiTreeT;
charch;
intflag=1;
cout<<"二叉树"<cout<<"请建立二叉树。
"<CreateBiTree（T）;//初始化队列
getchar（）;
while（flag）
{
cout<<"请选择:
"<cout<<"1.先序遍历"<cout<<"2.中序遍历"<cout<<"3.后序遍历"<cout<<"4.层次遍历"<cout<<"5.树的深度和节点个数"<cout<<"6.根据前序和中序确定后序"<cout<<"0.退出程序"<cin>>ch;
switch（ch）
{
case'1':
if（T）
{
cout<<"递归先序遍历二叉树:
";
PreOrder（T）;
cout<}
else
cout<<"二叉树为空!
"<break;
case'2':
if（T）
{
cout<<"递归中序遍历二叉树:
";
InOrder（T）;
cout<}
else
cout<<"二叉树为空!
"<break;
case'3':
if（T）
{
cout<<"递归后序遍历二叉树:
";
PostOrder（T）;
cout<}
else
cout<<"二叉树为空!
"<break;
case'4':
if（T）
{
cout<<"层序遍历二叉树:
";
LeverTraverse（T）;
cout<}
else
cout<<"二叉树为空!
";
break;
case'5':
if（T）
{intdepth=0,NodeNum=0;
depth=TreeDepth（T）;NodeNum=TreeNodeNUM（T）;//求树的深度及叶子数
cout<<"树的深度"<}
else
cout<<"二叉树为空!
";
break;
case'6':
if（T）
{
cout<<"输入所要求的树的前序：
";
strings0;
cin>>s0;
constchar*p0=s0.c_str（）;
char*pre=newchar[strlen（p0）+1];
strcpy（pre,p0）;
cout<<"输入所要求的树的中序：
";
strings1;
cin>>s1;
constchar*p1=s1.c_str（）;
char*in=newchar[strlen（p1）+1];
strcpy（in,p1）;
cout<<"树的后序为：
";
pronum（pre,0,strlen（in）-1,in,0,strlen（pre）-1）;
}
else
cout<<"二叉树为空!
";
break;
default:
flag=0;
cout<<"程序运行结束，按任意键退出!
";
cout<}
}
}
//建立二叉树
voidCreateBiTree（BiTree&T）
{
charch;
cin>>ch;//读入一个字符
if（ch=='#'）
T=NULL;
else
{
T=（BiTNode*）malloc（sizeof（BiTNode））;//生成一个新结点
T->data=ch;
CreateBiTree（T->lchild）;//生成左子树
CreateBiTree（T->rchild）;//生成右子树
}
}
//先序遍历的递归
voidPreOrder（BiTreeT）
{
if（T）
{
cout<data;//访问结点
PreOrder（T->lchild）;//遍历左子树
PreOrder（T->rchild）;//遍历右子树
}
}
//中序遍历的递归
voidInOrder（BiTreeT）
{
if（T）
{
InOrder（T->lchild）;//遍历左子树
cout<data;//访问结点
InOrder（T->rchild）;//遍历右子树
}
}
//后序遍历的递归
voidPostOrder（BiTreeT）
{
if（T）
{
PostOrder（T->lchild）;//遍历左子树
PostOrder（T->rchild）;//访问结点
cout<data;//遍历右子树
}
}
voidLeverTraverse（BiTreeT）
{//非递归层次遍历
queueQ;
BiTreep;
p=T;
if（visit（p）==1）
Q.push（p）;
while（!
Q.empty（））
{
p=Q.front（）;
Q.pop（）;
if（visit（p->lchild）==1）
Q.push（p->lchild）;
if（visit（p->rchild）==1）
Q.push（p->rchild）;
}
}
intvisit（BiTreeT）
{
if（T）
{
cout<data;
return1;
}
else
return0;
}
实验结果：
升级会员 