树和二叉树的实验报告.doc

《树和二叉树的实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《数据结构》实验报告题目：树和二叉树一、用二叉树来表示代数表达式（一）需求分析输入一个正确的代数表达式，包括数字和用字母表示的数，运算符号+-*/^=及括号。系统根据输入的表达式建立二叉树，按照先括号里面的后括号外面的，先乘后除的原则，每个节点里放一个数字或一个字母或一个操作符，括号不放在节点里。分别先序遍历，中序遍历，后序遍历此二叉树，并输出表达式的前缀式，中缀式和后缀式。（二）系统设计1.本程序中用到的所有抽象数据类型的定义；typedefstructBiNode//二叉树的存储类型{chars[20];structBiNode*lchild,*rchild;}BiTNode

2、,*BiTree;2.主程序的流程以及各程序模块之间的层次调用关系，函数的调用关系图：Create_RootTree()构造二叉树Main()Create_RTree()构造右子树PreOrderTraverse(BiTreeT)先序遍历二叉树InOrderTraverse(BiTreeT)中序遍历二叉树PostOrderTraverse(BiTreeT)后序遍历二叉树3．列出各个功能模块的主要功能及输入输出参数voidpush(charcc)初始条件：输入表达式中的某个符号操作结果：将输入的字符存入buf数组中去BiTreeCreate_RTree()初始条件：给出二叉树的定义

3、表达式操作结果：构造二叉树的右子树，即存储表达式等号右侧的字符组BiTreeCreate_RootTree()初始条件：给出二叉树的定义表达式操作结果：构造存储输入表达式的二叉树，其中左子树存储‘X’，根节点存储‘：=’voidPreOrderTraverse(BiTreeT)初始条件：二叉树T存在操作结果：先序遍历T，对每个节点调用函数Visit一次且仅一次voidInOrderTraverse(BiTreeT)初始条件：二叉树T存在操作结果：中序遍历T，对每个节点调用函数Visit一次且仅一次voidPostOrderTraverse(BiTreeT)初始条件：二叉树T存在操

4、作结果：后序遍历T，对每个节点调用函数Visit一次且仅一次intmain()主函数，调用各方法，操作成功后返回0（三）调试分析调试过程中还是出现了一些拼写错误，经检查后都能及时修正。有些是语法设计上的小错误，比如一些参变量的初始值设置错误，使得程序调试出错。还有操作符优先级设计不够合理，在输出遍历表达式结果时有错误。在小组讨论分析后纠正了这些结果，并尽量改进了算法的性能，减小时间复杂度。有输入表达式建立二叉树的时间复杂度为O(n),先序遍历和中序遍历及后序遍历的时间复杂度都为O(n).（四）测试结果X：=(-b+(b^2-4*a*c)^0.5)/(2*a)（五）用户手册打开界面

5、后，根据提示，输入代数表达式，包括包括数字和用字母表示的数，运算符号+-*/^=及括号。输入完毕回车后系统将显示表达式的前缀式，中缀式，后缀式。（六）附录源程序：#include#include#includetypedefstructBiNode{chars[20];structBiNode*lchild,*rchild;}BiTNode,*BiTree;charch,bt[1024];intlen=0;voidpush(charc){if(len<1024)bt[len++]=c;}BiTreeCreate_RTree

6、(){BiTreeT,Q,S;char*p;while(ch!=EOF){ch=getchar();if(ch==''){if(len>0){//输入结束，堆栈中为右节点的值if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)returnNULL;memset(Q->s,0x00,sizeof(Q->s));Q->lchild=NULL;Q->rchild=NULL;memcpy(Q->s,bt,len);len=0;returnQ;}returnNULL;}elseif(ch=='('){if((Q=(BiTNode*)malloc

7、(sizeof(BiTNode)))==NULL)returnNULL;memset(Q->s,0x00,sizeof(Q->s));Q->rchild=NULL;Q->lchild=Create_RTree();ch=getchar();if(ch=='')returnQ;Q->s[0]=ch;Q->rchild=Create_RTree();returnQ;}elseif(ch==')'){if(len>0){if((Q=(BiTNode*)malloc(sizeof(B