本科生实验报告（二叉树）.doc

数据结构实验报告一程序设计相关信息（1）实验题目：编写一个程序，先用二叉树来表示代数表达式，树的每一个结点包括一个运算符或运算数，代数表达式中只包含+.-.*./和一位整数且没有错误，并且要按照先乘除后加减的原则构造二叉树，如图所示是“1+2*3-4/5”代数表达式对应的二叉树。然后由对应的二叉树计算该表达式的值。2354*1/+-用二叉树来表示代数表达式(2)实验目的：用二叉树来表示代数表达式并计算该表达式的值。（3）算法流程图： (4)实验结果：（5）附录：程序原代码：#include typedef struct node / 结点类型定义 float data; bool sign; struct node *lchild; struct node *rchild; BTNode; BTNode *create(char *str,int n) / 创建代数表达式对应的二叉树 BTNode *root = NULL; /始终指向当前已经生成的二叉树的根 BTNode *p = NULL; /始终指向当前待处理结点 float ch; int j = 0; ch = strj; while(ch != 0 & j data = ch; p-sign = false; if(root = NULL) root = p; else if(root-rchild = NULL) root-rchild = p; else root-rchild-rchild=p; else if(ch = + | ch = -) p = new BTNode; p-data = ch; p-sign = true; p-rchild = NULL; p-lchild = root; root = p; root-rchild = NULL; else if(ch = * | ch = /) if(root-data = 0 & root-data data = * | root-data = /) p=new BTNode; p-data = ch; p-sign = true; p-rchild = NULL; p-lchild = root; root = p; else p = new BTNode; p-data = ch; p-sign = true; p-lchild = root-rchild; root-rchild = p; p-rchild = NULL; j+; ch=strj; return root; float result(BTNode *b) /计算表达式 float n1,n2; if(b-sign = false & b-data = 0 & b-data data - 0); n1 = result(b-lchild);/计算左子表达式 n2 = result(b-rchild);/计算右子表达式 if (b-sign = true & b-data = +) b-data = n1 + n2; else if (b-sign = true & b-data = -) b-data = n1 - n2; else if (b-sign = true & b-data = *) b-data = n1 * n2; else if (b-sign = true & b-data = /) b-data = n1 / n2; return b-data; void main() BTNode *b=NULL,*q=NULL; char str100; printf(请输入符合要求的代数表达式：); scanf(%s,str); int n