资源描述
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*3+6/3的标识树(如下图)存入一维数组。(3) 求标识符树的前序遍历、中序遍历和后序遍历的 序列。(4) 以后序计算标识符树的值。3 参考程序#include#includestruct tree/ 树的结构声明char data;/ 结点数据/ 指向左子树的指针/ 指向右子树的指针;typedef struct tree treenode;/ 树的结构新类型typedef treenode *btree;/ 声明树结点指针类型int n;n计算字符串长度btree createbtree(int *data,int pos) 树/ 创建表达式二叉btree newnode;/ 新结点指针if (datapos=0|posn)/ 终止条件return NULL;elsenewnode=new treenode;/ 创建新结点内存newnode-data=datapos;/ 创建结点内容struct tree *left;struct tree *right;/ 创建左子树递归newnode-left=createbtree(data,2*pos);调用newnode-right=createbtree(data,2*pos+1); / 创建右子树递归调用return newnode;void 输出preorder(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)输出if(ptr!=NULL)postorder(ptr-left);postorder(ptr-right);printf( %c,ptr-data);/ 表达式二叉树/ 定义操作数变量1/ 定义操作数变量2/ 对/ 终止条件/字符数字转为数值/ 左子树/ 右子树/ 计算二叉int cal(btree ptr)后序计值int operand1=0;int operand2=0;int getvalue(int op,int operand1,int operand2);getvalue函数作声明if (ptr-left=NULL & ptr-right=NULL)return ptr-data-48;esleoperand1=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-operand2);void main() / 主程序/ 表达式二叉树指针/ 定义输出结果变btree root=NULL;int result,k=1; 量int data100= ;char ch;prin tf（按前序输入标识符树的结点数据，以回车键表示结束n）;while(ch=getchar()!=n)datak+=ch;datak=0;n=k-1;root=createbtree(data,1); 二叉树printf(tn 前序表达式：);preorder(root);printf(tnn 中序表达式：);inorder(root);/ 创建表达式/ 前序输出二叉树/ 中序输出二叉树printf（tnn 后序表达式：）;/ 后序输出二叉树/ 计算postorder(root);result=cal(root);printf(tnn 表达式结果是：dnn,result);/输出计算结果 4程序运行运行本程序，按标识符树的前序序列，把：+,*,/,2,3,6,3存入一维数组data，所以程序运行以后就能输出结果如下：按前序输入标识符树的结点数据，以回车键表示结車+*z2363前序表达式；+ * 2 3 / & 3中序表迖式：2 * 36 / 3后序表达式:2 3 * 6 3 / +表迖式结杲是：8注意：字符之间不允许空格，数值只能是一位。5算法分析Createbtree函数的时间复杂度为：t (n)=O(n)。 1preorder函数的时间复杂度为：t (n)=0(n)。2inorder函数的时间复杂度为：t (n)=0(n)。3postorder函数的时间复杂度为：t (n)=0(n)。4cal函数的时间复杂度为：t (n)=O(n)。5get value函数的时间复杂度为：t (n)=O(l)。6
展开阅读全文