《数据结构》实验报告题目：树和二叉树一、用二叉树来表示代数表达式（一）需求分析输入一个正确的代数表达式，包括数字和用字母表示的数，运算符号+ - * / ^ =及括号。

系统根据输入的表达式建立二叉树，按照先括号里面的后括号外面的，先乘后除的原则，每个节点里放一个数字或一个字母或一个操作符，括号不放在节点里。

分别先序遍历，中序遍历，后序遍历此二叉树，并输出表达式的前缀式，中缀式和后缀式。

（二）系统设计1. 本程序中用到的所有抽象数据类型的定义；typedef struct BiNode 主程序的流程以及各程序模块之间的层次调用关系，函数的调用关系图：3．列出各个功能模块的主要功能及输入输出参数void push(char cc)初始条件：输入表达式中的某个符号操作结果：将输入的字符存入buf数组中去BiTree Create_RTree()初始条件：给出二叉树的定义表达式操作结果：构造二叉树的右子树，即存储表达式等号右侧的字符组BiTree Create_RootTree()初始条件：给出二叉树的定义表达式操作结果：构造存储输入表达式的二叉树，其中左子树存储‘X’，根节点存储‘：=’void PreOrderTraverse(BiTree T)初始条件：二叉树T存在操作结果：先序遍历T，对每个节点调用函数Visit一次且仅一次void InOrderTraverse(BiTree T)初始条件：二叉树T存在操作结果：中序遍历T，对每个节点调用函数Visit一次且仅一次void PostOrderTraverse(BiTree T)初始条件：二叉树T存在操作结果：后序遍历T，对每个节点调用函数Visit一次且仅一次int main()主函数，调用各方法，操作成功后返回0（三）调试分析调试过程中还是出现了一些拼写错误，经检查后都能及时修正。

有些是语法设计上的小错误，比如一些参变量的初始值设置错误，使得程序调试出错。

还有操作符优先级设计不够合理，在输出遍历表达式结果时有错误。

在小组讨论分析后纠正了这些结果，并尽量改进了算法的性能，减小时间复杂度。

有输入表达式建立二叉树的时间复杂度为O(n),先序遍历和中序遍历及后序遍历的时间复杂度都为O(n).（四）测试结果X：=(-b+(b^2-4*a*c)^/(2*a)（五）用户手册打开界面后，根据提示，输入代数表达式，包括包括数字和用字母表示的数，运算符号+ - * / ^ =及括号。

输入完毕回车后系统将显示表达式的前缀式，中缀式，后缀式。

（六）附录源程序：#include<>#include<>#include <>typedef struct BiNode{char s[20];struct BiNode *lchild,*rchild; }BiTNode,*BiTree;char ch,bt[1024];int len=0;void push(char c){if (len<1024)bt[len++] = c;}BiTree Create_RTree(){BiTree T,Q,S;char *p;while(ch!=EOF){ch=getchar();if(ch=='\n'){if(len>0){//输入结束，堆栈中为右节点的值if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)return NULL;memset(Q->s,0x00,sizeof(Q->s));Q->lchild=NULL;Q->rchild=NULL;memcpy(Q->s,bt,len);len =0;return Q;}return NULL;}else if (ch == '('){if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)return NULL;memset(Q->s,0x00,sizeof(Q->s));Q->rchild = NULL;Q->lchild =Create_RTree();ch=getchar();if(ch=='\n') return Q;Q->s[0]=ch;Q->rchild=Create_RTree();return Q;}else if(ch ==')'){if(len>0){if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)return NULL;memset(Q->s,0x00,sizeof(Q->s));Q->lchild=NULL;Q->rchild=NULL;memcpy(Q->s,bt,len);len=0;return Q;}return NULL;}else if(ch =='+'||ch=='-'||ch =='*'||ch =='/'||ch =='^') {if((T=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)return NULL;if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)return NULL;memset(Q->s,0x00,sizeof(Q->s));memset(T->s,0x00,sizeof(T->s));T->lchild=NULL;T->rchild=NULL;if(len==0){if(ch =='+'||ch =='-'){// 只有+-号前面可以不是数字,此时左节点为空T->s[0]=ch;if((S=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)return NULL;memset(S->s,0x00,sizeof(S->s));S->lchild=NULL;S->rchild=NULL;p=S->s;while(1){ch=getchar();if(ch=='+'||ch =='-'||ch =='*'||ch =='/'||ch=='^')break;*p++=ch;}T->rchild=S;}elsereturn NULL;}else{//堆栈中为左节点值memcpy(T->s,bt,len);len =0;}Q->lchild=T;Q->s[0]=ch;if((Q->rchild = Create_RTree()) == NULL)return NULL;elsereturn Q;} elsepush(ch);}return NULL;}BiTNode *Create_RootTree(){BiTree Q,T;while((ch=getchar())!= EOF){if (ch=='\n'){return NULL;}else if(ch==':') //构造根节点：={ch=getchar();if(ch!='=') return NULL;if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)return NULL;memset(Q->s,0x00,sizeof(Q->s));memcpy(Q->s,bt,len);len =0;Q->lchild = NULL;Q->rchild = NULL;if((T=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)return NULL;T->lchild = Q;memset(T->s,0x00,sizeof(T->s));memcpy(T->s,":=",2);//继续处理:=后面的数据，作为根节点的右节点if((T->rchild=Create_RTree())==NULL)return NULL;return T;}else{push(ch);}}return NULL;}void PreOrderTraverse(BiTree T){if(T){printf("%s ",T->s);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}elsereturn;}void InOrderTraverse(BiTree T){if(T){InOrderTraverse(T->lchild);printf("%s ",T->s);InOrderTraverse(T->rchild);}else{return;}}void PostOrderTraverse(BiTree T){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%s ",T->s);}elsereturn;}int main(){printf("请输入一个中缀表达式：\n");BiTree T=NULL;if((T=Create_RootTree())==NULL)return 0;printf("先序遍历：");PreOrderTraverse(T);printf("\n");printf("中序遍历：");InOrderTraverse(T);printf("\n");printf("后序遍历：");PostOrderTraverse(T);printf("\n");return 0;}测试数据结果：X：=(-b+(b^2-4*a*c)^/(2*a)二、求二叉树中从根结点到叶子节点的路径（一）需求分析以无歧义的陈述说明程序设计的任务，强调程序要做什么。

明确规定：（1）．输入的形式和输入值的范围；（2）输出的形式（3）程序所能达到的功能（4）测试数据：包括正确的输入及其输出结果，含有错误的输入及其输出结果。