树和二叉树的实验报告

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

2、de,*bitree;2. 主程序的流程以及各程序模块之间的层次调用关系，函数的调用关系图：create_roottree()构造二叉树main()create_rtree()构造右子树preordertraverse(bitree t)先序遍历二叉树inordertraverse(bitree t)中序遍历二叉树postordertraverse(bitree t)后序遍历二叉树3列出各个功能模块的主要功能及输入输出参数void push(char cc)初始条件：输入表达式中的某个符号操作结果：将输入的字符存入buf数组中去bitree create_rtree()初始条件：给出二叉树的定

3、义表达式操作结果：构造二叉树的右子树，即存储表达式等号右侧的字符组bitree create_roottree()初始条件：给出二叉树的定义表达式操作结果：构造存储输入表达式的二叉树，其中左子树存储x，根节点存储：=void preordertraverse(bitree t)初始条件：二叉树t存在操作结果：先序遍历t，对每个节点调用函数visit一次且仅一次void inordertraverse(bitree t)初始条件：二叉树t存在操作结果：中序遍历t，对每个节点调用函数visit一次且仅一次void postordertraverse(bitree t)初始条件：二叉树t存在操作结果

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

5、，输入代数表达式，包括包括数字和用字母表示的数，运算符号+ - * / =及括号。输入完毕回车后系统将显示表达式的前缀式，中缀式，后缀式。（六）附录源程序：#include#include#include typedef struct binodechar s20;struct binode *lchild,*rchild;bitnode,*bitree;char ch,bt1024;int len=0;void push(char c)if (len0)/输入结束，堆栈中为右节点的值if(q=(bitnode*)malloc(sizeof(bitnode)=null)return null;

6、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-s0=ch;q-rchild=creat

7、e_rtree();return q; else if(ch =) if(len0)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=(b

8、itnode*)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-s0=ch;if(s=(bitnode*)malloc(sizeof(bitnode)=null)return null;memset(s-s,0x00,sizeof(s-s);s-lchild=null;s-rchild=null;p=

9、s-s;while(1)ch=getchar();if(ch=+|ch =-|ch =*|ch =/|ch=)break;*p+=ch;t-rchild=s; else return null; else /堆栈中为左节点值memcpy(t-s,bt,len);len =0;q-lchild=t;q-s0=ch;if(q-rchild = create_rtree() = null)return null;elsereturn q; elsepush(ch);return null;bitnode *create_roottree()bitree q,t; while(ch=getchar()

10、!= 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;mems

11、et(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)inord

12、ertraverse(t-lchild);printf(%s ,t-s);inordertraverse(t-rchild);elsereturn;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(先序遍历：);preordert

13、raverse(t);printf(n); printf(中序遍历：);inordertraverse(t);printf(n);printf(后序遍历：);postordertraverse(t);printf(n);return 0;测试数据结果：x：=(-b+(b2-4*a*c)0.5)/(2*a)二、求二叉树中从根结点到叶子节点的路径（一）需求分析以无歧义的陈述说明程序设计的任务，强调程序要做什么。明确规定：（1）输入的形式和输入值的范围；（2） 输出的形式（3） 程序所能达到的功能（4） 测试数据：包括正确的输入及其输出结果，含有错误的输入及其输出结果。（二）系统设计1 说明本程序中

14、用到的所有抽象数据类型的定义；typedef char elemtype;typedef struct node elemtype data; struct node *lchild; struct node *rchild;bitnode;2 主程序的流程以及各程序模块之间的层次调用关系，画出函数的调用关系图。3 列出各个功能模块的主要功能及输入输出参数。（三）调试分析内容包括：（1）调试过程中遇到的问题是如何解决的及对设计与实现的回顾讨论与分析。（2） 算法的时间复杂度分析（包括基本操作和其他算法）和改进设想；（3） 经验与体会等。（四）测试结果（五）用户手册说明如何使用你编写的程序，详细

15、列出每一步操作步骤。（6） 附录 #include #define null 0#define max 50using namespace std;typedef struct nodechar data;struct node *lc,*rc;btnode;void creattree(btnode *&b) /递归创建二叉树char i; cini;if(i=#) b=null; elseb=(btnode *)malloc(sizeof(btnode); b-data=i; creattree(*&b-lc); creattree(*&b-rc);void findleafnode(btnode *b) /找出所有叶子结点if(b!=null)if(b-lc=null&b-rc=null) coutdatalc);findleafnode(b-rc);btnode *stmax;int front,rear=-1;void allpath(btnode *b) /从叶子结点到根结点的路径if(b!=null)rear+; strear=b;/当前结点入栈 if(b-lc=null&b-rc=null) /当b为叶子结点时 front=rear; wh