实验6二叉树及其应用.docx
《实验6二叉树及其应用.docx》由会员分享，可在线阅读，更多相关《实验6二叉树及其应用.docx（23页珍藏版）》请在冰点文库上搜索。
实验6二叉树及其应用
实验6：
二叉树及其应用
一、实验目的
树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。
二、问题描述
首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。
其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。
如算术表达式：
a+b*（c-d）-e/f
三、实验要求
1、如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算
a）统计叶子结点的个数。
b）求二叉树的深度。
2、十进制的四则运算的计算器可以接收用户来自键盘的输入。
3、由输入的表达式字符串动态生成算术表达式所对应的二叉树。
4、自动完成求值运算和输出结果。
四、实验环境
PC微机
DOS操作系统或Windows操作系统
TurboC程序集成环境或VisualC++程序集成环境
五、实验步骤
1、根据二叉树的各种存储结构建立二叉树；
2、设计求叶子结点个数算法和树的深度算法；
3、根据表达式建立相应的二叉树，生成表达式树的模块；
4、根据表达式树，求出表达式值，生成求值模块；
5、程序运行效果，测试数据分析算法。
六、功能分析
存储结构
typedefunion{
intOperator;//操作符
floatOperand;//操作数
}Int_Float;
//表达式树
typedefstructBinaryTreeNode{
Int_FloatData;//数据域
intIsOperator;//判断是不是操作数的标志位
structBinaryTreeNode*RChild;//左子树
structBinaryTreeNode*LChild;//右子树
}BiTreeNode,*lpBiTreeNode;
//栈的定义
typedefstruct{
lpBiTreeNode*base;
lpBiTreeNode*top;
intstacksize;
}SqStack;
函数一览表
lpBiTreeNodeGetTop（SqStacks）;//取栈顶结点函数
intIsEmpty（SqStacks）;//判空函数
intInitStack（SqStack&s）;//初始化栈函数
intPop（SqStack&s,lpBiTreeNode&e）;//出栈函数
intPush（SqStack&s,lpBiTreeNodee）;//入栈函数
intIn（intc,int*op）;//判断c是否在op中
intPrecede（inttheta1,inttheta2）;//比较运算符号的优先级
intisNum（intc）;//判断是不是数
intGetInput（Int_Float*Result）;//读入输入的数
lpBiTreeNodeCreateBiTree（）;//创建二叉树
boolcalculate（lpBiTreeNodeRoot,float*result）;//计算二叉树化表达式的值
intgetLeafNum（lpBiTreeNodeRoot）;//计算二叉树的叶子结点数
intgetDepth（lpBiTreeNodeRoot）;//计算二叉树的深度
计算叶子节点数的算法分析
计算二叉树深度的算法分析
递归，核心在于
num=numleft+numright
Intnum（二叉树*p）{
If（空树）return0；
Elseif（一个节点的树）return1；
Else{
Returnnum（num（左子树）+num（右子树））；
}
}
递归，核心在于depth=max（leftdepth,righydepth）+1
Intdepth（二叉树*p）{
If（空树）return0；
Elseif（一个节点的树）return1；
Else{
Return
max（depth（左子树），depth（右子树）+1）；
}
}
七、程序代码
#include
#include
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineERROR0
#defineNUMBER1
#defineSIMBLE2
intOP[8]={'+','-','*','/','（','）','#',0};//运算符数组
//共用体
typedefunion
{
intOperator;//操作符
floatOperand;//操作数
}Int_Float;
//表达式树
typedefstructBinaryTreeNode
{
Int_FloatData;//数据域
intIsOperator;//判断是不是操作数的标志位
structBinaryTreeNode*RChild;//左子树
structBinaryTreeNode*LChild;//右子树
}BiTreeNode,*lpBiTreeNode;
//栈的定义
typedefstruct{
lpBiTreeNode*base;
lpBiTreeNode*top;
intstacksize;
}SqStack;
//函数声明区
lpBiTreeNodeGetTop（SqStacks）;//取栈顶结点函数
intIsEmpty（SqStacks）;//判空函数
intInitStack（SqStack&s）;//初始化栈函数
intPop（SqStack&s,lpBiTreeNode&e）;//出栈函数
intPush（SqStack&s,lpBiTreeNodee）;//入栈函数
intIn（intc,int*op）;//判断c是否在op中
intPrecede（inttheta1,inttheta2）;//比较运算符号的优先级
intisNum（intc）;//判断是不是数
intGetInput（Int_Float*Result）;//读入输入的数
lpBiTreeNodeCreateBiTree（）;//创建二叉树
boolcalculate（lpBiTreeNodeRoot,float*result）;//计算二叉树化表达式的值
intgetLeafNum（lpBiTreeNodeRoot）;//计算二叉树的叶子结点数
intgetDepth（lpBiTreeNodeRoot）;//计算二叉树的深度
intmain（）//主函数
{
lpBiTreeNodeRoot;//二叉树
floatresult;//表达式运算结果
if（Root=CreateBiTree（））//若创建二叉树失败则不会执行if操作
{
printf（"二叉树叶子数=%d\n",getLeafNum（Root））;
printf（"二叉树的深度=%d\n",getDepth（Root））;
if（calculate（Root,&result））//计算结果
{
printf（"表达式的值=%0.2f\n",result）;
}
else
printf（"ERROR"）;
}
else
printf（"INPUTERROR\n"）;
printf（"********************************\n"）;
return0;
}
lpBiTreeNodeGetTop（SqStacks）
{
lpBiTreeNodee;
if（s.top==s.base）//栈为空情况
returnNULL;
e=*（s.top-1）;//top指针指向栈顶元素的后一个空间
returne;
}
intIsEmpty（SqStacks）
{
if（s.top==s.base）//栈为空
return1;
else
return0;
}
intInitStack（SqStack&s）
{
s.base=（lpBiTreeNode*）malloc（STACK_INIT_SIZE*sizeof（lpBiTreeNode））;//malloc栈基址空间
if（!
s.base）//分配空间失败
return0;
s.top=s.base;//栈顶指针
s.stacksize=STACK_INIT_SIZE;//初始化栈大小
return1;
}
intPop（SqStack&s,lpBiTreeNode&e）
{
if（s.top==s.base）//空栈
return0;
s.top--;//top指针前移
e=*s.top;//取栈顶元素
return1;
}
intPush（SqStack&s,lpBiTreeNodee）//入栈函数
{
if（s.top-s.base>=s.stacksize）//空间已满
{
s.base=（lpBiTreeNode*）realloc（s.base,（s.stacksize+STACKINCREMENT）*sizeof（lpBiTreeNode））;//重新分配空间
if（!
s.base）
return0;
s.top=s.base+s.stacksize;//栈顶指针位置
s.stacksize+=STACKINCREMENT;//新栈的大小
}
*s.top=e;//元素e入栈
s.top++;//栈顶指针后移
return1;
}
intIn（intc,int*op）//判断c是否在op中，op为以结尾的数组
{
while（*op!
=0）//比较所有元素，最后一个为0
{
if（c==*op）//相等，存在return1
return1;
op++;//op指针后移
}
return0;
}
intPrecede（inttheta1,inttheta2）//比较优先级
{
inti,j;
intop_look[7][7]=
{{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=',''},
{'>','>','>','>','','>','>'},
{'<','<','<','<','<','','='}
};//运算符优先级二维数组
switch（theta1）//定位theta1
{
case'+':
i=0;
break;
case'-':
i=1;
break;
case'*':
i=2;
break;
case'/':
i=3;
break;
case'（':
i=4;
break;
case'）':
i=5;
break;
case'#':
i=6;
break;
default:
return0;
}
switch（theta2）//定位theta2
{
case'+':
j=0;
break;
case'-':
j=1;
break;
case'*':
j=2;
break;
case'/':
j=3;
break;
case'（':
j=4;
break;
case'）':
j=5;
break;
case'#':
j=6;
break;
default:
return0;
}
returnop_look[i][j];//判断优先级
}
intisNum（intc）//是不是数字
{
if（c>='0'&&c<='9'）//ascii码
return1;
elsereturn0;
}
intGetInput（Int_Float*Result）//返回值：
无，1数字，2符号
{
staticintbuffer=0;//缓存存储数字后的符号
intc;
Int_Floatresult;
intIsNumber=0;//是否为数字
intIsFloat=0;//是否为小数
inti,t=1;
result.Operand=0;
if（In（buffer,OP））//缓存中有符号
{
result.Operator=buffer;
buffer=0;
Result->Operator=result.Operator;
returnSIMBLE;//符号
}//去前导空格
c=getchar（）;
while（c==''&&c!
=10）
{
c=getchar（）;
}
while（c!
=''&&c!
=10）//不是空格和回车
{
if（isNum（c））//是数字
{
IsNumber=1;
c=c-48;//字符到整型
if（IsFloat==0）
result.Operand=result.Operand*10+c;
else
{
result.Operand=result.Operand*10+c;
IsFloat++;
}
}
elseif（c=='.'）
{
if（IsFloat!
=0）//两个小数点
{
Result->Operand=0;
returnERROR;
}
else
IsFloat=1;
}
elseif（In（c,OP））
{
if（IsNumber）//数字后接符号
{
if（IsFloat==1）
{
Result->Operand=0;
returnERROR;
}
else
{
buffer=c;
for（i=0;it*=10;
Result->Operand=result.Operand/（float）t;
returnNUMBER;//数字
}
}
else
{
Result->Operator=c;
returnSIMBLE;//符号
}
}
c=getchar（）;
}
buffer=0;
if（IsNumber）//处理数字
{
if（IsFloat==1）
{
Result->Operand=0;
returnERROR;
}
else
{
for（i=0;it*=10;
Result->Operand=result.Operand/（float）t;
returnNUMBER;
}
}
elseif（result.Operand==0）//错误输入
{
Result->Operand=0;
returnERROR;
}
else//处理符号
{
Result->Operator=result.Operator;
returnSIMBLE;
}
}
lpBiTreeNodeCreateBiTree（）//创建新的二叉树
{
SqStackOperand;//操作数
SqStackOperator;//操作符
lpBiTreeNodepNode;
lpBiTreeNodetheta,a,b;
Int_Floatc;
printf（"********************************\n"）;
printf（"QAQ请输入一个算式并以'#'号结尾：
\n"）;
intr=GetInput（&c）;
InitStack（Operand）;//初始化操作数栈
InitStack（Operator）;//初始化操作符栈
pNode=（lpBiTreeNode）malloc（sizeof（BiTreeNode））;
pNode->Data.Operator='#';
pNode->IsOperator=1;
pNode->LChild=NULL;
pNode->RChild=NULL;
Push（Operator,pNode）;
while（!
（r==SIMBLE&&c.Operator=='#'）||GetTop（Operator）->Data.Operator!
='#'）//处理到#
{
if（r==ERROR）
returnNULL;
if（r==NUMBER）//是数字
{
pNode=（lpBiTreeNode）malloc（sizeof（BiTreeNode））;
pNode->Data.Operand=c.Operand;
pNode->IsOperator=0;
pNode->LChild=NULL;
pNode->RChild=NULL;
Push（Operand,pNode）;
r=GetInput（&c）;
}
elseif（r==SIMBLE）//是符号
{
switch（Precede（GetTop（Operator）->Data.Operator,c.Operator））
{
case'<':
//栈顶元素优先权低
pNode=（lpBiTreeNode）malloc（sizeof（BiTreeNode））;
pNode->Data.Operator=c.Operator;
pNode->IsOperator=1;
pNode->LChild=NULL;
pNode->RChild=NULL;
Push（Operator,pNode）;
r=GetInput（&c）;
break;
case'=':
//'（','）'相遇，脱括号
Pop（Operator,pNode）;
r=GetInput（&c）;
break;
case'>':
//栈顶元素优先权高,退栈并将运算结果入栈
Pop（Operator,theta）;
Pop（Operand,b）;
Pop（Operand,a）;
theta->LChild=a;
theta->RChild=b;
Push（Operand,theta）;
break;
}
}
}
returnGetTop（Operand）;
}
boolcalculate（lpBiTreeNodeRoot,float*result）//计算二叉树的值
{
floatresultLchild;
floatresultRchild;
if（Root!
=NULL）//非空
{
if（Root->LChild==NULL&&Root->RChild==NULL）//叶子节点
{
*result=Root->Data.Operand;
returntrue;
}
elseif（Root->LChild==NULL||Root->RChild==NULL）//不可能出现单子树情况
returnfalse;
else//左右子树都存在的情况，递归计算
{
switch（Root->Data.Operator）//取操作符
{
case'+':
if（calculate（Root->LChild,&resultLchild）==false）
returnfalse;
if（calculate（Root->RChild,&resultRchild）==false）
returnfalse;
*result=resultLchild+resultRchild;//该二叉树的值等于左子树的值加上右子树的值
break;
case'-':
if（calculate（Root->LChild,&resultLchild）==false）
returnfalse;
if（cal
升级会员 