《标识符树与表达式求值》由会员分享，可在线阅读，更多相关《标识符树与表达式求值（6页珍藏版）》请在金锄头文库上搜索。
1、1实验目的(1) 掌握二叉树的数组存储方法。(2) 掌握二叉树的非线性特点、递归特点和动态特性。(3) 复习二叉树遍历算法和标识符树的概念。(4) 利用标识符树的后序计算表达式的值( 运算只涉及 +、- 、*、/) 。2实验内容(1) 定义二叉树的结构如下：struct tree / 定义结构体 int data; / 定义一个整型数据域struct tree *left; / 定义左子树指针struct tree *right; / 定义右子树指针;typedef struct tree btnode; / 树的结构类型typedef btnode *bt; / 定义树结点的指针类型(2)
2、把算术表达式 2*3+6/3 的标识树 (如下图 ) 存入一维数组。(3) 求标识符树的前序遍历、中序遍历和后序遍历的 序列。(4) 以后序计算标识符树的值。3参考程序#include #include struct tree / 树的结构声明 char data; / 结点数据struct tree *left; / 指向左子树的指针struct tree *right; / 指向右子树的指针; typedef struct tree treenode; / 树的结构新类型typedef treenode *btree; / 声明树结点指针类型int n; / n计算字符串长度btree c
3、reatebtree(int *data,int pos) / 创建表达式二叉树 btree newnode; / 新结点指针if (datapos=0|posn) / 终止条件return NULL; else newnode=new treenode; / 创建新结点内存newnode-data=datapos; / 创建结点内容newnode-left=createbtree(data,2*pos); / 创建左子树递归 调用newnode-right=createbtree(data,2*pos+1); / 创建右子树递归调用return newnode; void preorder(
4、btree ptr) / 表达式二叉树前序输出 if(ptr!=NULL) / 终止条件 printf(“ %c“,ptr-data); / 输出结点内容preorder(ptr-left); / 左子树preorder(ptr-right); / 右子树 void inorder(btree ptr) / 表达式二叉树中序输出 if (ptr!=NULL) / 终止条件 inorder(ptr-left); / 左子树printf(“ %c“,ptr-data); / 输出结点内容inorder(ptr-right); / 右子树 void postorder(btree ptr) / 表达
5、式二叉树后序 输出 if(ptr!=NULL) / 右子树 postorder(ptr-left); / 左子树postorder(ptr-right); / 右子树printf(“ %c“,ptr-data); / 输出结点内容 int cal(btree ptr) / 表达式二叉树后序计值 int operand1=0; / 定义操作数变量1int operand2=0; / 定义操作数变量2int getvalue(int op,int operand1,int operand2); / 对getvalue函数作声明if (ptr-left=NULL /字符数字转为数值esleopera
6、nd1=cal(ptr-left); / 左子树operand2=cal(ptr-right); / 右子树return getvalue(ptr-data,operand1,operand2); int getvalue(int op,int operand1,int operand2) / 计算二叉树表达式值 switch(char)op) case*:return(operand1*operand2); case/:return(operand1/operand2); case+:return(operand1+operand2); case-:return(operand1-opera
7、nd2); void main() / 主程序 btree root=NULL; / 表达式二叉树指针int result,k=1; / 定义输出结果变 量int data100= ; char ch; printf(“按前序输入标识符树的结点数据，以回车键表示结束n“); while(ch=getchar()!=n) datak+=ch; datak=0; n=k-1; root=createbtree(data,1); / 创建表达式二叉树printf(“tn 前序表达式： “); preorder(root); / 前序输出二叉树printf(“tnn 中序表达式： “); inorde
8、r(root); / 中序输出二叉树printf(“tnn 后序表达式： “); postorder(root); / 后序输出二叉树result=cal(root); / 计算printf(“tnn 表达式结果是： %dnn“,result); / 输出计算结果 4程序运行运行本程序，按标识符树的前序序列，把：+,*,/,2,3,6,3 存入一维数组 data ，所以程序运行以后就能输出结果如下：注意：字符之间不允许空格，数值只能是一位。5算法分析Createbtree函数的时间复杂度为： t1(n)=O(n) 。preorder 函数的时间复杂度为： t2(n)=O(n) 。inorder函数的时间复杂度为： t3(n)=O(n) 。postorder函数的时间复杂度为： t4(n)=O(n) 。cal 函数的时间复杂度为： t5(n)=O(n) 。getvalue 函数的时间复杂度为： t6(n)=O(1) 。
