标识符树和表达式求值

《数据结构》实验报告 - 1 - 实验内容或题目 1定义二叉树的结构如下 struct tree // 定义结构体 { int data; // 定义一个整型数据域 struct tree *left; // 定义左子树指针 struct tree *right; // 定义右子树指针 }; typedefstruct tree btnode; // 树的结构类型 typedefbtnode *bt; // 定义树结点的指针类型 2把算术表达式2*3+6/3的标识符树见图存入一维数组。 3求标识符树的前序遍历、中序遍历和后序遍历的序列。 4以后序计算标识符树的值。 实验目的与要求 1 掌握二叉树的数组存储方法。 2掌握二叉树的非线性特点、递归特点和动态特性。 3复习二叉树遍历算法和标识符树的概念。 4利用标识符树的后序计算表达式的值运算只涉及+、-、*、/。 实验步骤与源程序 ⑴ 实验步骤： 1. 从具体问题抽象出适当的数学模型 2. 设计求解数学模型的算法 3. 编制、运行并调试程序，直到解决实际问题。 ⑵ 源代码： #include #include struct tree { char data; struct tree *left; struct tree *right; }; 《数据结构》实验报告 - 2 - typedefstruct tree btnode; typedefbtnode *bt; int n; bt *createtree(int *data,int i) { btnewnode; if (data[i]==0||i>n) return NULL; else { newnode=(bt *)malloc(sizeof(bt)); newnode->data=data[i]; newnode->left=createtree(data,2*i); newnode->right=createtree(data,2*i+1); returnnewnode; } } void preorder(bt t) { if(t!=NULL) { printf(\ preorder(t->left); preorder(t->right); } } voidinorder(bt t) { if (t!=NULL) { inorder(t->left); printf(\ inorder(t->right); } } voidpostorder(bt t) { if(t!=NULL) { postorder(t->left); postorder(t->right); printf(\ } 《数据结构》实验报告 - 3 - } intcal(bt t) { int operand1=0; int operand2=0; intgetvalue(intop,int operand1,int operand2); if (t->left==NULL && t->right==NULL) return t->data-48; { operand1=cal(t->left); operand2=cal(t->right); returngetvalue(t->data,operand1,operand2); } } intgetvalue(intop,int operand1,int operand2) { switch((char)op) { case'*':return(operand1*operand2); case'/':return(operand1/operand2); case'+':return(operand1+operand2); case'-':return(operand1-operand2); } } void main() { bt T=NULL; intresult,k=1; int data[100]={' '}; charch; printf(\按层次遍历输入标识符树的结点数据，以回车键表示结束\\n\while((ch=getchar())!='\\n') data[k++]=ch; data[k]='\\0'; n=k-1; T=createtree(data,1); printf(\前序表达式：\preorder(T); printf(\中序表达式：\inorder(T); printf(\后序表达式：\postorder(T); result=cal(T); 《数据结构》实验报告 - 4 - printf(\表达式结果是：%d\\n\\n\ } 测试数据与实验结果（可以抓图粘贴） 结果分析与实验体会 本实验主要是掌握二叉树的存储方法、二叉树的非线性特点、递归特点、动态特性、二叉树遍历算法、标志符树的概念以及利用标识符树的后序计算表达式的值。 树形结构是一种重要的非线性结构，树是以分组关系定义的层次结构，其中二叉树为最常用。二叉树具有顺序存储结构和链式存储两种存储结构。在顺序存储时，必须按完全二叉树格式存储；在二叉链式存储时，每个结点有两个指针域，具有n个结点的二叉树共有2n个指针，其中指向左、右孩子的指针有n-1个，空指针有n+1个。将算术表达式用二叉树来表示称为标识符树，也称为二叉表示树，利用标识符树的后序遍历可以得到算术表达式的后缀表达式，这也是本实验的重点。本实验的求解标识符树的值就是通过表达式建立的标识符树的输出后序遍历的结果，而标识符树的后序遍历的结果即是原表达式的后缀表达式，然后只要通过后缀表达式便可得到标识符的结果。本实验有七个函数，bt *createtree(int *data,int i)是二叉树的建立，void preorder(bt t)是标识符树的先序遍历，void inorder(bt t)是标识符树的中序遍历，也是原算术表达式，void postorder(bt t)是后序遍历，即原算术表达式的后缀表达式，intcal(bt t)、intgetvalue(intop,int operand1,int operand2)则是来求表达式的结构的，最后一个就是主函数。二叉树是树中最常用的，而树形结构是一种重要的非线性结构。在数据库系统中树结构是信息的重要组织形式之一。所以学好树是为了以后学习打好扎实的基础。

本文来源：https://www.bwwdw.com/article/83e7.html