树和二叉树的实验报告

树和二叉树的实验报告

《数据结构》

实验报告

题目： 树和二叉树

树和二叉树的实验报告

一、 用二叉树来表示代数表达式

（一）需求分析

输入一个正确的代数表达式，包括数字和用字母表示的数，运算符号+ - * / ^ =及括号。系统根据输入的表达式建立二叉树，按照先括号里面的后括号外面的，先乘后除的原则，每个节点里放一个数字或一个字母或一个操作符，括号不放在节点里。分别先序遍历，中序遍历，后序遍历此二叉树，并输出表达式的前缀式，中缀式和后缀式。 （二）系统设计

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)

树和二叉树的实验报告

}

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 { }

void PreOrderTraverse(BiTree T) { }

void InOrderTraverse(BiTree T) {

if(T) { } else

InOrderTraverse(T->lchild); printf("%s ",T->s); InOrderTraverse(T->rchild); if(T) { } else

return;

printf("%s ",T->s);

PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); }

return NULL;

}

push(ch);

树和二叉树的实验报告

}

…… 此处隐藏：3332字，全部文档内容请下载后查看。喜欢就下载吧 ……