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

《数据结构》

实验报告

题目：树和二叉树

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

（一）需求分析

输入一个正确的代数表达式，包括数字和用字母表示的数，运算符号+-*/^=及括号。

系统根据输入的表达式建立二叉树，按照先括号里面的后括号外面的，先乘后除的原则，每

个节点里放一个数字或一个字母或一个操作符，括号不放在节点里。分别先序遍历，中序遍

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

（二）系统设计

1.本程序中用到的所有抽象数据类型的定义；

typedefstructBiNode主程序的流程以及各程序模块之间的层次调用关系，函数的

调用关系图：

Main()

Create_RootTree()PreOrderTraverse(BiTreeT)InOrderTraverse(BiTreeT)

构造二叉树先序遍历二叉树中序遍历二叉树

PostOrderTraverse(BiTreeT)

后序遍历二叉树

Create_RTree()

构造右子树

3．列出各个功能模块的主要功能及输入输出参数

voidpush(charcc)

初始条件：输入表达式中的某个符号

操作结果：将输入的字符存入buf数组中去

BiTreeCreate_RTree()

初始条件：给出二叉树的定义表达式

操作结果：构造二叉树的右子树，即存储表达式等号右侧的字符组

BiTreeCreate_RootTree()

初始条件：给出二叉树的定义表达式

操作结果：构造存储输入表达式的二叉树，其中左子树存储‘X’，根节点存储‘：=’

voidPreOrderTraverse(BiTreeT)

初始条件：二叉树T存在

操作结果：先序遍历T，对每个节点调用函数Visit一次且仅一次

voidInOrderTraverse(BiTreeT)

初始条件：二叉树T存在

操作结果：中序遍历T，对每个节点调用函数Visit一次且仅一次

voidPostOrderTraverse(BiTreeT)

初始条件：二叉树T存在

操作结果：后序遍历T，对每个节点调用函数Visit一次且仅一次

intmain()

主函数，调用各方法，操作成功后返回0

（三）调试分析

调试过程中还是出现了一些拼写错误，经检查后都能及时修正。有些是语法设计上的

小错误，比如一些参变量的初始值设置错误，使得程序调试出错。还有操作符优先级设计不

够合理，在输出遍历表达式结果时有错误。在小组讨论分析后纠正了这些结果，并尽量改进

了算法的性能，减小时间复杂度。

有输入表达式建立二叉树的时间复杂度为O(n),先序遍历和中序遍历及后序遍历的时间复

杂度都为O(n).

（四）测试结果

X：=(-b+(b^2-4*a*c)^/(2*a)

（五）用户手册

打开界面后，根据提示，输入代数表达式，包括包括数字和用字母表示的数，运算符

号+-*/^=及括号。输入完毕回车后系统将显示表达式的前缀式，中缀式，后缀式。

（六）附录

源程序：

#include

#include

#include

typedefstructBiNode

{

chars[20];

structBiNode*lchild,*rchild;

}BiTNode,*BiTree;

charch,bt[1024];

intlen=0;

voidpush(charc)

{

if(len1024)

bt[len++]=c;

}

BiTreeCreate_RTree()

{

BiTreeT,Q,S;

char*p;

while(ch!=EOF)

{