树和二叉树的实验报告
时间:2025-07-01
时间:2025-07-01
树和二叉树的实验报告
《数据结构》
实验报告
题目: 树和二叉树
树和二叉树的实验报告
一、 用二叉树来表示代数表达式
(一)需求分析
输入一个正确的代数表达式,包括数字和用字母表示的数,运算符号+ - * / ^ =及括号。系统根据输入的表达式建立二叉树,按照先括号里面的后括号外面的,先乘后除的原则,每个节点里放一个数字或一个字母或一个操作符,括号不放在节点里。分别先序遍历,中序遍历,后序遍历此二叉树,并输出表达式的前缀式,中缀式和后缀式。 (二)系统设计
1. 本程序中用到的所有抽象数据类型的定义;
typedef struct BiNode //二叉树的存储类型
{
char s[20];
struct BiNode *lchild,*rchild; }BiTNode,*BiTree;
2. 主程序的流程以及各程序模块之间的层次调用关系,函数的调用关系图:
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)^0.5)/(2*a) (五)用户手册
打开界面后,根据提示,输入代数表达式,包括包括数字和用字母表示的数,运算符号+ - * / ^ =及括号。输入完毕回车后系统将显示表达式的前缀式,中缀式,后缀式。 (六)附录 源程序:
#include<stdio.h> #include<stdlib.h> #include <string.h>
树和二叉树的实验报告
typedef struct BiNode {
char ch,bt[1024]; int len=0;
void push(char c) { }
BiTree Create_RTree() {
BiTree T,Q,S; char *p; while(ch!=EOF) {
ch=getchar(); if(ch=='\n') { }
if(len>0) { }
return NULL;
//输入结束,堆栈中为右节点的值
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;
if (len<1024)
bt[len++] = c; char s[20];
struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;
else if (ch == '(') {
if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL;
memset(Q->s,0x00,sizeof(Q->s)); Q->rchild = NULL;
树和二叉树的实验报告
}
ch=getchar(); if(ch=='\n') return Q; Q->s[0]=ch;
Q->rchild=Create_RTree(); return Q;
else if(ch ==')') {
}
if(len>0) { }
return NULL;
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;
else if(ch =='+'||ch=='-'||ch =='*'||ch =='/'||ch =='^') {
if((T=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL; return NULL;
if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==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;
树和二叉树的实验报告
}
} else
{ }
T->rchild=S;
ch=getchar();
if(ch=='+'||ch =='-'||ch =='*'||ch =='/'||ch=='^')
break; *p++=ch;
return NULL;
else { }
BiTNode *Create_RootTree() {
BiTree Q,T;
while((ch=getchar())!= EOF) {
if (ch=='\n') { }
return NULL;
}
return NULL;
}
Q->lchild=T; Q->s[0]=ch;
if((Q->rchild = Create_RTree()) == NULL) else
return Q; return NULL; //堆栈中为左节点值 memcpy(T->s,bt,len); len =0;
} else
push(ch);
else if(ch==':') //构造根节点:= {
ch=getchar();
if(ch!='=') return NULL;
if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
树和二叉树的实验报告 …… 此处隐藏:3701字,全部文档内容请下载后查看。喜欢就下载吧 ……
上一篇:时代倾城(长沙)营销执行方案