[高效]有效数据结构基础（第二版）试验7：标识符树与表达式求值.doc

该【[高效]有效数据结构基础（第二版）试验7：标识符树与表达式求值 】是由【gorynich】上传分享，文档一共【5】页，该文档可以免费在线阅读，需要了解更多关于【[高效]有效数据结构基础（第二版）试验7：标识符树与表达式求值 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。[高效]有效数据结构基础(第二版)试验7:标识符树与表达式求值
实用数据结构基础(第二版)实验7:标识符树与表达式求值#include<>
#include<>
structtree//树的结构声明
{
chardata;//结点数据
structtree*left;//指向左子树的指针
structtree*right;//指向右子树的指针
};
typedefstructtreetreenode;//树的结构新类型
typedeftreenode*btree;//声明树结点指针类型
intn;//n
计算字符串长度
btreecreatebtree(int*data,intpos)//创建表达式二叉树
{
btreenewnode;//新结点指针
if(data[pos]==0||pos>n)//终止条件
returnNULL;
else
{
newnode=newtreenode;//创建
新结点内存
newnode->data=data[pos];//创建结点内容
newnode->left=createbtree(data,2*pos);//创建左子树递归调用
newnode->right=createbtree(data,2*pos+1);//创建右子树递归调用
returnnewnode;
}
}
voidpreorder(btreeptr)//表达式二叉树前序输出
{
if(ptr!=NULL)//终止条件
{
printf("%c",ptr->data);//输出结点内容
preorder(ptr->left);//左子树
preorder(ptr->right);//右子树
}
}
voidinorder(btreeptr)//表达式二叉树中序输出
{
if(ptr!=NULL)//终止条件
{
inorder(ptr->left);//左子树
printf("%c",ptr->data);//输出结点内容
inorder(ptr->right);//右子树
}
}
voidpostorder(btreeptr)//表达式二叉树后序输出
{
if(ptr!=NULL)//右子树
{
postorder(ptr->left);//左子树
postorder(ptr->right);//右子树
printf("%c",ptr->data);//输出结点内容
}
}
intcal(btreeptr)//表达式二叉树后序计值
{
intoperand1=0;//定义操作数变量1
intoperand2=0;//定
义操作数变量2
intgetvalue(intop,intoperand1,intoperand2);//对getvalue函数作声明
if(ptr->left==NULL&&ptr->right==NULL)//终止条件
returnptr->data-48;
{
operand1=cal(ptr->left);//左子树
operand2=cal(ptr->right);//右子树
returngetvalue(ptr->data,operand1,operand2);
}
}
intgetvalue(intop,intoperand1,intoperand2)//计算二叉树表达式值
{
switch((char)op)
{
case'*':return(operand1*operand2);
case'/':return(operand1/operand2);
case'+':return(operand1+operand2);
case'-':return(operand1-operand2);
}
}
voidmain()//主程序
{
btreeroot=NULL;//表达式二叉树指针
intresult,k=1;//定义输出结果变量
intdata[100]={''};
charch;
printf("按前序输入标识符树的结点数据,以回车键表示结束\n");
while((ch=getchar())!='\n')
data[k++]=ch;
data[k]='\0';
n=k-1;
root=createbtree(data,1);//创建表达式二叉树
printf("\t\n前序表达式:");
preorder(root);//前序输出二叉树
printf("\t\n\n中序表达式:");
inorder(root);//中序输出二叉树
printf("\t\n\n后序表达式:");
postorder(root);//后序输出二叉树
result=cal(root);//计算
printf("\t\n\n表达式结果是:%d\n\n",result);//输出计算结果
}