数据结构-实验7-标识符树与表达式求值.doc

《数据结构-实验7-标识符树与表达式求值.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、实验目的（1）掌握二叉树的数组存储方法。（2）掌握二叉树的非线性特点、递归特点和动态特性。（3）复习二叉树遍历算法和标识符树的概念。（4）利用标识符树的后序计算表达式的值（运算只涉及+、-、*、/）。2、实验内容（1）定义二叉树的结构如下：structtree//定义结构体{intdata;//定义一个整型数据域structtree*left;//定义左子树指针structtree*right;//定义右子树指针};typedefstructtreebtnode;//树的结构类型+*/2363标识符树typedefbtnode*bt;//定

2、义树结点的指针类型（2）把算术表达式2*3+6/3的标识符树（见图7-35）存入一维数组。（3）求标识符树的前序遍历、中序遍历和后序遍历的序列。（4）以后序计算标识符树的值。3、实验要求（1)用C（C++）语言完成算法设计和程序设计。（2)上机调试通过实验程序。（3)输入数据，检验程序运行结果。（4)给出具体的算法分析，包括时间复杂度和空间复杂度等。（5)撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。4、实验步骤与源程序⑴实验步骤先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，其中，需要设计一个主函数来实现菜

3、单的输出，设计另外五个函数来求分别实现新建，先序遍历输出，中序遍历输出，后序遍历输出，表达式求值，最后，串接函数，并调试程序，多次调试后，发现没有问题，得出实验结果，并截图。⑵源代码#include#includestructtree//树的结构声明{chardata;//结点数据structtree*left;//指向左子树的指针structtree*right;//指向右子树的指针};typedefstructtreetreenode;//树的结构新类型typedeftreenode*btree;//声

4、明树结点指针类型intn;//n计算字符串长度btreecreatebtree(int*data,intpos)//创建表达式二叉树{btreenewnode;//新结点指针if(data[pos]==0

5、

6、pos>n)//终止条件returnNULL;else{newnode=newtreenode;//创建新结点内存newnode->data=data[pos];//创建结点内容newnode->left=createbtree(data,2*pos);//创建左子树递归调用newnode->right=createbtree(data,2

7、*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);

8、//输出结点内容inorder(ptr->right);//右子树}}voidpostorder(btreeptr)//表达式二叉树后序输出{if(ptr!=NULL)//右子树{postorder(ptr->left);//左子树postorder(ptr->right);//右子树printf("%c",ptr->data);//输出结点内容}}intcal(btreeptr)//表达式二叉树后序计值{intoperand1=0;//定义操作数变量1intoperand2=0;//定义操作数变量2intgetvalue(intop,into

9、perand1,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)

10、{case'*':return(operand1*operand2);case'/':return(operand1/operand2);case'+