数据结构实验二叉树基本操作概论.docx
《数据结构实验二叉树基本操作概论.docx》由会员分享,可在线阅读,更多相关《数据结构实验二叉树基本操作概论.docx(25页珍藏版)》请在冰点文库上搜索。
数据结构实验二叉树基本操作概论
大学
《数据结构》课程
实验报告
实验名称:
二叉树算法的实现
实验室(中心):
学生信息:
专业班级:
指导教师:
教师评阅意见:
签名:
年月日
实验成绩:
实验完成时间:
2016年
实验三二叉树算法的实现
一、实验目的
1.通过实验,掌握二叉树的建立与存储
2.通过实验,掌握二叉树的遍历方法
二、实验内容及要求
1.练习二叉树的建立与存储
2.练习二叉树的遍历
三、实验设备及软件
计算机、MicrosoftVisualC++6.0软件
四、设计方案(算法设计)
㈠采用的数据结构
本程序栈数据的逻辑结构为非线性结构,存储结构为链式存储。
㈡设计的主要思路
1.建立自己的头文件,内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。
2.建立二叉树,并通过调用函数,,输出先序遍历、中序遍历与后序遍历的结果。
㈢算法描述
StaCrBiTr(BiTr&T)//生成一个二叉树
StaCrBiTrInPOR(BiTr&T)//根据存放在字符串中的先序遍历二叉树结果,生成链接存储的二叉树(若某结点无左孩子或右孩子,则以空格表示其"孩子")。
StaCrBiTrInBr(BiTr&T)//根据嵌套括号表示法的字符串生成链接存储的二叉树(例如:
*pstr="(a(b(c),d(e(,f),g))))。
StaDestroyBiTr(BiTr&T)//销毁
StaPOTra(BiTrT,Sta(*Visit)(BiTrt))//先序(访问结点->遍历左子树->遍历右子树)
StaInOTra(BiTrT,Sta(*Visit)(BiTrt))//中序(遍历左子树->访问结点->遍历右子树)
StaPoOTra(BiTrT,Sta(*Visit)(BiTre))//后序(遍历右子树->访问左子树->访问结点)
StaDisplayBiTrInConcave(BiTrT)//以凹入表示法输出一棵二叉树
StaDisplayBiTrInBracket(BiTrT)//以嵌套括号表示法输出一棵二叉树
五、程序代码
#include
#include
#include
#include
#include
#defineTrue1
#defineFalse0
#defineOK1
#defineError0
#defineInFea-1
#defineOverFlow-2
typedefintSta;
typedefcharType;
typedefstructBiTrN//定义二叉树结点结构
{
Typedata;
structBiTrN*lchild,*rchild;//左右指针域
}BiTrN,*BiTr;
StaCrBiTrInPOR(BiTr&T);
StaCrBiTrInBr(BiTr&T);
char*pstr;
StaCrBiTr(BiTr&T)//生成一个二叉树
{
inti,len,C=0;
charstr[200];
printf("请选择建立二叉树方法的序号:
\n\n");
printf("1.按先序遍历的结果输入二叉树\n");
printf("2.按嵌套括号表示法输入二叉树\n");
do{
gets(str);
C=atoi(str);
}while(C<1||C>2);
if(C==1)
{
printf("请输入先序遍历二叉树的结果,程序据此建立二叉树,对于叶子结点以空格表示.\n例如:
abc__de_g__f___(回车),建立如下二叉树:
\n\n");
printf("a\n\n");
printf("/\n\n");
printf("b\n\n");
printf("/\\\n\n");
printf("cd\n\n");
printf("/\\\n\n");
printf("ef\n\n");
printf("\\\n\n");
printf("g\n\n");
pstr=gets(str);
len=strlen(str);
for(i=len;i<180;++i)
str[i]='';
str[i]=0;
CrBiTrInPOR(T);
}
else
{
printf("请输入嵌套括号表示法表示的二叉树,程序据此建立二叉树.\n例如:
(a(b(c,d(e(,g),f))))(回车),建立如下二叉树:
\n\n");
printf("a\n\n");
printf("/\n\n");
printf("b\n\n");
printf("/\\\n\n");
printf("cd\n\n");
printf("/\\\n\n");
printf("ef\n\n");
printf("\\\n\n");
printf("g\n\n");
pstr=gets(str);
CrBiTrInBr(T);
}
returnOK;
}
StaCrBiTrInPOR(BiTr&T)//根据存放在字符串中的先序遍历二叉树结果,生成链接存储的二叉树(若某结点无左孩子或右孩子,则以空格表示其"孩子")。
{
if(!
(*pstr)||*pstr=='')
{
T=NULL;
pstr++;
}
else
{
T=(BiTrN*)malloc(sizeof(BiTrN));
if(!
T)exit(OverFlow);
T->data=*(pstr++);
CrBiTrInPOR(T->lchild);
CrBiTrInPOR(T->rchild);
}
returnOK;
}
StaCrBiTrInBr(BiTr&T)//根据嵌套括号表示法的字符串生成链接存储的二叉树(例如:
*pstr="(a(b(c),d(e(,f),g))))。
{
BiTrstack[100],p;
inttop=0,k;
T=NULL;
while(*pstr)
{
switch(*pstr)
{
case'(':
stack[top++]=p;k=1;break;
case')':
top--;break;
case',':
k=2;break;
case'':
break;
default:
p=(BiTr)malloc(sizeof(BiTrN));
p->data=*pstr;
p->lchild=p->rchild=NULL;
if(!
T)T=p;
else
{
switch(k)
{
case1:
stack[top-1]->lchild=p;break;
case2:
stack[top-1]->rchild=p;break;
}
}
}
pstr++;
}
returnOK;
}
StaDestroyBiTr(BiTr&T)//销毁
{
if(T)
{
if(T->lchild)DestroyBiTr(T->lchild);
if(T->rchild)DestroyBiTr(T->rchild);
free(T);
T=NULL;
returnOK;
}
else
returnOK;
}
StaPElem(BiTrt)
{
printf("%c",t->data);
returnOK;
}
StaPOTra(BiTrT,Sta(*Visit)(BiTrt))//先序(访问结点->遍历左子树->遍历右子树)
{
if(T){
if((*Visit)(T))
if(POTra(T->lchild,Visit))
if(POTra(T->rchild,Visit))
returnOK;
returnError;
}
elsereturnOK;
}
StaInOTra(BiTrT,Sta(*Visit)(BiTrt))//中序(遍历左子树->访问结点->遍历右子树)
{
if(T){
if(InOTra(T->lchild,Visit))
if((*Visit)(T))
if(InOTra(T->rchild,Visit))
returnOK;
returnError;
}
elsereturnOK;
}
StaPoOTra(BiTrT,Sta(*Visit)(BiTre))//后序(遍历右子树->访问左子树->访问结点)
{
if(T){
if(PoOTra(T->lchild,PElem))
if(PoOTra(T->rchild,PElem))
if((*Visit)(T))
returnOK;
returnError;
}
elsereturnOK;
}
StaDisplayBiTrInConcave(BiTrT)//以凹入表示法输出一棵二叉树
{
BiTrstack[100],p;
intlevel[100][2],top,n,i,width=4;
charchildtype[3]={'L','R','D'};
constintMaxWidth=30;
if(T)
{
top=0;
stack[top]=T;
level[top][0]=width;
level[top][1]=2;
while(top>=0)
{
p=stack[top];
n=level[top][0];
for(i=1;i<=n;i++)printf("");
printf("%c(%c)",p->data,childtype[level[top][1]]);
for(i=n+1;i<=MaxWidth;i+=2)printf("━");
printf("\n\n");
top--;
if(p->rchild)//右子树根结点入栈
{
top++;
stack[top]=p->rchild;
level[top][0]=n+width;
level[top][1]=1;
}
if(p->lchild)//左子树根结点入栈
{
top++;
stack[top]=p->lchild;
level[top][0]=n+width;
level[top][1]=0;
}
}
}
else
printf("提示:
该二叉树是一棵空二叉树!
\n\n");
returnOK;
}
StaDisplayBiTrInBracket(BiTrT)//以嵌套括号表示法输出一棵二叉树
{
if(T)
{
printf("%c",T->data);
if(T->lchild||T->rchild)
{
printf("(");
if(T->lchild)DisplayBiTrInBracket(T->lchild);
if(T->rchild)printf(",");
if(T->rchild)DisplayBiTrInBracket(T->rchild);
printf(")");
}
}
else
printf("提示:
该二叉树是一棵空二叉树!
");
returnOK;
}
voidmain()
{
BiTrT;
charch,j;
charstr[200];
intC,F=1,len,i;
Statemp;
printf("本程用于序实现二叉树的操作,可以进行建立二叉树,递归先序、中序、后序遍历等操作.\n\n");
CrBiTr(T);
while(F)
{
printf("请选择需要进行操作的序号:
\n\n");
printf("1.递归先序遍历\n");
printf("2.递归中序遍历\n");
printf("3.递归后序遍历\n");
printf("4.凹入表示法输出二叉树\n");
printf("5.嵌套括号表示法输出二叉树\n");
printf("6.重新构建二叉树\n");
printf("7.退出程序\n\n");
scanf("%d",&C);
switch(C)
{
case1:
if(T)
{
printf("提示:
先序遍历二叉树:
\n");
POTra(T,PElem);//先序递归遍历二叉树
printf("\n\n");
}
else
printf("提示:
二叉树为空!
\n\n");
break;
case2:
if(T)
{
printf("提示:
中序遍历二叉树:
\n");
InOTra(T,PElem);//中序递归遍历二叉树
printf("\n\n");
}
else
printf("提示:
二叉树为空!
\n\n");
break;
case3:
if(T)
{
printf("提示:
后序遍历二叉树:
\n");
PoOTra(T,PElem);//后序递归遍历二叉树
printf("\n\n");
}
else
printf("提示:
二叉树为空!
\n\n");
break;
case4:
DisplayBiTrInConcave(T);
break;
case5:
printf("(");
DisplayBiTrInBracket(T);
printf(")\n\n");
break;
case6:
DestroyBiTr(T);
CrBiTr(T);
break;
default:
F=0;
printf("提示:
程序运行结束,按任意键退出!
\n\n");
getch();
}
}
DestroyBiTr(T);
}
六、测试结果及说明
二叉树算法实现的程序编译结果没有错误和提醒,测试结果都是正确的,没有出现任何的错误。
七、实验体会
在编程对二叉树算法实现之前需明确二叉树是一种非线性结构,是一种层次结构。
二叉树的前中后序遍历的原理尤为重要,要理解它的本质都是一种递归调用的思想。
二叉树提升实验
(一)、对二叉树进行遍历、计算高度和叶子节点等
一、设计方案
㈠采用的数据结构
本程序采用的数据逻辑结构为非线性结构,存储结构为链式存储结构,算法的总体功能是建立二叉树,计算二叉树的高度、叶子节点、总节点数以及遍历二叉树。
㈡设计的主要思路
由用户确定元素构建一个二叉树,然后对二叉树进行遍历,求其高度、叶子节点数、节点总数。
㈢算法描述
voidBinaryTree:
:
CreateBinTree(BinTreeNode*&subTree)
//创建一个二叉树
intBinaryTree:
:
Height(BinTreeNode*subTree)const
//利用二叉树后序遍历算法计算二叉树的高度或深度;
voidBinaryTree:
:
destroy(BinTreeNode*&subTree)
//私有函数:
删除根为subTree的子树
voidBinaryTree:
:
BinaryTreeCount(BinTreeNode*BT,int&m1,int&m2)
//分别统计出二叉树中所有结点数和叶子结点数
voidBinaryTree:
:
Output(BinTreeNode*subtree)
//利用二叉树后序遍历算法输出二叉树的结点
二、主要代码
#include
usingnamespacestd;
template
structBinTreeNode
{Tdata;
BinTreeNode*leftChild,*rightChild;
BinTreeNode()
{
leftChild=NULL;
rightChild=NULL;
}
BinTreeNode(Tx,BinTreeNode*left=NULL,BinTreeNode*right=NULL)
{
data=x;
leftChild=left;
rightChild=right;
}
};
template
classBinaryTree
{
public:
BinaryTree(){root=NULL;}
BinaryTree(Tvalue)
{RefValue=value;root=NULL;}
~BinaryTree(){destroy(root);}
boolIsEmpty(){returnroot==NULL;}
intHeight(){returnHeight(root);}
intSize(){returnSize(root);}
BinTreeNode*getRoot(){returnroot;}
BinTreeNode*LeftChild(BinTreeNode*cur)
{
return(cur!
=NULL)?
cur->leftChild:
NULL;
}
BinTreeNode*RightChild(BinTreeNode*cur)
{
return(cur!
=NULL)?
cur->rightChild:
NULL;
}
voidOutput(BinTreeNode*subtree);
voidBinaryTreeCount(BinTreeNode*BT,int&m1,int&m2);
voidSetRefValue(T&M){RefValue=M;}
voidSetroot(BinTreeNode*N){root=N;}
voidCreateBinTree(BinTreeNode*&subTree);
protected:
BinTreeNode*root;
TRefValue;
voiddestroy(BinTreeNode*&subTree);
intHeight(BinTreeNode*subTree)const;
intSize(BinTreeNode*subTree)const;
BinTreeNode*Parent(BinTreeNode*subTree,BinTreeNode*cur);
friendostream&operator<<(ostream&out,BinaryTree&Tree);
};
template
voidBinaryTree:
:
CreateBinTree(BinTreeNode*&subTree)
{Titem;
cin>>item;
if(item!
=RefValue)
{subTree=newBinTreeNode(item);
if(subTree==NULL)
{cerr<<"存储分配错!
"<(1);}
CreateBinTree(subTree->leftChild);//递归建立左子
CreateBinTree(subTree->rightChild);//递归建立右子树
}
else{subTree=NULL;}
};
template
intBinaryTree:
:
Height(BinTreeNode*subTree)const//利用二叉树后序遍历算法计算二叉树的高度或深度;
{
if(subTree==NULL)return0;
else
{
inti=Height(subTree->leftChild);
intj=Height(subTree->rightChild);
return(ij+1:
i+1;
}
};
template
voidBinaryTree:
:
destroy(BinTreeNode*&subTree)//私有函数:
删除根为subTree的子树
{if(subTree!
=NULL)
{destroy(subTree->leftChild);//删除左子树
destroy(subTree->rightChild);//删除右子树
deletesubTree;//删除根结点
}
};
template
voidBinaryTree:
:
BinaryTreeCount(BinTreeNode*BT,int&m1,int&m2)//分别统计出二叉树中所有结点数和叶子结点数
{
if(BT!
=NULL)
{m1++;
if(BT->leftChild==NULL&&BT->rightChild==NULL)
m2++;
BinaryTreeCount(BT->leftChild,m1,m2);
BinaryTreeCount(BT->rightChild,m1,m2);
}
elsereturn;
return;
};
template
voidBinaryTree:
:
Output(BinTreeNode*subtree)//利用二叉树后序遍历算法输出二叉树的结点
{
if(subtree!
=NULL)
{
cout<data<<'\t';
Output(subtree->leftChild);
Output(subtree->rightChild